本篇文章是對C++學習的哈希表部分的學習分享

相信一定會對你有所幫助~

那咱們廢話不多說，直接開始吧！

---

一、基礎概念

1. 哈希核心思想：

• 哈希函數的作用：通過此函數建立一個Key與存儲位置之間的映射關系。
• 理想目標：實現O(1)時間復雜度的查找

2.直接定址法

本質：?關鍵字計算出?個絕對位置或者相對位置

適用場景：Key 范圍集中（如?[0,99]）

二、關鍵問題與解決方案

1.哈希沖突：

• 根本原因：不同 Key 映射到同一位置

• 負載因子（Load Factor）：α = N/M（N為已映射存儲的值，M為哈希表的大小）

  • α↑?→ 沖突概率↑，空間利用率↑

  • α↓?→ 沖突概率↓，空間利用率↓

2. 哈希函數設計原則：

• 目標：均勻分布、減少沖突

• 除法散列法 / 除留余數法（重點）：

  • h(key) = key % M

  • M?的選擇：避免?2^n?或?10^n，因為?key%M 會僅保留?key 的最后?n?位（二進制或十進制），導致不同?key 可能映射到同一位置。例如：

M=16（2^4）時，63（00111111）和31（00011111）的后4位均為?1111，哈希值均為15。

M=100（10^2）時，112和12312的后兩位均為12，哈希值相同。

• 理論上建議選擇遠離?2^n?的質數作為哈希表大小?M，以減少沖突。但實踐中可靈活優化，如 Java 的?HashMap?采用?2^16?作為?M，通過位運算（(key ^ (key >> 16)) & (M-1)）替代取模，既提升效率又讓高位參與計算，分散哈希值。核心在于均勻分布，而非機械套用理論。

• 其他方法（了解）：乘法散列法、全域散列法

3. 非整數Key的處理

有些數據類型無法直接用整形的哈希函數，比如string字符串類型，這時我們便可以嘗試將字符串轉證書（BKDR哈希思路）

size_t hash = 0;
for (char c : str) {hash = hash * 131 + c;  // 質數 131 減少沖突
}

三、 沖突解決策略

1. 開放定址法

線性探測：

• 從發?沖突的位置開始，依次線性向后探測，直到尋找到下?個沒有存儲數據的位置為?，如果? 到哈希表尾，則回繞到哈希表頭的位置
• 沖突后公式：hashi = (hash0 + i) % M
• 缺點：易產生聚集（Clustering）

二次探測：

• 從發?沖突的位置開始，依次左右按?次?跳躍式探測，直到尋找到下?個沒有存儲數據的位置為 ?，如果往右?到哈希表尾，則回繞到哈希表頭的位置；如果往左?到哈希表頭，則回繞到哈希表 尾的位置

• 公式：hashi = (hash0 ± i2) % M
• 緩解聚集，但可能錯過空位

刪除優化：

• 狀態標記（EXIST?/?EMPTY?/?DELETE）

1. EXIST：當前槽位存儲有效數據。

2. EMPTY：槽位從未使用過，查找時可終止探測。

3. DELETE：槽位數據已刪除，但探測鏈不能中斷（需繼續向后查找）。

enum STATE
{EMPTY,DELETE,EXIST
};

擴容機制

1. 負載因子與擴容條件

• 負載因子（Load Factor）：α = 元素數量 / 哈希表大小

• 擴容閾值：當?α ≥ 0.7?時擴容，以降低沖突概率。

• 擴容倍數：通常擴容為原大小的?2倍。

2. 質數大小的必要性

• 理論要求：哈希表大小?M?應為質數，使?key % M?分布更均勻（減少聚集）。

• 問題：若初始?M?是質數（如 7），2倍擴容后（14）不再是質數，可能引發更多沖突。

3.解決方案

• SGI 版本的質數表：

預定義質數表：按近似2倍遞增的質數序列擴容

//寫出來的28個素數（每一個都差不多為前一個的兩倍）
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
};//取素數的函數
inline unsigned long __stl_next_prime(unsigned long n)
{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;
}

• 擴容步驟：

  1. 當前大小為?53（質數），負載因子 ≥0.7 時，從表中取下一個質數?97（≈53×1.8）。

  2. 重新哈希所有元素到新表。

• 例子：在插入函數中，發現負載因子>=0.7后的操作：

• bool Insert(const pair<K, V>& kv)
  {//Check(_tables);//如果負載因子 >=0.7 時就需要擴容了if ((double)_n / (double)_tables.size() >= 0.7){HashTable<K, V,Hash> newHT(__stl_next_prime(_tables.size()+1));for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);return true;}

  完整代碼實現

• #pragma once
  #include<iostream>
  #include<vector>
  using namespace std;//寫出來的28個素數（每一個都差不多為前一個的兩倍）
  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
  };//取素數的函數
  inline unsigned long __stl_next_prime(unsigned long n)
  {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;
  }enum STATE
  {EMPTY,DELETE,EXIST
  };template<class K,class V>
  struct HashData
  {pair<K, V> _kv;STATE _state;
  };template<class K>
  struct HashFunc
  {size_t operator()(const K& key){return (size_t)key;}
  };//因為用string類型的數值做key的情況十分常見，但是在unordered_map中卻沒有在另外寫一個仿函數
  //是因為直接將HashFunc 特化 了
  template<>
  struct HashFunc<string>
  {size_t operator()(const string& s){size_t hashi = 0;for (auto e : s){hashi += e;}return hashi;}
  };template<class K,class V,class Hash = HashFunc<K>>
  class HashTable
  {
  public://構造函數HashTable(size_t size = __stl_next_prime(0)):_n(0), _tables(size){}//將一些非整形的數值強轉成整形一次方便映射關系的計算void Check(vector<HashData<K,V>>& table){double fuzai = _n / table.size();if (fuzai >= 0.7){cout << "負載過大" << endl;}else{cout << "負載正常" << endl;}}bool Insert(const pair<K, V>& kv){//Check(_tables);//如果負載因子 >=0.7 時就需要擴容了if ((double)_n / (double)_tables.size() >= 0.7){HashTable<K, V,Hash> newHT(__stl_next_prime(_tables.size()+1));for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);return true;}Hash hs;size_t hash0 = hs(kv.first) % _tables.size();size_t hashi = hash0;size_t i = 1;//如果映射的位置已經被占用了while (_tables[hashi]._state == EXIST){hashi = (hashi + i) % _tables.size();++i;}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}HashData<K,V>* Find(const K& key){Hash hs;size_t hash0 = hs(key) % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._kv.first == key && _tables[hashi]._state != DELETE){return &_tables[hashi];}hashi = (hashi + i) % _tables.size();++i;}cout << " 找不到找不到 " ;return nullptr;}bool Erase(const K& key	){HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;cout << "成功刪除！" << endl;return true;}else{cout << "刪除失敗奧" << endl;return false;}}private:vector<HashData<K, V>> _tables;size_t _n;
  };

• 2.鏈地址法

• 核心思想：沖突位置掛鏈表（桶）

• 擴容時機：負載因子?α ≥ 1（STL 風格）

• 極端場景優化：

  • 鏈表過長 → 轉紅黑樹（Java 8 HashMap 策略）

• 擴容技巧：

  • 直接移動舊節點（避免重復創建）：

// 舊節點重新映射到新表
cur->_next = newTable[hashi];
newTable[hashi] = cur;

• 例子：在哈希桶版本的Insert函數中發現負載因子過大

• bool Insert(const pair<K, V>& kv)
  {if (_n == _tables.size()){vector<Node*> newTables(__stl_next_prime(0), nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = cur->_kv.first % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTables);}size_t hashi = kv.first % _tables.size();Node* newnode = new Node(kv);newnode->_next = _table[hashi];_tables[hashi] = newnode;++_n;return true;
  }

  完整代碼實現

• template<class K, class V>
  struct HashNode
  {pair<K, V> _kv;HashNode* _next;HashNode(const pair<K,V>& key):_kv(key),_next(nullptr){}
  };template<class K,class V>
  class HashTable
  {typedef HashNode<K, V> Node;
  public:HashTable(size_t size = __stl_next_prime(0)):_tables(size,nullptr){}~HashTable(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}bool Insert(const pair<K, V>& kv){if (_n == _tables.size()){vector<Node*> newTables(__stl_next_prime(0), nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = cur->_kv.first % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTables);}size_t hashi = kv.first % _tables.size();Node* newnode = new Node(kv);newnode->_next = _table[hashi];_tables[hashi] = newnode;++_n;return true;}Node* Find(const K& key){size_t hashi = key % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}bool Erase(const K& key) {size_t hashi = key % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if (prev == nullptr){cur->_next = _tables[hashi];}else{prev->_next = cur->_next;}delete cur;return true;}prev = cur;cur = cur->_next;}return false;}
  private:vector<Node*> _tables;size_t _n = 0;
  };

  ---

  那么本次關于哈希表的知識分享就此結束了~

  非常感謝你能夠看到這里~

  如果感覺對你有些許的幫助也請給我三連 這會給予我莫大的鼓舞！

  之后依舊會繼續更新C++學習分享

  那么就讓我們

  下次再見~