文章目錄
- 引導案例
-
- 案例一
- 案例二
- hash表（散清單）
- 哈希函數(散列函數）
- 哈希碰撞( 哈希沖突 )
- 如何解決hash沖突（hash碰撞）
-
- 開放尋址
-
- 線性探測(LP)
- 二次探測 （平方探測 QP）
- 再哈希法（DH）
- 鍊位址法
- 算法可視化網站
問題: 有n個(1<n<10)自然數 ，每個自然數的範圍在1~100之間，用最快的速度來判斷某個數是否在這n個數中，不能使用已經封裝好的類。
假設有5個自然數：
4 ，50， 87，99，100
判斷100， 在不在這5個數中
分析：
自然 —> 非負整數 ( 0 , 1 , 2 , 3 , 4 , … )
可以想到的幾種方式 ： 排序（沒必要）周遊、 數組（利用數組下标）…
周遊： 循環，判斷每個數是否和目标數值相等，相等則退出循環，存在。
數組下标： 初始化一個能夠容納最大資料的int數組，數組中的值預設為0 ，然後把出現的這n個數的下标置為1，判斷某個數是否存在—>直接判斷這個數在數組中對應的下标是0還是1即可，1則存在，0 則不存在，那麼查詢的時間複雜度 O(1)，也不需要周遊。
很顯然周遊的效率不如利用數組下标
解答：
拿上面的例子為例，
假設有5個自然數： 4 ，50， 87，99，100
判斷100， 在不在這5個數中
初始化一個長度為100的int數組 (每個自然數的範圍是1~100，100個數）
int[] arr = new int[100];
a[4]-->1
a[50]-->1
a[87]-->1
a[99]-->1
a[100]-->1
其餘的數組中的值為預設值 0
判斷a[100]是否存在，直接看下 a[100] 為 0 還是 1 即可。 （不用較真，數組下标從0開始，檢視100，應該檢視a[99], 重要的是思路）
思考： 案例一中的這種方式有什麼弊端嗎？
先來看下另外一個例子
問題: 有n個(1<n<10)自然數 ，每個自然數的範圍在0~10000000000（100億）之間，用最快的速度來判斷某個數是否在這n個數中，不能使用已經封裝好的類。
假設這5個數為 999999,999999999,9999999999,9989898989
這個時候 ，你初始化一個 100億的一個數組嗎? 就為了存上面的5個數，顯然是不合理的。
int 最多存21億多，這100億肯定存不下，當然了 你換成可以long型 , 但是這個空間浪費的是不是太多了… 肯定接收不了。
資料太大存不下，并且空間浪費太多 ，那該如何解決呢？ --------------> hash 就要登場了。
hash表（散清單）
散清單 , 英文 hash table .
hash table 就是利用數組支援按照下标随機通路資料的特性，對數組的一種擴充，從數組演化而來。 是以hash table 本質上就是一個數組。
<font color=red我們剛才的例子，已經用到了散列的思想 。 N個自然數，并且與數組的下标形成一一的映射，是以利用數組支援下标随機通路特性，**查詢時間複雜度是O(1)**這一個特性，就可以實作快速哦按段元素是否存在序列當中。
哈希函數(散列函數）
上面的例子我們也看到了，資料量巨大的時候，數組是放不下的，那就需要一種壓縮方法，把這種資料壓縮到一個可接收的範圍内。
比如把 0~199 （largeNum）的壓縮為 0到9(smallNum) ， 0到9 有10個數，是以smallRange = 10 ，
用個公式來表示的話就是
smallNum = largeNum % smallRange
上面這種取餘的操作，就可以了解為是hash化,是hash函數的一種。
細看一下
假設N=10 （壓到0到9的值）， 有下面幾個數
11 ， 52 ，33 ，64 ，75 ，26 ，199…
對應上面的公式的話， smallRange = 10 ， 上面的這幾個數字就是largeNum
我們來通過取餘來計算下smallRange
11 % 10 = 1，
52 % 10 = 2，
33 % 10 = 3 ，
64 % 10 = 4，
75 % 10 = 5，
26% 10 = 6 ，
199 % 10 = 9
我們是不是可以把 0 到 9 了解為數組下标 ？ 對的。
11 % 10 = 1， =========> a[1]======> 代表 11
52 % 10 = 2， =========> a[2]======> 代表 52
33 % 10 = 3 ， =========> a[3]======> 代表 33
64 % 10 = 4， =========> a[4]======> 代表 64
75 % 10 = 5， =========> a[5]======> 代表 75
26% 10 = 6 ， =========> a[6]======> 代表 26
199 % 10 = 9 =========> a[9]======> 代表 199
判斷 199 是不是在 這幾個數中，是不是就可以這樣操作？
199 % 10 = 9 =======> a[9] ===⇒ 比對下a[9] = 199 ？ =====> 等于則存在，不等于則不存在。
哈希碰撞( 哈希沖突 )
到了這裡，你可能已經發現問題了，這組資料當然是故意制作的，
11 ， 52 ，33 ，64 ，75 ，26 ，199......
數組下标沒有沖突的…
如果是下面這組數字呢？
11 ， 52 ，22 ，42，75 ，26 ，199......
hash化處理一下如下：
11 % 10 = 1，
52 % 10 = 2，
22 % 10 = 2 ，
42 % 10 = 2，
75 % 10 = 5，
26% 10 = 6 ，
199 % 10 = 9
可以知道 52 ， 22 ， 42 取餘後 都是 2 ，那問題來了 a[2] 有多個值了，到底代表哪一個呢？
這種情況就稱之為 哈希碰撞 或者 哈希沖突
核心思想： 在開放尋址法中，如果資料不能直接放在由hash函數計算出來的數組下标所指的單元時，就要尋找數組的其他位置。
根據在找下一個空白單元時使用的方法不同，又可以分為
- 線性探
- 二次探
- 二次哈希
LP : LINEAR PROBING
我們以線性探測為例來看下 是如何實作開放尋址的
線性探測：線上性探測中，線性的查找空白單元，比如 數組下标 666 為要插入資料的位置，如果它已經被占用了，則繼續探測667，依次類推，直到找到一個空位，這個就叫線性探測，因為它沿着數組的下标一步步的尋找空白單元
線性探測 示意圖：
QP：QUADRATIC PROBING
線性探測會發生聚集，如果hash化後的資料落到了聚集範圍内的資料項，就要一步步的移動。
已填入hash表中的資料和表長的比率叫做裝填因子，比如1萬個單元的哈希表填入了3334個資料，那麼它的裝填因子就是1/3.
當裝填因子不是很大的時候，聚集分布的比較連貫。 hash表的某部分可能包含大量的聚集，而另一部分還很稀疏。 聚集降低了hash表的性能。
二次探測主要是為了防止聚集的産生。核心思想：探測相隔較遠的單元，而不是和原始位置相鄰的單元。
步驟是步數的平方
舉個例子：
線上性探測中，如果哈希函數計算出來的原始下标是x, 線性探測就是 x+1 , x+2 ,x+3 ,x+4,x+5…依次類推。
而在二次探測中，探測的過程則是 x+1 , x+4 ,x+9 x+16,x+25… 到原始位置的距離是步數的平方：
x+1^2
x+2^2
x+3^2
x+4^2
x+5^2
…
當二次探測的搜尋邊長的時候，它好像變得很絕望。
- 第一次操作相鄰單元
- 如果這個單元被占用，它認為這裡可能有一個小的聚集，是以它嘗試距離為4的單元
- 如果這裡也被占用，它變得有些焦慮，它認為這裡有個大的聚集，然後就嘗試距離為9的單元
- 如果這裡還是被占用了，它感到了一絲恐慌，跳到距離為16的單元，很快，它就會歇斯底裡的飛躍整個數組空間 。
- 當hash表快滿的時候，就會出現這種情況
二次探測消除了線性探測中産生的聚集問題，這種聚集被稱為原始聚集，但是也産生了更細的聚集 ，被稱為二次聚集。 二次聚集不是一個很嚴重的問題，因為不常用 。 有更好的解決方案------> rehash
DH： DOUBLE HASHING
為了消除原始聚集和二次聚集，可以使用 二次哈希 。
其實而此舉既産生的原因是二次探測的算法産生的探測序列步長總是固定的： 1，4,9，16…依次類推。
核心思想： 需要産生一種依賴關鍵字的探測序列，而不是每個關鍵字都一樣，那麼，不同的關鍵字即使映射到相同的數組下标，也可以使用不同的探測序列。把關鍵字用不同的哈希函數再做一遍哈希化，用這個結果作為步長。對于指定的關鍵字，步長在整個探測中是不變的，不過不同的關鍵字使用不同的步長。
第二個哈希函數必須具備如下特點：
- 和第一個哈希函數不同
- 不能輸出0（否則，将沒有步長，每次探測都是原地踏步，算法将陷入死循環）。
使用如下的哈希函數工作的非常好：
stepSize = constant - key % constant;
其中constant是質數，且小于數組容量。
再哈希法要求表的容量是一個質數.
舉個例子： 假如表長度為15(0-14)，非質數，有一個特定關鍵字映射到0，步長為5，則探測序列是
0,5,10,0,5,10,
以此類推一直循環下去。算法隻嘗試這三個單元，是以不可能找到某些空白單元，最終算法導緻崩潰。
如果數組容量為13, 質數，探測序列最終會通路所有單元。即
0,5,10,2,7,12,4,9,1,6,11,3,
一直下去，隻要表中有一個空位，就可以探測到它。
Q: 如果中間有個資料被删除了怎麼辦呢？
标記為 -1，否則的話就會出現資料缺失。 因為查找的時候，找到一個空位，就不找了，認為已經結束了，是以需要給删除的資料單元打标 。
核心思想： 某個資料項的關鍵字值還是像通常一樣映射到哈希表的單元，而資料項本身插入到這個單元的連結清單中。 其他同樣映射到這個位置的資料項隻需要加到連結清單中，不需要在原始的數組中尋找空位。
上述的這個模型就是JDK1.7 HashMap的原型。
再來看個極端的情況