hashtable演算法

1. 誰解釋下hashtable為什麼是無序的， 演算法是怎樣。。

因為hashtable是的繼承Set介面的，Set是Collection（集合）中的無序集合它的元素數耐是不可重復的，而List集合恰好相反，List是Collection中余禪的有序集合，元素豎畢塵可以重復.

2. java中的Hashtable怎麼用，請詳細舉例子說明，拜託了 謝謝

就是哈希表，下面這個示例創建了一個數字的哈希表。它將數字的名稱用作鍵： Hashtable<String, Integer> numbers = new Hashtable<String, Integer>();
numbers.put("one", 1);
numbers.put("two", 2);
numbers.put("three", 3);
要獲取一個數字，可以使用以下代碼：
Integer n = numbers.get("two");
if (n != null) {
System.out.println("two = " + n);
}

3. 哈希表、哈希演算法、一致性哈希表

    散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。它通過把關鍵碼映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數（哈希函數），存放記錄的數組叫做散列表。

  優點：

        哈希表可以提供快速的操作。

缺點：

        哈希表通常是基於數組的，數組創建後難於擴展。

        也沒有一種簡便的方法可以以任何一種順序〔例如從小到大）遍歷表中的數據項 。

    綜上， 如果不需要有序遍歷數據，井且可以提前預測數據量的大小。那麼哈希表在速度和易用性方面是無與倫比的。

        1. 使用哈希函數將被查找的鍵轉換為數組的索引。

        2. 處理哈希碰撞沖突。

    若關鍵字為 k ，則其值存放在 f(k) 的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關系 f 為散列函數，按這個思想建立的表為散列表。

    若對於關鍵字集合中的任一個關鍵字，經散列函數映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數為 均勻散列函數 (Uniform Hash function)，這就是使關鍵字經過散列函數得到一個"隨機的地址"，從而減少碰撞。

散列函數能使對一個數據序列的訪問過程更加迅速有效，通過散列函數，數據元素將被更快地定位。

一個好的散列函數一般應該考慮下列因素 ：

    1.計算簡單，以便提高轉換速度。

    2.關鍵詞對應的地址空間分布均勻，以盡量減少沖突。

1.   直接定址法

    取關鍵字或者關鍵字的某個線性函數值作為哈希地址,即H(Key)=Key或者H(Key)=a*Key+b(a,b為整數),這種散列函數也叫做自身函數.如果H(Key)的哈希地址上已經有值了,那麼就往下一個位置找,直到找到H(Key)的位置沒有值了就把元素放進去。

2.   數字分析法

    數字分析法就是找出數字的規律，盡可能利用這些數據來構造沖突幾率較低的散列地址。

3.   平方取中法

    取關鍵字平方後的中間幾位作為散列地址。這種方法的原理是通過取平方擴大差別，平方值的中間幾位和這個數的每一位都相關，則對不同的關鍵字得到的哈希函數值不易產生沖突，由此產生的哈希地址也較為均勻。該方法適用於關鍵字中的每一位都有某些數字重復出現頻度很高的現象。

4.   折疊法

    折疊法是將關鍵字分割成位數相同的幾部分,最後一部分位數可以不同,然後取這幾部分的疊加和(注意:疊加和時去除進位)作為散列地址。

    數位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割後的每一部分的最低位對齊,然後相加;間界疊加是從一端向另一端沿分割界來回折疊,然後對齊相加。

    該方法適用於關鍵字特別多的情況。

5.   隨機數法

    選擇一個隨機數,作為散列地址,通常用於關鍵字長度不同的場合。

6.   除留余數法

    取關鍵字被某個不大於散列表表長m的數p除後所得的余數為散列地址.即H(Key)=Key MOD p,p<=m.不僅可以對關鍵字直接取模,也可在折疊、平方取中等運算之後取模。對p的選擇很重要，一般取素數或m，若p選得不好，則很容易產生沖突。

    對不同的關鍵字可能得到同一散列地址，即 k1≠k2 ，而 f(k1)=f(k2) ，這種現象稱為碰撞(英語:Collision)。具有相同函數值的關鍵字對該散列函數來說稱做同義詞。

    通過構造性能良好的散列函數，可以減少沖突，但一般不可能完全避免沖突，因此解決沖突是哈希法的另一個關鍵問題。 創建哈希表和查找哈希表都會遇到沖突，兩種情況下解決沖突的方法應該一致。

下面以創建哈希表為例，說明解決沖突的方法。

1.開放定址法

    這種方法也稱再散列法，其基本思想是：當關鍵字key的哈希地址p=H(key)出現沖突時，以p為基礎，產生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎，產生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。這種方法有一個通用的再散列函數形式：Hi=(H(key)+di)%m   i=1，2，…，m-1,其中H（key）為哈希函數，m 為表長，di稱為增量序列，i為碰撞次數。增量序列的取值方式不同，相應的再散列方式也不同。增量序列主要有以下幾種：

    (1) 線性探測再散列

        di=1，2，3，…，m-1

        這種方法的特點是：沖突發生時，順序查看錶中下一單元，直到找出一個空單元或查遍全表。

    (2)二次探測再散列

        di=12，-12，22，-22，…，k2，-k2( k<=m/2 )

        這種方法的特點是：沖突發生時，在表的左右進行跳躍式探測，比較靈活。

    (3)偽隨機探測再散列

        di=偽隨機數序列。

    線性探測再散列的 優點 是：只要哈希表不滿，就一定能找到一個不沖突的哈希地址，而二次探測再散列和偽隨機探測再散列則不一定。線性探測再散列容易產生「二次聚集」，即在處理同義詞的沖突時又導致非同義詞的沖突。

    其實除了上面的幾種方法，開放定址法還有很多變種，不過都是對di有不同的表示方法。（如雙散列探測法：di=i*h2(k)）

2.再哈希法

    這種方法是同時構造多個不同的哈希函數：Hi=RHi（key），i=1，2,3，…,n。

    當哈希地址H1=RH1（key）發生沖突時，再計算H2=RH2（key）……，直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間。

 3.鏈地址法(拉鏈法)

    這種方法的基本思想是將所有哈希地址相同的元素構成一個稱為同義詞鏈的單鏈表，並將單鏈表的頭指針存在哈希表（數組）中，因而查找、插入和刪除主要在同義詞鏈中進行。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數組T[0..m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應為空指針。鏈地址法適用於經常進行插入和刪除的情況。

     拉鏈法的優點

        與開放定址法相比，拉鏈法有如下幾個優點：

            (1)拉鏈法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短；

            (2)由於拉鏈法中各鏈表上的結點空間是動態申請的，故它更適合於造表前無法確定表長的情況；

            (3)開放定址法為減少沖突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而拉鏈法中理論上可取α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節省空間；（散列表的裝填因子定義為：α= 填入表中的元素個數 / 散列表的長度）

註：HashMap默認裝填因子是0.75。

            (4)在用拉鏈法構造的散列表中，刪除結點的操作易於實現。只要簡單地刪去鏈表上相應的結點即可。而對開放定址法構造的散列表，刪除結點不能簡單地將被刪結點的空間置為空，否則將截斷在它之後填入散列表的同義詞結點的查找路徑。這是因為各種開放定址法中，空地址單元都被理解沒有查找到元素。 因此在用開放定址法處理沖突的散列表上執行刪除操作，只能在被刪結點上做刪除標記，而不能真正刪除結點。

     拉鏈法的缺點

        拉鏈法的缺點是：指針需要額外的空間，故當結點規模較小時，開放定址法較為節省空間，此時將節省的指針空間用來擴大散列表的規模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。

4、建立公共溢出區

    這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發生沖突的元素，一律填入溢出表(在這個方法裡面是把元素分開兩個表來存儲)。

    散列表的查找過程基本上和造表過程相同。一些關鍵碼可通過散列函數轉換的地址直接找到，另一些關鍵碼在散列函數得到的地址上產生了沖突，需要按處理沖突的方法進行查找。在介紹的三種處理沖突的方法中，產生沖突後的查找仍然是給定值與關鍵碼進行比較的過程。所以，對散列表查找效率的量度，依然用平均查找長度來衡量。

    查找過程中，關鍵碼的比較次數，取決於產生沖突的多少，產生的沖突少，查找效率就高，產生的沖突多，查找效率就低。因此，影響產生沖突多少的因素，也就是影響查找效率的因素。

影響產生沖突多少有以下三個因素:

    1. 散列函數是否均勻;

    2. 處理沖突的方法;

    3. 散列表的裝填因子。

     散列表的裝填因子

        定義為:α= 填入表中的元素個數 / 散列表的長度

        α是散列表裝滿程度的標志因子。由於表長是定值，α與"填入表中的元素個數"成正比，所以，α越大，填入表中的元素較多，產生沖突的可能性就越大;α越小，填入表中的元素較少，產生沖突的可能性就越小。

        實際上，散列表的平均查找長度是裝填因子α的函數，只是不同處理沖突的方法有不同的函數。

    這個HASH演算法不是大學里數據結構課里那個HASH表的演算法。這里的HASH演算法是密碼學的基礎，了解了hash基本定義，就不能不提到一些著名的hash演算法，MD5 和 SHA-1 可以說是目前應用最廣泛的Hash演算法，而它們都是以 MD4 為基礎設計的。

Hash演算法在信息安全方面的應用主要體現在以下的3個方面:

     ⑴  文件校驗

        我們比較熟悉的校驗演算法有奇偶校驗和CRC校驗，這2種校驗並沒有抗 數據篡改 的能力，它們一定程度上能檢測出數據傳輸中的信道誤碼，但卻不能防止對數據的惡意破壞。

        MD5 Hash演算法的"數字指紋"特性，使它成為目前應用最廣泛的一種文件完整性 校驗和 (Checksum)演算法，不少Unix系統有提供計算md5 checksum的命令。

     ⑵  數字簽名

        Hash 演算法也是現代密碼體系中的一個重要組成部分。由於非對稱演算法的運算速度較慢，所以在 數字簽名 協議中，單向散列函數扮演了一個重要的角色。對 Hash 值，又稱"數字摘要"進行數字簽名，在統計上可以認為與對文件本身進行數字簽名是等效的。而且這樣的協議還有其他的優點。

     ⑶ 鑒權協議

        如下的鑒權協議又被稱作挑戰--認證模式:在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡單而安全的方法。

    一致性哈希表簡稱DHT，主要應用於分布式緩存中，可以用來解決分布式存儲結構下動態增加和刪除節點所帶來的問題。比如，一個分布式的存儲系統，要將數據存儲到具體的節點上，如果採用普通的hash方法，將數據映射到具體的節點上，如key%N（key是數據的key，N是機器節點數），如果有一個機器加入或退出這個集群，則所有的數據映射都無效了，如果是持久化存儲則要做數據遷移，如果是分布式緩存，則其他緩存就失效了。

判定哈希演算法好壞的四個定義 ：

    1、平衡性(Balance)：平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。

    2、單調性(Monotonicity)：單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到原有的或者新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。

    3、分散性(Spread)：在分布式環境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。當終端希望通過哈希過程將內容映射到緩沖上時，由於不同終端所見的緩沖范圍有可能不同，從而導致哈希的結果不一致，最終的結果是相同的內容被不同的終端映射到不同的緩沖區中。這種情況顯然是應該避免的，因為它導致相同內容被存儲到不同緩沖中去，降低了系統存儲的效率。 分散性的定義就是上述情況發生的嚴重程度。好的哈希演算法應能夠盡量避免不一致的情況發生，也就是盡量降低分散性。

    4、負載(Load)：負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內容映射到不同的緩沖區中，那麼對於一個特定的緩沖區而言，也可能被不同的用戶映射為不同的內容。與分散性一樣，這種情況也是應當避免的， 因此好的哈希演算法應能夠盡量降低緩沖的負荷。

    在分布式集群中，對機器的添加刪除，或者機器故障後自動脫離集群這些操作是分布式集群管理最基本的功能。如果採用常用的hash取模演算法，那麼在有機器添加或者刪除後，很多原有的數據就無法找到了，這樣嚴重的違反了單調性原則。接下來主要說明一下一致性哈希演算法是如何設計的。

以SpyMemcached的ketama演算法來說，思路是這樣的：

把數據用hash函數，映射到一個很大的空間里，如圖所示。數據的存儲時，先得到一個hash值，對應到這個環中的每個位置，如k1對應到了圖中所示的位置，然後沿順時針找到一個機器節點B，將k1存儲到B這個節點中。

如果B節點宕機了，則B上的數據就會落到C節點上，如下圖所示：

這樣，只會影響C節點，對其他的節點A，D的數據不會造成影響。然而，這又會造成一個「雪崩」的情況，即C節點由於承擔了B節點的數據，所以C節點的負載會變高，C節點很容易也宕機，這樣依次下去，這樣造成整個集群都掛了。

為此，引入了「虛擬節點」的概念：即把想像在這個環上有很多「虛擬節點」，數據的存儲是沿著環的順時針方向找一個虛擬節點，每個虛擬節點都會關聯到一個真實節點，如下圖所使用：

圖中的A1、A2、B1、B2、C1、C2、D1、D2都是虛擬節點，機器A負載存儲A1、A2的數據，機器B負載存儲B1、B2的數據，機器C負載存儲C1、C2的數據。由於這些虛擬節點數量很多，均勻分布，因此不會造成「雪崩」現象。

4. 哈希演算法從原理到實戰

引言 

       將任意長度的二進制字元串映射為定長二進制字元串的映射規則我們稱為散列（hash）演算法，又叫哈希（hash）演算法，而通過原始數據映射之後得到的二進制值稱為哈希值。哈希表（hash表）結構是哈希演算法的一種應用，也叫散列表。用的是數組支持按照下標隨機訪問數據的特性擴展、演化而來。可以說沒有數組就沒有散列表。

哈希演算法主要特點

        從哈希值不能反向推導原始數據，也叫單向哈希。

        對輸入數據敏感，哪怕只改了一個Bit，最後得到的哈希值也大不相同。

        散列沖突的概率要小。

        哈希演算法執行效率要高，散列結果要盡量均衡。

哈希演算法的核心應用

         安全加密 ：對於敏感數據比如密碼欄位進行MD5或SHA加密傳輸。

         唯一標識 ：比如圖片識別，可針對圖像二進制流進行摘要後MD5，得到的哈希值作為圖片唯一標識。

         散列函數 :是構造散列表的關鍵。它直接決定了散列沖突的概率和散列表的性質。不過相對哈希演算法的其他方面應用，散列函數對散列沖突要求較低，出現沖突時可以通過開放定址法或鏈表法解決沖突。對散列值是否能夠反向解密要求也不高。反而更加關注的是散列的均勻性，即是否散列值均勻落入槽中以及散列函數執行的快慢也會影響散列表性能。所以散列函數一般比較簡單，追求均勻和高效。

        *負載均衡 ：常用的負載均衡演算法有很多，比如輪詢、隨機、加權輪詢。如何實現一個會話粘滯的負載均衡演算法呢？可以通過哈希演算法，對客戶端IP地址或會話SessionID計算哈希值，將取得的哈希值與伺服器列表大小進行取模運算，最終得到應該被路由到的伺服器編號。這樣就可以把同一IP的客戶端請求發到同一個後端伺服器上。

        *數據分片 ：比如統計1T的日誌文件中「搜索關鍵詞」出現次數該如何解決？我們可以先對日誌進行分片，然後採用多機處理，來提高處理速度。從搜索的日誌中依次讀取搜索關鍵詞，並通過哈希函數計算哈希值，然後再跟n(機器數)取模，最終得到的值就是應該被分到的機器編號。這樣相同哈希值的關鍵詞就被分到同一台機器進行處理。每台機器分別計算關鍵詞出現的次數，再進行合並就是最終結果。這也是MapRece的基本思想。再比如圖片識別應用中給每個圖片的摘要信息取唯一標識然後構建散列表，如果圖庫中有大量圖片，單機的hash表會過大，超過單機內存容量。這時也可以使用分片思想，准備n台機器，每台機器負責散列表的一部分數據。每次從圖庫取一個圖片，計算唯一標識，然後與機器個數n求余取模，得到的值就是被分配到的機器編號，然後將這個唯一標識和圖片路徑發往對應機器構建散列表。當進行圖片查找時，使用相同的哈希函數對圖片摘要信息取唯一標識並對n求余取模操作後，得到的值k，就是當前圖片所存儲的機器編號，在該機器的散列表中查找該圖片即可。實際上海量數據的處理問題，都可以藉助這種數據分片思想，突破單機內存、CPU等資源限制。

        *分布式存儲 ：一致性哈希演算法解決緩存等分布式系統的擴容、縮容導致大量數據搬移難題。

         JDK集合工具實現 ：HashMap、 LinkedHashMap、ConcurrentHashMap、TreeMap等。Map實現類源碼分析，詳見  https://www.jianshu.com/p/602324fa59ac

總結

        本文從哈希演算法的原理及特點，總結了哈希演算法的常見應用場景。

        其中基於余數思想和同餘定理實現的哈希演算法（除留取余法），廣泛應用在分布式場景中（散列函數、數據分片、負載均衡）。由於組合數學中的「鴿巢」原理，理論上不存在完全沒有沖突的哈希演算法。（PS:「鴿巢」原理是指有限的槽位，放多於槽位數的鴿子時，勢必有不同的鴿子落在同一槽內，即沖突發生。同餘定理：如果a和b對x取余數操作時a%x = b%x，則a和b同餘）

        構造哈希函數的常規方法有：數據分析法、直接定址法、除留取余法、折疊法、隨機法、平方取中法等  。

        常規的解決哈希沖突方法有開放定址法（線性探測、再哈希）和鏈表法。JDK中的HashMap和LinkedHashMap均是採用鏈表法解決哈希沖突的。鏈表法適合大數據量的哈希沖突解決，可以使用動態數據結構（比如：跳錶、紅黑樹等）代替鏈表，防止鏈表時間復雜度過度退化導致性能下降；反之開放定址法適合少量數據的哈希沖突解決。

5. 哈希表與哈希（Hash）演算法

根據設定的 哈希函數H（key） 和 處理沖突的方法 將一組關鍵字影像到一個有限的連續的地址集（區間）上，並以關鍵字在地址集中的「像」作為記錄在表中的存儲位置，這種表便成為 哈希表 ，這一映像過程稱為哈希造表或 散列 ，所得存儲位置稱 哈希地址 或 散列地址 。

上面所提到的 哈希函數 是指：有一個對應關系 f ，使得每個關鍵字和結構中一個唯一的存儲位置相對應，這樣在查找時，我們不需要像傳統的爛碼查找演算法那樣進行比較，而是根據這個對應關系 f 找到給定值K的像 f（K） 。

哈希函數也可叫哈希演算法，它可以用於檢驗信息是否相同（ 文件校驗 ），或兆歷褲者檢驗信息的擁有者是否真實（ 數字簽名 ）。

下面分別就哈希函數和族簡處理沖突的方法進行討論;

構造哈希函數的方法有很多。在介紹各種方法前，首先需要明確什麼是「好」 的哈希演算法。若對於關鍵字集合中的任一個關鍵字，經哈希函數映像到地址集合中任何一個地址的概率是相等的，則稱此類哈希函數是 均勻的 （Uniform）哈希函數。換句話說，就是使關鍵字經過哈希函數得到一個「隨機的地址」，以便使一組關鍵字的哈希地址均勻分布在整個地址區間中，從而減少沖突。
常用的構造哈希函數的方法有：

理論研究表明， 除留余數法的模 p 取不大於表長且最接近表長 m 的素數效果最好，且 p 最好取1.1 ⁿ ~ 1.7 ⁿ 之間的一個素數（n為存在的數據元素個數） 。

以上便是常用的6種構造哈希函數的方法，實際工作中需視不同的情況採用採用不同的哈希函數，通常考慮的因素有：

前面有提到過 均勻的哈希函數可以減少沖突，但不能避免 ，因此，如何處理沖突是哈希造表不可缺少的另一方面。

通常用的處理沖突的方法有下列幾種：

在哈希表上進行查找的過程和哈希建表的過程基本一致。 給定K值，根據建表時設定的哈希函數求得哈希地址，若表中此位置上沒有記錄，則查找不成功；否則比較關鍵字，若和給定值相等，則查找成功；否則根據造表時設定的處理沖突的方案找「下一地址」 ，直到找到為止。

6. 哈希演算法和哈希表的區別

哈希演算法將任意長度的二進制值映射為較短的固定長度的二進制值，這個小的二進制值稱為哈希值。哈希函數實現了哈希演算法,返回值就是 hash code。哈希表是一個數據結構,內部實現靠哈希函數。

7. 哈希表演算法的哈希表的優缺點

哈希表是種數據結構，它可以提供快速的插入操作和查找操作。第一次接觸哈希表時，它的優點多得讓人難以置信。不論哈希表中有多少數據，插入和刪除（有時包括側除）只需要接近常量的時間即0(1）的時間級。實際上，這只需要幾條機器指令。
對哈希表的使用者一一人來說，這是一瞬間的事。哈希表運算得非常快，在計算機程序中，如果需要在一秒種內查找上千條記錄通常使用哈希表（例如拼寫檢查器)哈希表的速度明顯比樹快，樹的操作通常需要O(N)的時間級。哈希表不僅速度快，編程實現也相對容易。
哈希表也有一些缺點它是基於數組的，數組創建後難於擴展某些哈希表被基本填滿時，性能下降得非常嚴重，所以程序雖必須要清楚表中將要存儲多少數據（或者准備好定期地把數據轉移到更大的哈希表中，這是個費時的過程）。
而且，也沒有一種簡便的方法可以以任何一種順序〔例如從小到大〕遍歷表中數據項。如果需要這種能力，就只能選擇其他數據結構。
然而如果不需要有序遍歷數據，並且可以提前預測數據量的大小。那麼哈希表在速度和易用性方面是無與倫比的。

8. 哈希表—什麼是哈希表

哈希表是一種數據結構～

哈希表可以存儲各種類型的數據，當我們從哈希表中查找所需要的數據時，理想情況是不經過任何比較，一次存取便能得到所查記錄， 那就必須在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系 f，使每個關鍵字和結構中一個唯一的存儲位置相對應。 (關鍵字就是所要存儲的數據，存儲位置相當於數組的索引)

當然，可以把哈希表理解為一個數組，每個索引對應一個存儲位置，哈希表的索引並不像普通數組的索引那樣，從0到length-1，而是由關鍵字(數據本身)通過哈希函數得到

eg1. 將26個小寫字母存儲到數組  int [26] a。

a對應a[0]，b對應a[1]，c對應a[3]……以此類推。

那麼，數組 int [26] a 就是一個哈希表！

例1中，關鍵字(小寫字母)是如何得到自己對應的索引(存儲位置)的呢？

關鍵字的ASCII值減去a的ASCII值！

上面說過，關鍵字通過哈希函數得到索引，所以，f(ch)就是本例題的哈希函數。

這樣，我們就在關鍵字和數字(存儲位置)之間建立了一個確定的對應關系f。

關鍵字與數字是皮棚卜一一對應的，由於數組本身支持隨機訪問，所以，當查找關鍵字時，只需要O(1)的查找操作，也就是實現了不經過任何比較，一次便能得到所查記錄。

哈希表中 哈希函數的設計 是相當重要的，這也是建哈燃穗希表過程中的關鍵問題之一。

假如，我們所要存儲的數據其關鍵字是一個人的身份證號(18位數字)，這個時候我們該怎麼計算關鍵字對應的索引呢？

比如一個人的身份證號是 411697199702076425，我們很難像例1那樣直接讓關鍵字與數字建立一一對應的關系，並且保證數字適合作為數組的索引。

在這種情況下，通過哈希函數計算出的索引，即使關鍵字不同，索引也會有可能相同。這就是 哈希沖突

當索引相同時，我們該怎麼存儲數據呢？如何解決哈希沖突，是我們建哈希表的另一個和含關鍵問題。

哈希表充分體現了空間換時間這種經典的演算法思想。

關鍵字是大整數時，比如上面我們舉的身份證號例子，411697199702076425

假如我們能開辟一個 999999999999999999 大的空間，這樣就能直接把身份證號作為關鍵字存儲到數組中，這樣可以用O(1)時間完成各項操作

假如我們只有 1 的空間，我們需要把所有信息存儲到這個空間中(也就是所有數據都會產生哈希沖突)，我們只能用O(n)時間完成各項操作

事實上，我們不可能開辟一個如此大的空間，也不可會開辟如此小的空間

無限空間時，時間為O(1)

1的空間時，時間為O(n)

而哈希表就是在二者之間產生一個平衡，即 空間和時間的平衡 。

1.哈希函數的設計

2.解決哈希沖突

3.哈希表實現時間和空間的平衡

後續會詳細說明這三個關鍵問題～

9. 數據結構與演算法-基礎（十八）哈希表

上期使用 紅黑樹 實現映射結構，這樣的結構滿足 Key 必須具備可比性，元素有順序地分布 這兩個特點。在實際的應用場景中，存在結構中的 元素是不需要有序的，並且 Key 也不具備可比較性 ，哈希表完全滿足這樣的應用場景。

比如設計一個公司的通訊錄，存放所有員工的通訊信息，就可以拿手機號作為 index，員工的名稱、職位等作為 value。用哈希表的方式可以將添加、刪除和搜索的時間復雜度控制在 O(1)。

這時創建一個數組，手機號作為 index，然後存放 value。這樣能將復雜度控制在 O(1)，但是這種 空間換時間 的方式也造成了一些其他問題，比如空間復雜度大（需要更多的空間），空間使用率極其低，非常浪費內存空間。

哈希表 就是空間換時間的處理方式，但是做了優化，在空間和時間兩個緯度中達到適當的平衡。

哈希表也叫做散列表，整體結構就是一個數組 ，哈希表會將 key 用哈希函數處理之後返回 hash（哈希值），hash 就是哈希表中的 index這樣的處理方式就可以滿足搜索時間是 O(1)，這樣的處理方式就可以滿足搜索時間是 O(1)。因為哈希表中的 key 可能不具備可比較性，所以要做哈希處理。

在執行哈希函數之後返回的 hash，可能會出現相同的情況 ，這樣的情況就是 哈希沖突 。解決哈希沖突常見的方法有這三種：

JDK1.8 解決哈希沖突的方式就是使用鏈地址法，其中的鏈表就是通過鏈表+紅黑樹的組合來實現 。比如當哈希表中的容量大於等於 64，並且單向鏈表的節點數大於 8 時，轉換為紅黑樹，不滿足這個條件時就使用單向鏈表。

哈希函數 是生成哈希值的實現方法，哈希函數的實現步驟大致分為兩步：

hash_code 是生成哈希值的函數，也可以直接用 JAVA 中的標准函數 hashCode() 。

這里可以用 & 位運算替換 % 運算，來提高效率。因為 & 位運算是二進制運算，所以在設計數組的時候，需要將數組的長度設計為 2 的冪次方。

一個良好的哈希函數，可以讓生成的哈希值分布更加均勻，減少哈希沖突的次數，最終可以提升哈希表的性能。

Key 的常見類型可能有證書、浮點數、字元串或者自定義對象，不同的類型生成哈希值的方式也會不一樣，但是目標是一致的，就是 盡量讓每個 Key 的哈希值唯一，盡量讓 Key 中的所有信息參與運算 。

比如在 Java 中， Long 的哈希值實現如下代碼：

這里的 >>> 和 ^ 就是將高 32 bit 和低 32 bit 混合計算出 32 bit 的哈希值。

在計算字元串的哈希值時，可以將字元串拆解成若干個字元，比如 jack，將它拆解成 j、a、c、k（字元的本質就是一個整數，所以 jack 的哈希值可以表示為 j * n3 + a * n2 + c * n1 + k * n0，表達式也可以寫成 [(j * n + a) * n + c] * n + k，代碼實現如下：

看上面代碼時，可以發現，表達式中的 n 使用的是 31 這個數字，那麼為什麼用 31 呢？

因為 31 不僅符合 22 - 1 , 而且它還是個奇素數（既是技術，又是素數，還是質數），素數和其他數相乘的結果比其他方式更容易產生唯一性，減少哈希沖突。

JDK 中，乘數 n 也是用 31，31 也是經過觀測分布結果後的選擇，關於 31 的變體可以有以下幾種：

31 * i = (25 - 1) * i = i * 25 - i = (i << 5) - i