Hash详解
Hash(哈希)
Hash ：散列，通過關于鍵值(key)的函數，將數據映射到內存存儲中一個位置來訪問。這個過程叫做Hash，這個映射函數稱做散列函數，存放記錄的數組稱做散列表(Hash Table),又叫哈希表。JAVA函數hashCode()即請求對象的哈希值。
?
Hash的優點
先分類再查找，通過計算縮小范圍，加快查找速度。
例：
集合：｛13,19,25,27，17｝若是采用數組或鏈表結構：
訪問其中的一個元素（如18），需要遍歷整個集合的元素，時間復雜度為O(n).而采用哈希表時:
假如散列函數為H[key] = key % 5；則集合元素對應的hash值分別為｛3,4,0,2,2｝。 訪問元素（18）只需要在Hash值為2的集合中尋找即可. 如果訪問沒有哈希沖突的元素，例如訪問（25），可以直接訪問哈希值為（0）的值。 故hash時間復雜度最差才為O(n),最優情況下只需要O(1); ?由上面的例子，我們可以想象，如果由大量的數據，采用數組或是鏈表存儲時，訪問需要遍歷，耗費的時間非常多，而Hash表通過哈希計算，可以直接定位到數據所在位置（發生哈希沖突時，哈希值相同，可以定位到較小范圍）大大加快了 查找的速度，節省了大量時間。
?
?
散列函數（Hash函數）
Hash通過Hash函數，將Key值映射為地址，Address = F[key];
常見的幾種Hash函數：直接定址法、數字分析法、平方取中法、折疊法、隨機數法、除留余數法
直接定址法：取Key或者Key的某個線性函數值為散列地址。Hash(k) = k，或者Hash(k) = a*k + b, (a\b均為常數).
如下例所示：a = 1/100,b = -5.
| 1005200 | 10047 |
| 3009800 | 30093 |
| 1506400 | 15059 |
| 7604300 | 76038 |
?
數字分析法：需要知道Key的集合，并且Key的位數比地址位數多，選擇Key數字分布均勻的位。如下：
Hash(Key) 取六位：
列數 ： 1? ?(2)? ?3? ?(4)? ?5? ?(6)? ?(7)? ?8? ?(9)? ?10? ?11? ?12? ?(13)
key1：? 5? ? 2? ? 4? ? 2? ? 7? ? 5? ? ?8? ? ?5? ? ?3? ? ?6? ? ?5? ? ?1? ? ? 3
key2：? 5? ? 4? ? 4? ? 8 ? ?7? ? 7? ? ?7? ? ?5? ? ?4? ? ?8? ? ?9 ? ? 5? ? ? 1
key3：? 3????1 ? ?5 ? ?3 ? ?7 ? ?8 ? ?5? ? ? 4 ? ? 6 ? ? 3? ? ? 5 ? ? 5 ? ? 2
key4：? 5? ? 3 ? ?6? ? 4? ? 3? ? 2? ? ? 5? ? 4 ? ? 5? ? ? 3? ? ? 2? ? 6 ? ? 4
?
其中(2、4、6、7、9、13) 這6列數字無重復，分布較均勻，取此六列作為Hash(Key)的值。
Hash(Key1) :225833
Hash(Key2):487741
Hash(Key3):138562
Hash(Key4):342554
?
平方取中法：取Key平方值的中間幾位作為Hash地址。因為在設置散列函數時不一定知道所有關鍵字，選取哪幾位不確定。一個數的平方的中間幾位和數本身的每一位都有關，這樣可以使隨機分布的Key，得到的散列地址也是隨機分布的 。如下：
| 111112113 | 12345901655324769 | 01655 |
| 010111101 | 00102234363432201 | 34363 |
| 210222134 | 44193345623513956 | 45623 |
折疊法：將關鍵字分割成位數相同的幾部分（最后一部分的位數可以不同），然后取這幾部分的疊加和（舍去進位）作為哈希地址。 當Key的位數較多的時候數字分布均勻適合采用這種方案.
具體的疊加方法有兩種，移位法和折疊法：
例子：若Key為下列數串，地址位數為7，兩種方法的Hash(key)分別如下：
Key：7982374 | 1861215 | 9892154 | 56923
| 第一段 | 7982374 | d1-dr | 7982374 | d1-dr |
| 第二段 | 1861215 | d(r+1)-d(2r) | 5121681 | d(2r)-d(r+1) |
| 第三段 | 9892154 | d(2r+1)-d(3r) | 4512989 | d(3r)-d(2r+1) |
| 第四段 | + 56923 | d(3r+1)-d(end) | + 32965 | d(end)-d(3r+1) |
| 結果： | 19792666 | ? | 17650009 | ? |
| Hash(key): | 9792666 | ? | 7650009 | ? |
隨機數法：偽隨機探測再散列
具體實現：建立一個偽隨機數發生器，Hash(Key) = random(Key). 以此偽隨機數作為哈希地址。
除留余數法：取關鍵字被某個除數 p 求余，得到的作為散列地址。
即 H(Key) = Key % p；
例子如下：
| 11076302 | 1000 | 6302 |
| 13635279 | 1000 | 5279 |
| 41076553 | 1000 | 6553 |
| 76553027 | 1000 | 3027 |
以上就是6種構造哈希函數的方法，選擇時要本著盡量減少產生沖突的原則，根據Key值的位數，分布情況，范圍大小做出更優的選擇。
?
哈希沖突
不管選用何種散列函數，不可避免的都會產生不同Key值對應同一個Hash地址的情況，這種情況叫做哈希沖突。
?
哈希沖突的處理
當沖突發生時，我們需要想辦法解決沖突，一般常用的方法有：開放定址法、單獨鏈表法、雙散列法、再散列法以及建業公共溢出取等方法。
開放定址法：
當沖突發生時，探測其他位置是否有空地址 (按一定的增量逐個的尋找空的地址)，將數據存入。根據探測時使用的增量的取法，分為：線性探測、平方探測、偽隨機探測等。
新的Hash地址函數為 Hash_new (Key) = (Hash(Key) + d i) mod m；i = 1，2...k (k<= m-1).m表示集合的元素數，i表示已經探測的次數。
-
線性探測(Linear Probing)
d i = a * i + b; a\b為常數。
相當于逐個探測地址列表，直到找到一個空置的，將數據放入。
-
平方探測(Quadratic Probing)
d i = a * i 2 (i <= m/2) m是Key集合的總數。a是常數。
探測間隔 i2 個單元的位置是否為空，如果為空，將地址存放進去。
-
偽隨機探測
d i = random(Key);
探測間隔為一個偽隨機數。
?
?
例子：
Key集合為(15,36,25,46,75)，采用除留余數法，模10 ，沖突時采用線性探測法d i = i;
如圖，15和36放入時無沖突發生，分別對應地址 5 和6 。
但是當25放入時，Hash(25) = 25%10 = 5,和Key= 15發生沖突，則令d 1 = 1,Hash(25) = (25 + 1) %10 = 6.
此時已然與Key = 36發生沖突，令d 2 = 2，Hash(25) = (25+2) %10 = 7,無沖突，放入。
此后46,75也發生沖突，解決方法同上。
?
鏈表法
將散列到同一個位置的所有元素依次存儲在單鏈表中，或者也有存儲在棧中。具體實現根據實際情況決定這些元素的數據存儲結構。
如下圖所示：
首頁Hash地址為 i 的結點，均插入到以 T[i] 為頭指針的單鏈表中。T 中各分量的初值均應為空指針。
在拉鏈法中，裝填因子 α 可以大于 1，但一般均取 α ≤ 1。
?
裝填因子(載荷因子)
散列表的載荷因子定義為：
? α = 填入表中的元素個數 / 散列表的長度.
α 是散列表裝滿程度的標志因子。由于表長是定值，α 與“填入表中的元素個數”成正比，所以，α 越大，表明填入表中的元素越多，產生沖突的可能性就越大；反之，α 越小，標明填入表中的元素越少，產生沖突的可能性就越小。實際上，散列表的平均查找長度是載荷因子α 的函數，只是不同處理沖突的方法有不同的函數。
對于開放定址法，荷載因子是特別重要因素，應嚴格限制在0.7-0.8以下。超過0.8，查表時的CPU緩存不命中（cache missing）按照指數曲線上升。因此，一些采用開放定址法的hash庫，如Java的系統庫限制了荷載因子為0.75，超過此值將resize散列表。
總結
- 上一篇： 下水盖为什么是圆的？
- 下一篇： ArcGIS两种线简化算法和建筑物综合(