1.哈希的概念
哈希(hash)?稱散列，是?種組織數據的?式。從譯名來看，有散亂排列的意思。本質就是通過哈希函數把關鍵字Key跟存儲位置建??個映射關系，查找時通過這個哈希函數計算出Key存儲的位置，進?快速查找。
1.2.直接定址法
當關鍵字的范圍?較集中時，直接定址法就是?常簡單?效的?法，?如?組關鍵字都在[0,99]之間，那么我們開?個100個數的數組，每個關鍵字的值直接就是存儲位置的下標。再?如?組關鍵字值都在[a,z]的?寫字?，那么我們開?個26個數的數組，每個關鍵字acsii碼-a ascii碼就是存儲位置的下標。也就是說直接定址法本質就是?關鍵字計算出?個絕對位置或者相對位置
1.3.哈希沖突?
直接定址法的缺點也?常明顯，當關鍵字的范圍?較分散時，就很浪費內存甚?內存不夠?。
這?存在的?個問題就是，兩個不同的key可能會映射到同?個位置去，這種問題我們叫做哈希沖突。
1.4.負載因子
假設哈希表中已經映射存儲了N個值，哈希表的大小為M，那么 負載因子 = N/M ，負載因?有些地?也翻譯為載荷因?/裝載因?等，他的英?為load factor。負載因?越?，哈希沖突的概率越?，空間利?率越?；負載因?越?，哈希沖突的概率越低，空間利?率越低。
1.5.將關鍵字轉為整數
我們將關鍵字映射到數組中位置，?般是整數好做映射計算，如果不是整數，我們要想辦法轉換成整數。后面給具體實現方法。
2.哈希函數
?個好的哈希函數應該讓N個關鍵字被等概率的均勻的散列分布到哈希表的M個空間中，但是實際中卻很難做到，但是我們要盡量往這個?向去考量設計。
2.1除法散列法
假設哈希表的??為M，那么通過key除以M的余數作為映射位置的下標，也就是哈希函數為：h(key) = key % M。
當使?除法散列法時，要盡量避免M為某些值，如2的冪，10的冪等。如果是2^x ，那么key %
2^x本質相當于保留key的后X位，那么后x位相同的值，計算出的哈希值都是?樣的，就沖突了。如： {63 , 31}看起來沒有關聯的值，如果M是16，也就是2^4 ，那么計算出的哈希值都是15，因為63的? 進制后8位是 00111111，31的?進制后8位是 00011111。如果是10^2 ，就更明顯了，保留的都是10進值的后x位，如：{112, 12312}，如果M是100，也就是10^2 ，那么計算出的哈希值都是12。
當使?除法散列法時，建議M取不太接近2的整數次冪的?個質數(素數)。
3.處理哈希沖突
實踐中哈希表?般還是選擇除法散列法作為哈希函數，當然哈希表?論選擇什么哈希函數也避免不了沖突，那么插?數據時，如何解決沖突呢？主要有兩種兩種?法，開放定址法和鏈地址法。
3.1開放定址法
在開放定址法中所有的元素都放到哈希表?，當?個關鍵字key?哈希函數計算出的位置沖突了，則按照某種規則找到?個沒有存儲數據的位置進?存儲，開放定址法中負載因??定是?于1的。
1.線性探測：
1.1 從發?沖突的位置開始，依次線性向后探測，直到尋找到下?個沒有存儲數據的位置為?，如果?
到哈希表尾，則回繞到哈希表頭的位置。1.2 h(key) = hash0 = key % M，, hash0位置沖突了，則線性探測公式為：
hc(key,i) = hashi = (hash0 + i) % M， i = {1, 2, 3, ..., M ? 1}，
因為負載因??于1，則最多探測M-1次，?定能找到?個存儲key的位置。2.?次探測：
2.1 從發?沖突的位置開始，依次左右按?次?跳躍式探測，直到尋找到下?個沒有存儲數據的位置為
?，如果往右?到哈希表尾，則回繞到哈希表頭的位置；如果往左?到哈希表頭，則回繞到哈希表
尾的位置；
2.2 h(key) = hash0 = key % M , hash0位置沖突了，則?次探測公式為：
hc(key,i) = hashi = (hash0 ± i^2 ) % M， i = {1, 2, 3, ..., M/2}
2.3 ?次探測當 hashi = (hash0 ? i^2)%M 時，當hashi<0時，需要hashi += M
3.2擴容：
這?哈希表負載因?控制在0.7，當負載因?到0.7以后我們就需要擴容了，我們還是按照2倍擴容，但是同時我們要保持哈希表??是?個質數，第?個是質數，2倍后就不是質數了。那么如何解決了，?種?案就是除法散列中Java HashMap的使?2的整數冪，但是計算時不能直接取模的改進?法。另外?種?案是sgi版本的哈希表使?的?法，給了?個近似2倍的質數表，每次去質數表獲取擴容后的??。
3.3key不能取模的問題
當key是string/自定義等類型時，key不能取模， 那么我們需要給HashTable增加?個仿函數，這個仿函 數?持把key轉換成?個可以取模的整形，如果key可以轉換為整形并且不容易沖突，那么這個仿函數 就?默認參數即可，如果這個Key不能轉換為整形，我們就需要??實現?個仿函數傳給這個參數，實 現這個仿函數的要求就是盡量key的每值都參與到計算中，讓不同的key轉換出的整形值不同。string 做哈希表的key?常常?，所以我們可以考慮把string特化?下。
3.4開放定址法代碼實現
*3.4鏈地址法
哈希表中存儲?個指針，沒有數據映射這個位置時，這個指針為空，有多個數據映射到這個位置時，我們把這些沖突的數據鏈接成?個鏈表，掛在哈希表這個位置下?，鏈地址法也叫做拉鏈法或者哈希桶。
擴容：
開放定址法負載因?必須?于1，鏈地址法的負載因?就沒有限制了，可以?于1。負載因?越?，哈希沖突的概率越?，空間利?率越?；負載因?越?，哈希沖突的概率越低，空間利?率越低；stl中unordered_xxx的最?負載因?基本控制在1，?于1就擴容。
極端場景：
如果極端場景下，某個桶特別?怎么辦？這是把鏈表轉換成紅黑樹，提供一個思路。
3.5鏈地址法代碼實現
