摘要 ：掌握高頻數據結構！今日深入解析哈希表的核心原理與設計實現，結合沖突解決策略與大廠高頻真題，徹底掌握O(1)時間復雜度的數據訪問技術。

一、哈希表核心思想

哈希表（Hash Table） 是一種基于鍵值對的高效數據結構，通過哈希函數將鍵映射到存儲位置，核心特性：

• 平均時間復雜度：插入、刪除、查找均為O(1)

• 沖突處理：開放尋址法、鏈地址法等策略

• 負載因子：哈希表性能的關鍵指標（元素數/桶數）

應用場景 ：

• 快速數據檢索

• 去重操作

• 緩存系統設計（如LRU Cache）

二、哈希表實現原理

1. 哈希函數設計

理想哈希函數特性 ：

• 確定性：相同鍵的哈希值始終相同

• 均勻性：鍵值均勻分布到各個桶

• 高效性：計算速度快

常見哈希函數 ：

• 除法哈希：hash(key) = key % capacity

• 乘法哈希：利用黃金分割點

• 多項式哈希：用于字符串處理

// 字符串哈希示例（多項式滾動哈希）
size_t stringHash(const string& s, size_t mod = 1e9+7) {size_t hash = 0;const size_t base = 31; // 常用質數基數for (char c : s) {hash = (hash * base + c) % mod;}return hash;
}

2. 沖突解決策略

動態示意圖 ：

鏈地址法示意圖

策略1：鏈地址法（Separate Chaining）

// 哈希表節點定義
template <typename K, typename V>
struct HashNode {K key;V value;HashNode* next;HashNode(K k, V v) : key(k), value(v), next(nullptr) {}
};// 哈希表類框架
template <typename K, typename V>
class HashMap {
private:vector<HashNode<K,V>*> buckets;size_t capacity;size_t size;size_t hashFunction(K key) {return hash<K>{}(key) % capacity;}public:HashMap(size_t cap = 16) : capacity(cap), size(0) {buckets.resize(cap, nullptr);}// 插入、查找、刪除操作實現...
};

策略2：開放尋址法（Open Addressing）

// 線性探測插入實現
template <typename K, typename V>
void HashMap<K,V>::put(K key, V value) {size_t index = hashFunction(key);while (buckets[index] != nullptr) {if (buckets[index]->key == key) { // 已存在則更新buckets[index]->value = value;return;}index = (index + 1) % capacity; // 線性探測}buckets[index] = new HashNode<K,V>(key, value);size++;
}

三、哈希表操作實現（C++）

1. 插入操作（鏈地址法）

template <typename K, typename V>
void HashMap<K,V>::put(K key, V value) {size_t index = hashFunction(key);HashNode<K,V>* node = buckets[index];while (node) { // 檢查鍵是否已存在if (node->key == key) {node->value = value;return;}node = node->next;}// 頭插法添加新節點HashNode<K,V>* newNode = new HashNode<K,V>(key, value);newNode->next = buckets[index];buckets[index] = newNode;size++;
}

2. 查找操作、

template <typename K, typename V>
V HashMap<K,V>::get(K key) {size_t index = hashFunction(key);HashNode<K,V>* node = buckets[index];while (node) {if (node->key == key) {return node->value;}node = node->next;}throw out_of_range("Key not found");
}

3. 刪除操作

template <typename K, typename V>
void HashMap<K,V>::remove(K key) {size_t index = hashFunction(key);HashNode<K,V>* node = buckets[index];HashNode<K,V>* prev = nullptr;while (node) {if (node->key == key) {if (prev) prev->next = node->next;else buckets[index] = node->next;delete node;size--;return;}prev = node;node = node->next;}
}

四、復雜度與優化

操作	平均情況	最壞情況
插入	O(1)	O(n)
刪除	O(1)	O(n)
查找	O(1)	O(n)

優化策略 ：

• 負載因子監控：當元素數/桶數超過閾值（如0.75），觸發擴容

• 動態擴容：容量擴展為原來的2倍，并重新哈希所有元素

• 良好的哈希函數選擇：減少沖突，提升性能