1. 哈希概念
哈希(hash)又稱散列，是?種組織數據的方式。從譯名來看，有散亂排列的意思。本質就是通過哈希 函數把關鍵字Key跟存儲位置建立一個映射關系，查找時通過這個哈希函數計算出Key存儲的位置，進行快速查找
1.1 直接定址法
當關鍵字的范圍較集中時，直接定址法就是簡單高效的方法，如?組關鍵字都在[0,99]之間， 那么開一個100個數的數組，每個關鍵字的值直接就是存儲位置的下標。再如一組關鍵字值都在 [a,z]的小寫字母，那么開一個26個數的數組，每個關鍵字acsii碼-a 的ascii碼就是存儲位置的下標。 也就是說直接定址法本質就是用關鍵字計算出一個絕對位置或者相對位置
1.2 哈希沖突
兩個不同的key可能會映射到同一個位置去，這種問題叫做哈希沖突， 或者哈希碰撞
1.3 負載因子
?假設哈希表中已經映射存儲了N個值，哈希表的大小為M，那么負載因子=N/M ，負載因子有些地方也翻譯為載荷因子/裝載因子等，負載因子越大，哈希沖突的概率越高，空間利用率越高；負載因子越小，哈希沖突的概率越低，空間利用率越低
1.4?哈希函數
一個好的哈希函數應該讓N個關鍵字被等概率的均勻的散列分布到哈希表的M個空間中，但是實際中卻很難做到，盡量往這個方向去考量設計
除法散列法/除留余數法
- 假設哈希表的大小為M，那么通過key除以M的余數作為映射位置的下標，也就是哈希函數為：h(key)=key%M
- 當使用除法散列法時，要盡量避免M為某些值，如2的冪，10的冪等
- 如果是2的冪，那么key % 2^x?本質相當于保留key的后X位，那么后x位相同的值，計算出的哈希值都是?樣的，就沖突了。如果是10的冪 ，保留的都是 10進值的后x位
- 當使用除法散列法時，建議M取不太接近2的整數次冪的一個質數(素數)
1.5?處理哈希沖突
主要有兩種兩種方法，開放定址法和鏈地址法
1.5.1 開放定址法
在開放定址法中所有的元素都放到哈希表里，當一個關鍵字key用哈希函數計算出的位置沖突了，則按照某種規則找到一個沒有存儲數據的位置進行存儲，開放定址法中負載因子一定是小于的。有三種：線性探測、?次探測、雙重探測
1）線性探測
- 從發生沖突的位置開始，依次線性向后探測，直到尋找到下一個沒有存儲數據的位置為止，如果走到哈希表尾，則回繞到哈希表頭的位置
，hash0位置沖突了，則線性探測公式為： 
，因為負載因子小于1， 則最多探測M-1次，一定能找到一個存儲key的位置- 線性探測的比較簡單且容易實現，線性探測的問題假設，hash0位置連續沖突，hash0，hash1， hash2位置已經存儲數據了，后續映射到hash0，hash1，hash2，hash3的值都會爭奪hash3位 置，這種現象叫做群集/堆積。二次探測可以一定程度改善這個問題
2）二次探測
- 從發生沖突的位置開始，依次左右按二次方跳躍式探測，直到尋找到下一個沒有存儲數據的位置為 為，如果走到哈希表尾，則回繞到哈希表頭的位置；如果往左走到哈希表頭，則回繞到哈希表尾的位置
，hash0位置沖突了，則二次探測公式為：
- 二次探測當hashi = (hash0 ? i )%M 時，當hashi<0時，需要hashi+=M
1.5.2 開放定址法代碼實現
哈希表結構
enum State
{EXIST,EMPTY,DELETE
};template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;
};template<class K, class V>
class HashTable
{
private:vector<HashData<K, V>> _tables;size_t _n = 0; // 表中存儲數據個數
};
擴容
哈希表負載因子控制在0.7，當負載因子到0.7以后就需要擴容了，給了一個近似2倍的質數表，每次去質數表獲取擴容后的大小
inline unsigned long __stl_next_prime(unsigned long n)
{// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] ={53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;
}key不能取模的問題
- 當key是string/Date等類型時，key不能取模，那么需要給HashTable增加一個仿函數，這個仿函數?持把key轉換成一個可以取模的整形
- 自己實現一個仿函數傳給這個參數，讓不同的key轉換出的整形值不同
- string 做哈希表的key很常見，可以考慮把string特化一下
template<class K>
class HashFunc
{
public:size_t operator()(const K& key){return (size_t)key;}
};template<>
class HashFunc<string>
{
public:// 字符串轉換成整形，可以把字符ascii碼相加即可 // 但是直接相加的話，類似"abcd"和"bcad"這樣的字符串計算出是相同的 // 這?我們使?BKDR哈希的思路，?上次的計算結果去乘以一個質數，這個質數一般去31, 131
等效果會?較好size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash += ch;hash *= 131;}return hash;}
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
private:vector<HashData<K, V>> _tables;size_t _n = 0; // 表中存儲數據個數
};完整代碼實現
開放地址法
1.5.3 鏈地址法
開放定址法中所有的元素都放到哈希表，鏈地址法中所有的數據不再直接存儲在哈希表中，哈希表 中存儲一個指針，沒有數據映射這個位置時，這個指針為空，有多個數據映射到這個位置時，把這些沖突的數據鏈接成一個鏈表，掛在哈希表這個位置下面，鏈地址法也叫做拉鏈法或者哈希桶
擴容
開放定址法負載因子必須小于1，鏈地址法的負載因子就沒有限制了，可以大于1
這里大于1就擴容
插入邏輯
鏈地址法代碼實現
實現代碼
