程序員哈希表是什麼

❶ 面試中如何回答HashMap的工作原理

用過哪些Map類，都有什麼區別，HashMap是線程安全的嗎,並發下使用的Map是什麼，他們
內部原理分別是什麼，比如存儲方式，hashcode，擴容，默認容量等。
JAVA8的ConcurrentHashMap為什麼放棄了分段鎖，有什麼問題嗎，如果你來設計，你如何
設計。
有沒有有順序的Map實現類，如果有，他們是怎麼保證有序的。

hashmap的實現原理，https://blog.csdn.net/mbshqqb/article/details/79799009

下面是自己的總結:

存儲結構:
裡面存儲的是一個entry數組，每個數組元素中的結構是一個entry鏈表
Entry是map中的一個靜態內部類，其中的變數有:key,value,hashcocd,下一個Entry

什麼是hash？
又稱散列，將任意長度的輸入通過散列演算法轉換成固定長度的輸出，該輸出就是散列值。這是一種壓縮映射，散列值的空間通常遠小於輸出的空間。不同的輸入有可能會散列出相同的輸出，因此不能從散列值來確定唯一的輸入值。這也是為什麼比較兩個對象不能僅僅使用hashcode方法比較的原因。

hash碰撞:
對不同的值進行hash運算生成了相同的散列值。這個是不可避免的，但是我們需要盡量的減少其帶來的損失。
(1)設計好的hash演算法讓其盡可能的分布均勻
hashmap中的hash演算法解析
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
讓key的hashcode本身與它右移16位異或，是為了讓它的高位與低位混合，增加低位的隨機性，同時也變相保持了高位的特徵

計算元素位置的演算法:
int index = hash & (arrays.length-1);
那麼這也就明白了為什麼HashMap的數組長度是2的整數冪。比如以初始長度為16為例，16-1 = 15，15的二進制數位00000000 00000000 00001111。可以看出一個基數二進制最後一位必然位1，當與一個hash值進行與運算時，最後一位可能是0也可能是1。但偶數與一個hash值進行與運算最後一位必然為0，造成有些位置永遠映射不上值。

對於null值的處理
hashmap是接受null值的，null值被放在數組的第一個元素當中，取出來的時候怎麼處理呢？

hashmap的工作原理？
它的裡面有一個Entry數組，在put時我們先根據key值計算出hashcode，進而計算出該元素在數組中的位置，將健值對封裝在Map.Entry對象中，然後存儲在數組中

若產生hash沖突怎麼辦？
每個數組元素的位置都是一個鏈表結構，若計算出來的hashcode相同則將元素追加到該鏈表當中，這是hashmap的處理方式

在取元素的時候，先計算key值對應的hashcode ，找到元素所在的位置，然後調用key的equals方法去遍歷鏈表，最後找到元素

還有哪些解決hash沖突的方法？
開放定址法
這種方法也稱再散列法，其基本思想是：當關鍵字key的哈希地址p=H（key）出現沖突時，以p為基礎，產生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎，產生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。
再哈希法
這種方法是同時構造多個不同的哈希函數：
Hi=RH1（key） i=1，2，…，k
當哈希地址Hi=RH1（key）發生沖突時，再計算Hi=RH2（key）……，直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間。
鏈地址法
這種方法的基本思想是將所有哈希地址為i的元素構成一個稱為同義詞鏈的單鏈表，並將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進行。鏈地址法適用於經常進行插入和刪除的情況。
建立公共溢出區
這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發生沖突的元素，一律填入溢出表。

默認的負載因子0.75
當map的大小超過當前容量的百分之75時會進行自動擴容，會將原來的對象重新放到新的數組中

rehash 的過程是什麼樣子的？
說白了就是先resize，生成一個新的Entry數組，再transfer將原數組中的值重新計算index放入新的數組中，然後改變閾值為新的長度x負載因子

如果key為null，這始終會被散列到table[0]的桶中，即使是rehash的過程也是一樣。非null的key也有可能會被散列到table[0]的位置，例如上圖中key=「f」，而且相同的key在在不同的時間可能會被散列到不同的位置，這與rehash有關。

這個過程中容易發生什麼問題呢？
容易產生條件競爭，如果在擴容的過程中put數據，會造成意想不到的結果。或者如果兩個線程都觸發了擴容，也會存在問題

這塊有沒有遇到過什麼比較好的例子？

jdk1.8以後改成了紅黑樹，為什麼？說一下紅黑樹的原理？

hashmap與hashtable的區別？
HashTable和HashMap的實現原理幾乎一樣，差別無非是
HashTable不允許key和value為null
HashTable是線程安全的
但是HashTable線程安全的策略實現代價卻太大了，簡單粗暴，get/put所有相關操作都是synchronized的，這相當於給整個哈希表加了一把大鎖。
多線程訪問時候，只要有一個線程訪問或操作該對象，那其他線程只能阻塞，相當於將所有的操作串列化，在競爭激烈的並發場景中性能就會非常差。

篇幅有限，未完待續

❷ 哈稀表是什麼東西，HashCode是什麼

哈希表是一些鍵值對的組合，如
Hashtable hs = new Hashtable();
hs.Add('1',200);
hs.Add('2',300);
hs.Add('3',400);
他的鍵是不能重復的。
我們通過它的鍵就可以得到他的值，如像，我們要得到300.
只需hs['2']就可以得到300

❸ 什麼hash code

是一種編碼方式，在Java中，每個對象都會有一個hashcode，Java可以通過這個hashcode來識別一個對象。至於hashcode的具體編碼方式，比較復雜（事實上這個編碼是可以由程序員重載的），可以參考數據結構書籍。而hashtable等結構，就是通過這個哈希實現快速查找鍵對象。這是他們的內部聯系，但一般編程時無需了解這些，只要知道hashtable實現了一種無順序的元素排列就可以了。

❹ 程序員必須掌握哪些演算法

一.基本演算法:

枚舉. (poj1753,poj2965)

貪心(poj1328,poj2109,poj2586)

遞歸和分治法.

遞推.

構造法.(poj3295)

模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.圖演算法:

圖的深度優先遍歷和廣度優先遍歷.

最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成樹演算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓撲排序 (poj1094)

二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)

最大流的增廣路演算法(KM演算法). (poj1459,poj3436)

三.數據結構.

串 (poj1035,poj3080,poj1936)

排序(快排、歸並排(與逆序數有關)、堆排) (poj2388,poj2299)

簡單並查集的應用.

哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼樹(poj3253)

堆

trie樹(靜態建樹、動態建樹) (poj2513)

四.簡單搜索

深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)

廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.動態規劃

背包問題. (poj1837,poj1276)

型如下表的簡單DP(可參考lrj的書 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學

組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.

幾何公式.

叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)

多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)

中級（校賽壓軸及省賽中等難度）:
一.基本演算法:

C++的標准模版庫的應用. (poj3096,poj3007)

較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)

二.圖演算法:

差分約束系統的建立和求解. (poj1201,poj2983)

最小費用最大流(poj2516,poj2516,poj2195)

雙連通分量(poj2942)

強連通分支及其縮點.(poj2186)

圖的割邊和割點(poj3352)

最小割模型、網路流規約(poj3308)

三.數據結構.

線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)

靜態二叉檢索樹. (poj2482,poj2352)

樹狀樹組(poj1195,poj3321)

RMQ. (poj3264,poj3368)

並查集的高級應用. (poj1703,2492)

KMP演算法. (poj1961,poj2406)

四.搜索

最優化剪枝和可行性剪枝

搜索的技巧和優化 (poj3411,poj1724)

記憶化搜索(poj3373,poj1691)

五.動態規劃

較為復雜的動態規劃(如動態規劃解特別的旅行商TSP問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)

樹型動態規劃(poj2057,poj1947,poj2486,poj3140)

六.數學

組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.
數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題. (poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩餘定理) (poj3101)
計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
隨機化演算法(poj3318,poj2454)
雜題(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.

坐標離散化.

掃描線演算法(例如求矩形的面積和周長並,常和線段樹或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多邊形的內核(半平面交)(poj3130,poj3335)

幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高級（regional中等難度）:
一.基本演算法要求:

代碼快速寫成,精簡但不失風格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

保證正確性和高效性. poj3434

二.圖演算法:

度限制最小生成樹和第K最短路. (poj1639)

最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最優比率生成樹. (poj2728)

最小樹形圖(poj3164)

次小生成樹.

無向圖、有向圖的最小環

三.數據結構.

trie圖的建立和應用. (poj2778)

LCA和RMQ問題(LCA(最近公共祖先問題) 有離線演算法(並查集+dfs) 和 在線演算法(RMQ+dfs)).(poj1330)
雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的目的). (poj2823)
左偏樹(可合並堆).

後綴樹(非常有用的數據結構,也是賽區考題的熱點).(poj3415,poj3294)
四.搜索

較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*演算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*演算法. (poj3131,poj2870,poj2286)

五.動態規劃

需要用數據結構優化的動態規劃.(poj2754,poj3378,poj3017)
四邊形不等式理論.

較難的狀態DP(poj3133)

六.數學

組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.

半平面求交(poj3384,poj2540)

可視圖的建立(poj2966)

點集最小圓覆蓋.

對踵點(poj2079)

❺ 哈希表map和table哪個性能高

list支持快速的插入和刪除，但是查找費時;
vector支持快速的查找，但是插入費時。
map查找的時間復雜度是對數的，這幾乎是最快的，hash也是對數的。
如果我自己寫，我也會用二叉檢索樹，它在大部分情況下可以保證對數復雜度，最壞情況是常數復雜度，而std::map在任何情況下都可以保證對數復雜度，原因是它保證存諸結構是完全二叉檢索樹，但這會在存諸上犧牲一些時間。
STL 中的 map 內部是平衡二叉樹，所以平衡二叉樹的性質都具備。查找數據的時間也是對數時間。 vector，在分配內存上一般要比 new 高效的多。
為什麼說 hash_map 是對數級的？在不碰撞的情況下，hash_map是所有數據結構中查找最快的，它是常數級的。
如果對問題設計了足夠好的hash演算法，保證碰撞率很低，hash_map的查找效率無可置疑。
另外，STL的map，它的查找是對數級的，是除hash_map外最高的了，你可以說「也許還有改進餘地」，但對於99.9999%的程序員，設計一個比STL map好的map，我執悲觀態度。
STL的map有平衡策略（比如紅黑樹什麼的），所以不會退化，不需要考慮數據本身的分布問題。只不過，如果數據本身是排好序的，用vector或heap會明顯的快些，因為它們的訪問比較簡單。

我想沒必要懷疑stl::map的查找效率,影響效率最主要的因素是什麼?演算法,在查找問題上,有什麼演算法比RB_tree更好嗎？至少現在還沒有。不否 認你可以通過自己寫代碼，設計一個符合你需要的BR—TREE，比stl：：map簡捷那麼一點，但最多也就每次迭代中少一行指令而已，處理十萬個數據多 執行十萬行指令，這對你重要嗎？如果你不是在設計OS像Linux，沒人會關注這十萬行指令花的時間。
rb-tree的時間花在了插入和刪除上，如果你不是對插入和刪除效率要求很高，你沒有理由不選擇基於rb-tree的stl::map。

大多數程序員寫不出比std::map更好的map，這是當然的。然而並不是std::map的所有特性都出現在我們的程序中，自己編寫的可以更適合自己的程序，的確會比std::map更快一些。

關於hash_map，它與map的實現機制是不一樣的，map內部一般用樹來實現，其查找操作是O(logN)的，這個沒有爭議，我就不多說了。
hash_map的查找，內部是通過一個從key到value的運算函數來實現的，這個函數「只接受key作為參數」，也就是說，hash_map的查找 演算法與數據量無關，所以認為它是O(1)級的。來這里的應該都是達人，可以參看《數據結構》。當然，事實總不這樣完美，再引一段前面我自已說的話，進一步 說明，以免誤會：
-----------------------------------------
在不碰撞的情況下，hash_map是所有數據結構中查找最快的，它是常數級的。
------------------------------------------
注意我的前提：「在不碰撞的情況下」，其實換句話說，就是要有足夠好的hash函數，它要能使key到value的映射足夠均勻，否則，在最壞的情況下，它的計算量就退化到O(N)級，變成和鏈表一樣。
如果說 hash_map 是所有容器中最慢的，也只能說：「最拙劣的hash函數」會使hash_map成為查找最慢的容器。但這樣說意義不大，因為，最湊巧的排列能使冒泡排序成為最快的排序演算法。
BS: "對於大型容器而言,hash_map能夠提供比map快5至10倍的元素查找速度是很常見的,尤其是在查找速度特別重要的地方.另一方面,如果hash_map選擇了病態的散列函數,他也可能比map慢得多. "
ANSIC++在1998年之後就沒再有重大改變，並且決定不再向C++標准庫中做任何重大的變更，正是這個原因，hash table(包括hash_map)並沒有被列入標准之中，雖然它理應在C++標准之中佔有一席之地。
雖然，現在的大多數編譯平台支持hash table，但從可移植性方面考慮，還是不用hash table的好。

hehe俺也來湊湊熱鬧。
1.有的時候vector可以替代map
比如key是整數，就可以以key的跨度作為長度來定義vector。
數據規模很大的時候，差異是驚人的。當然，空間浪費往往也驚人。
2.hash是很難的東西
沒有高效低碰撞的演算法，hash_xxx沒有意義。
而對不同的類型，數據集，不可能有優良的神仙演算法。必須因場合而宜。
俺有的解決方法是GP，可不是飯型，是遺傳編程，收效不錯。

你的百萬級的數據放到vector不大合適。因為vector需要連續的內存空間，顯然在初始化這個容器的時候會花費很大的容量。
使用map，你想好了要為其建立一個主鍵嗎？如果沒有這樣的需求，為什麼不考慮deque或者list？
map默認使用的是deque作為容器。其實map不是容器，拿它與容器比較意義不大。因為你可以配置它的底層容器類型。

如果內存不是考慮的問題。用vector比map好。map每插入一個數據，都要排序一次。所以速度反不及先安插所有元素，再進行排序。
用 binary_search對已序區間搜索，如果是隨機存取iterator，則是對數復雜度。可見，在不考慮內存問題的情況下，vector比map 好。

如果你需要在數據中間進行插入，list 是最好的選擇，vector 的插入效率會讓你痛苦得想死。

涉及到查找的話用map比較好，因為map的內部數據結構用rb-tree實現，而用vector你只能用線性查找，效率很低。
stl還提供了 hash容器，理論上查找是飛快~~~。做有序插入的話vector是噩夢，map則保證肯定是按key排序的，list要自己做些事情。

HASH類型的查找肯定快，是映射關系嘛，但是插入和刪除卻慢，要做移動操作, LIST類型的使鏈式關系，插入非常快，但是查找卻費時，需要遍歷~~ , 還是用LIST類型的吧，雖然查找慢點，
先快速排序，然後二分查找，效率也不低

❻ 哈希函數怎麼用pascal

暴雪公司有個經典的字元串的hash公式

先提一個簡單的問題，假如有一個龐大的字元串數組，然後給你一個單獨的字元串，讓你從這個數組中查找是否有這個字元串並找到它，你會怎麼做？

有一個方法最簡單，老老實實從頭查到尾，一個一個比較，直到找到為止，我想只要學過程序設計的人都能把這樣一個程序作出來，但要是有程序員把這樣的程序交給用戶，我只能用無語來評價，或許它真的能工作，但...也只能如此了。

最合適的演算法自然是使用HashTable（哈希表），先介紹介紹其中的基本知識，所謂Hash，一般是一個整數，通過某種演算法，可以把一個字元串"壓縮" 成一個整數，這個數稱為Hash，當然，無論如何，一個32位整數是無法對應回一個字元串的，但在程序中，兩個字元串計算出的Hash值相等的可能非常小，下面看看在MPQ中的Hash演算法

unsigned long HashString(char *lpszFileName, unsigned long dwHashType)
{
unsigned char *key = (unsigned char *)lpszFileName;
unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
int ch;

while(*key != 0)
{
ch = toupper(*key );

seed1 = cryptTable[(dwHashType < < 8) ch] ^ (seed1 seed2);
seed2 = ch seed1 seed2 (seed2 < < 5) 3;
}
return seed1;
}

Blizzard的這個演算法是非常高效的，被稱為"One-Way Hash"，舉個例子，字元串"unitneutralacritter.grp"通過這個演算法得到的結果是0xA26067F3。
是不是把第一個演算法改進一下，改成逐個比較字元串的Hash值就可以了呢，答案是，遠遠不夠，要想得到最快的演算法，就不能進行逐個的比較，通常是構造一個哈希表(Hash Table)來解決問題，哈希表是一個大數組，這個數組的容量根據程序的要求來定義，例如1024，每一個Hash值通過取模運算 (mod)對應到數組中的一個位置，這樣，只要比較這個字元串的哈希值對應的位置又沒有被佔用，就可以得到最後的結果了，想想這是什麼速度？是的，是最快的O(1)，現在仔細看看這個演算法吧

int GetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, int nTableSize)
{
int nHash = HashString(lpszString), nHashPos = nHash % nTableSize;

if (lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString))
return nHashPos;
else
return -1; //Error value
}

看到此，我想大家都在想一個很嚴重的問題："假如兩個字元串在哈希表中對應的位置相同怎麼辦？",究竟一個數組容量是有限的，這種可能性很大。解決該問題的方法很多，我首先想到的就是用"鏈表",感謝大學里學的數據結構教會了這個百試百靈的法寶，我碰到的很多演算法都可以轉化成鏈表來解決，只要在哈希表的每個入口掛一個鏈表，保存所有對應的字元串就OK了。

事情到此似乎有了完美的結局，假如是把問題獨自交給我解決，此時我可能就要開始定義數據結構然後寫代碼了。然而Blizzard的程序員使用的方法則是更精妙的方法。基本原理就是：他們在哈希表中不是用一個哈希值而是用三個哈希值來校驗字元串。

中國有句古話"再一再二不能再三再四"，看來Blizzard也深得此話的精髓，假如說兩個不同的字元串經過一個哈希演算法得到的入口點一致有可能，但用三個不同的哈希演算法算出的入口點都一致，那幾乎可以肯定是不可能的事了，這個幾率是1:18889465931478580854784，大概是10的 22.3次方分之一，對一個游戲程序來說足夠安全了。

現在再回到數據結構上，Blizzard使用的哈希表沒有使用鏈表，而採用"順延"的方式來解決問題，看看這個演算法：
int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize)
{
const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
int nHash = HashString(lpszString, HASH_OFFSET);
int nHashA = HashString(lpszString, HASH_A);
int nHashB = HashString(lpszString, HASH_B);
int nHashStart = nHash % nTableSize, nHashPos = nHashStart;

while (lpTable[nHashPos].bExists)
{
if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB)
return nHashPos;
else
nHashPos = (nHashPos 1) % nTableSize;

if (nHashPos == nHashStart)
break;
}

return -1; //Error value
}

1. 計算出字元串的三個哈希值（一個用來確定位置，另外兩個用來校驗)
2. 察看哈希表中的這個位置
3. 哈希表中這個位置為空嗎？假如為空，則肯定該字元串不存在，返回
4. 假如存在，則檢查其他兩個哈希值是否也匹配，假如匹配，則表示找到了該字元串，返回
5. 移到下一個位置，假如已經越界，則表示沒有找到，返回
6. 看看是不是又回到了原來的位置，假如是，則返回沒找到
7. 回到3

怎麼樣，很簡單的演算法吧，但確實是天才的idea, 其實最優秀的演算法往往是簡單有效的演算法。

❼ C# HashTable 明白人光臨

c#_hashtable- -

一,哈希表(Hashtable)簡述

在.NET Framework中，Hashtable是System.Collections命名空間提供的一個容器，用於處理和表現類似key/value的鍵值對，其中key通常可用來快速查找，同時key是區分大小寫；value用於存儲對應於key的值。Hashtable中key/value鍵值對均為object類型，所以Hashtable可以支持任何類型的key/value鍵值對.

二,哈希表的簡單操作

在哈希表中添加一個key/value鍵值對：HashtableObject.Add(key,value);
在哈希表中去除某個key/value鍵值對：HashtableObject.Remove(key);
從哈希表中移除所有元素： HashtableObject.Clear();
判斷哈希表是否包含特定鍵key： HashtableObject.Contains(key);
下面控制台程序將包含以上所有操作：
using System;
using System.Collections; //使用Hashtable時，必須引入這個命名空間
class hashtable
{
public static void Main()
{
Hashtable ht=new Hashtable(); //創建一個Hashtable實例
ht.Add("E","e");//添加key/value鍵值對
ht.Add("A","a");
ht.Add("C","c");
ht.Add("B","b");

string s=(string)ht["A"];
if(ht.Contains("E")) //判斷哈希表是否包含特定鍵,其返回值為true或false
Console.WriteLine("the E key:exist");
ht.Remove("C");//移除一個key/value鍵值對
Console.WriteLine(ht["A"]);//此處輸出a
ht.Clear();//移除所有元素
Console.WriteLine(ht["A"]); //此處將不會有任何輸出
}
}

三,遍歷哈希表

遍歷哈希表需要用到DictionaryEntry Object，代碼如下：
for(DictionaryEntry de in ht) //ht為一個Hashtable實例
{
Console.WriteLine(de.Key);//de.Key對應於key/value鍵值對key
Console.WriteLine(de.Value);//de.Key對應於key/value鍵值對value
}

四,對哈希表進行排序

對哈希表進行排序在這里的定義是對key/value鍵值對中的key按一定規則重新排列，但是實際上這個定義是不能實現的，因為我們無法直接在Hashtable進行對key進行重新排列，如果需要Hashtable提供某種規則的輸出，可以採用一種變通的做法：
ArrayList akeys=new ArrayList(ht.Keys); //別忘了導入System.Collections
akeys.Sort(); //按字母順序進行排序
for(string skey in akeys)
{
Console.Write(skey + ":");
Console.WriteLine(ht[skey]);//排序後輸出
}

自己看吧，程序員要學會自學，很容易的

❽ 如何正確實現Java中的hashCode方法

正確實現Java中的hashCode方法：
相等和哈希碼

相等是從一般的方面來講，哈希碼更加具有技術性。如果我們在理解方面存在困難,我們可以說,他們通過只是一個實現細節來提高了性能。
大多數的數據結構通過equals方法來判斷他們是否包含一個元素，例如：
List<String> list = Arrays.asList("a", "b", "c");
boolean contains = list.contains("b");

這個變數contains結果是true，因為,雖然」b」是不相同的實例(此外,忽略字元串駐留),但是他們是相等的。
通過比較實例的每個元素，然後將比較結果賦值給contains是比較浪費的，雖然整個類的數據結構進行了優化，能夠提升性能。
他們通過使用一種快捷的方式(減少潛在的實例相等)進行比較，從而代替通過比較實例所包含的每個元素。而快捷比較僅需要比較下面這些方面：
快捷方式比較即通過比較哈希值，它可以將一個實例用一個整數值來代替。哈希碼相同的實例不一定相等，但相等的實例一定具有有相同的哈希值。(或應該有,我們很快就會討論這個)這些數據結構經常通過這種這種技術來命名,可以通過Hash來識別他們的,其中，HashMap是其中最著名的代表。
它們通常是這樣這樣運作的
當添加一個元素,它的哈希碼是用來計算內部數組的索引(即所謂的桶)
如果是,不相等的元素有相同的哈希碼,他們最終在同一個桶上並且捆綁在一起,例如通過添加到列表。
當一個實例來進行contains操作時，它的哈希碼將用來計算桶值(索引值)，只有當對應索引值上存在元素時，才會對實例進行比較。
因此equals，hashCode是定義在Object類中。
散列法的思想
如果hashCode作為快捷方式來確定相等，那麼只有一件事我們應該關心:相等的對象應該具有相同的哈希碼，這也是為什麼如果我們重寫了equals方法後，我們必須創建一個與之匹配的hashCode實現的原因!
否則相等的對象是可能不會有相同的哈希碼的,因為它們將調用的是Object's的默認實現。
HashCode 准則
引用自官方文檔
hashCode通用約定:
* 調用運行Java應用程序中的同一對象,hashCode方法必須始終返回相同的整數。這個整數不需要在不同的Java應用程序中保持一致。
* 根據equals(Object)的方法來比較，如果兩個對象是相等的,兩個對象調用hashCode方法必須產生相同的結果。
* 根據equals(Object)的方法是比較，如果兩個對象是不相等的，那麼兩個對象調用hashCode方法並不一定產生不同的整數的結果。但是,程序員應該意識到給不相等的對象產生不同的整數結果將有可能提高哈希表的性能。
第一點反映出了相等的一致性屬性，第二個就是我們上面提出的要求。第三個闡述了一個重要的細節，我們將在稍後討論。
HashCode實現
下面是非常簡單的Person.hashCode的實現
@Override
public int hashCode() {
return Objects.hash(firstName, lastName);
}

person』s是通過多個欄位結合來計算哈希碼的。都是通過Object的hash函數來計算。
選擇欄位
但哪些欄位是相關的嗎?需求將會幫助我們回答這個問題:如果相等的對象必須具有相同的哈希碼,那麼計算哈希碼就不應包括任何不用於相等檢查的欄位。(否則兩個對象只是這些欄位不同但是仍然有可能會相等，此時他們這兩個對象哈希碼卻會不相同。)
所以用於哈希組欄位應該相等時使用的欄位的子集。默認情況下都使用相同的欄位,但有一些細節需要考慮。
一致性
首先,有一致性的要求。它應該相當嚴格。雖然它允許如果一些欄位改變對應的哈希碼發生變化(對於可變的類是不可避免的)，但是哈希數據結構並不是為這種場景准備的。
正如我們以上所見的哈希碼用於確定元素的桶。但如果hash-relevant欄位發生了改變,並不會重新計算哈希碼、也不會更新內部數組。
這意味著以後通過相等的對象，甚至同一實例進行查詢也會失敗，數據結構計算當前的哈希碼與之前存儲實例計算的哈希碼並不一致,並是錯誤的桶。
結論:最好不要使用可變欄位計算哈希碼!
性能
哈希碼最終計算的頻率與可能調用equals差不多，那麼這里將是影響性能的關鍵部分，因此考慮此部分性能也是非常有意義的。並且與equals相比，優化之後又更大的上升空間。
除非使用非常復雜的演算法或者涉及非常多的欄位，那麼計算哈希碼的運算成本是微不足道的、同樣也是不可避免的。但是也應該考慮是否需要包含所有的欄位來進行運算。集合需要特別警惕的對待。以Lists和sets為例，將會包含集合裡面的每一個元素來計算哈希碼。是否需要調用它們需要具體情況具體分析。
如果性能是至關重要的，使用Objects.hash因為需要為varargs創建一個數組也許並不是最好的選擇。但一般規則優化是適用的:不要過早地使用一個通用的散列碼演算法,也許需要放棄集合,只有優化分析顯示潛在的改進。
碰撞
總是關注性能,這個實現怎麼呢?
@Override
public int hashCode() {
return 0;
}

快是肯定的。相等的對象將具有相同的哈希碼。並且,沒有可變的欄位!
但是，我們之前說過的桶呢？！這種方式下所有的實例將會有相同的桶！這將會導致一個鏈表來包含所有的元素，這樣一來將會有非常差的性能。每次調用contains將會觸發對整個list線性掃描。
我們希望盡可能少的元素在同一個桶!一個演算法返回變化多端的哈希碼,即使對於非常相似的對象,是一個好的開始。
怎樣才能達到上面的效果部分取決於選取的欄位，我們在計算中包含更多的細節，越有可能獲取到不同的哈希碼。注意：這個與我們所說的性能是完全相反的。因此，有趣的是，使用過多或者過少的欄位都會導致糟糕的性能。
防止碰撞的另一部分是使用實際計算散列的演算法。
計算Hsah
最簡單的方法來計算一個欄位的哈希碼是通過直接調用hashCode，結合的話會自動完成。常見的演算法是首先在以任意數量的數值(通常是基本數據類型)反復進行相乘操作再與欄位哈希碼相加
int prime = 31;
int result = 1;
result = prime * result + ((firstName == null) ? 0 : firstName.hashCode());
result = prime * result + ((lastName == null) ? 0 : lastName.hashCode());
return result;

這可能導致溢出,但是不是特別有問題的,因為他們並沒有產生Java異常。
注意,即使是非常良好的的哈希演算法也可能因為輸入特定的模式的數據有導致頻繁碰撞。作為一個簡單的例子假設我們會計算點的散列通過增加他們的x和y坐標。當我們處理f(x) = -x線上的點時，線上的點都滿足：x + y == 0，將會有大量的碰撞。
但是:我們可以使用一個通用的演算法，只到分析表明並不正確，才需要對哈希演算法進行修改。
總結
我們了解到計算哈希碼就是壓縮相等的一個整數值：相等的對象必須有相同的哈希碼，而出於對性能的考慮：最好是盡可能少的不相等的對象共享相同的哈希碼。
這就意味著如果重寫了equals方法，那麼就必須重寫hashCode方法
當實現hashCode
使用與equals中使用的相同的欄位(或者equals中使用欄位的子集)
最好不要包含可變的欄位。
對集合不要考慮調用hashCode
如果沒有特殊的輸入特定的模式，盡量採用通用的哈希演算法
記住hashCode性能,所以除非分析表明必要性，否則不要浪費太多的精力。

❾ Hashtable與HashMap有什麼區別

HashTable的應用非常廣泛，HashMap是新框架中用來代替HashTable的類，也就是說建議使用HashMap，不要使用HashTable。可能你覺得HashTable很好用，為什麼不用呢？這里簡單分析他們的區別。

1.HashTable的方法是同步的，HashMap未經同步，所以在多線程場合要手動同步HashMap這個區別就像Vector和ArrayList一樣。

2.HashTable不允許null值(key和value都不可以),HashMap允許null值(key和value都可以)。

3.HashTable有一個contains(Object value)，功能和containsValue(Object value)功能一樣。

4.HashTable使用Enumeration，HashMap使用Iterator。 以上只是表面的不同，它們的實現也有很大的不同。

5.HashTable中hash數組默認大小是11，增加的方式是 old*2+1。HashMap中hash數組的默認大小是16，而且一定是2的指數。

6.哈希值的使用不同，HashTable直接使用對象的hashCode，代碼是這樣的：

int hash = key.hashCode();

int index = (hash & 0x7FFFFFFF) % tab.length;

而HashMap重新計算hash值，而且用與代替求模：

int hash = hash(k);
int i = indexFor(hash, table.length);

static int hash(Object x) {
int h = x.hashCode();
h += ~(h << 9);
h ^= (h >>> 14);
h += (h << 4);
h ^= (h >>> 10);
return h;
} static int indexFor(int h, int length) {
return h & (length-1);
}
以上只是一些比較突出的區別，當然他們的實現上還是有很多不同的，比如HashMap對null的操作。Hashtable和HashMap的區別：
1.Hashtable是Dictionary的子類，HashMap是Map介面的一個實現類；
2.Hashtable中的方法是同步的，而HashMap中的方法在預設情況下是非同步的。即是說，在多線程應用程序中，不用專門的操作就安全地可以使用Hashtable了；而對於HashMap，則需要額外的同步機制。但HashMap的同步問題可通過Collections的一個靜態方法得到解決：
Map Collections.synchronizedMap(Map m)
這個方法返回一個同步的Map，這個Map封裝了底層的HashMap的所有方法，使得底層的HashMap即使是在多線程的環境中也是安全的。
3.在HashMap中，null可以作為鍵，這樣的鍵只有一個；可以有一個或多個鍵所對應的值為null。當get()方法返回null值時，即可以表示HashMap中沒有該鍵，也可以表示該鍵所對應的值為null。因此，在HashMap中不能由get()方法來判斷HashMap中是否存在某個鍵，而應該用containsKey()方法來判斷。Hashtable繼承自Dictionary類，而HashMap是Java1.2引進的Map interface的一個實現

HashMap允許將null作為一個entry的key或者value，而Hashtable不允許

還有就是，HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。因為contains方法容易讓人引起誤解。最大的不同是，Hashtable的方法是Synchronize的，而HashMap不是，在
多個線程訪問Hashtable時，不需要自己為它的方法實現同步，而HashMap
就必須為之提供外同步。

❿ 什麼是哈希演算法

就是空間映射函數，例如，全體的長整數的取值作為一個取值空間，映射到全部的位元組整數的取值的空間，這個映射函數就是HASH函數。通常這種映射函數是從一個非常大的取值空間映射到一個非常小的取值空間，由於不是一對一的映射，HASH函數轉換後不可逆，即不可能通過逆操作和HASH值還原出原始的值，受到計算能力限制（注意，不是邏輯上不可能，前面的不可能是邏輯上的）而且也無法還原出所有可能的全部原始值。HASH函數運用在字典表等需要快速查找的數據結構中，他的計算復雜度幾乎是O(1)，不會隨著數據量增加而增加。另外一種用途就是文件簽名，文件內容很多，將文件內容通過HASH函數處理後得到一個HASH值，驗證這個文件是否被修改過，只需要把文件內容用同樣的HASH函數處理後得到HASH值再比對和文件一起傳送的HASH值即可，如不公開HASH演算法，那麼信道是無法篡改文件內容的時候篡改文件HASH值，一般應用的時候，HASH演算法是公開的，這時候會用一個非對稱加密演算法加密一下這個HASH值，這樣即便能夠計算HASH值，但沒有加密密鑰依然無法篡改加密後HASH值。這種演算法用途很廣泛，用在電子簽名中。HASH演算法也可進行破解，這種破解不是傳統意義上的解密，而是按照已有的HASH值構造出能夠計算出相同HASH值的其他原文，從而妨礙原文的不可篡改性的驗證，俗稱找碰撞。這種碰撞對現有的電子簽名危害並不嚴重，主要是要能夠構造出有意義的原文才有價值，否則就是構造了一個完全不可識別的原文罷了，接收系統要麼無法處理報錯，要麼人工處理的時候發現完全不可讀。理論上我們終於找到了在可計算時間內發現碰撞的演算法，推算了HASH演算法的逆操作的時間復雜度大概的范圍。HASH演算法的另外一個很廣泛的用途，就是很多程序員都會使用的在資料庫中保存用戶密碼的演算法，通常不會直接保存用戶密碼（這樣DBA就能看到用戶密碼啦，好危險啊），而是保存密碼的HASH值，驗證的時候，用相同的HASH函數計算用戶輸入的密碼得到計算HASH值然後比對資料庫中存儲的HASH值是否一致，從而完成驗證。由於用戶的密碼的一樣的可能性是很高的，防止DBA猜測用戶密碼，我們還會用一種俗稱「撒鹽」的過程，就是計算密碼的HASH值之前，把密碼和另外一個會比較發散的數據拼接，通常我們會用用戶創建時間的毫秒部分。這樣計算的HASH值不大會都是一樣的，會很發散。最後，作為一個老程序員，我會把用戶的HASH值保存好，然後把我自己密碼的HASH值保存到資料庫裡面，然後用我自己的密碼和其他用戶的用戶名去登錄，然後再改回來解決我看不到用戶密碼而又要「偷窺」用戶的需要。最大的好處是，資料庫泄露後，得到用戶資料庫的黑客看著一大堆HASH值會翻白眼。