散列表（Hash Table）是一種高效的數(shù)據(jù)結(jié)構(gòu)，廣泛用于實(shí)現(xiàn)快速的鍵值對(duì)存儲(chǔ)。

基本概念

散列表使用哈希函數(shù)將鍵映射到數(shù)組的索引。其主要優(yōu)點(diǎn)在于平均情況下提供常數(shù)時(shí)間復(fù)雜度的查找、插入和刪除操作。

• 哈希函數(shù): 將鍵映射到一個(gè)固定大小的數(shù)組索引。一個(gè)好的哈希函數(shù)應(yīng)該具備：
  • 散列均勻性：不同的鍵應(yīng)該盡量映射到不同的索引。
  • 計(jì)算簡單：哈希值的計(jì)算應(yīng)該高效。

沖突處理

由于多個(gè)鍵可能映射到同一個(gè)索引，必須采取措施處理沖突。常見的沖突解決方法包括：

• 鏈地址法: 在每個(gè)數(shù)組索引處使用鏈表存儲(chǔ)所有映射到該索引的鍵值對(duì)。
• 開放尋址法: 在數(shù)組中查找下一個(gè)可用位置，例如線性探測、二次探測和雙重散列等方法。

性能分析

時(shí)間復(fù)雜度:

• 查找：O(1)（平均情況），O(n)（最壞情況，發(fā)生沖突時(shí)）
• 插入：O(1)（平均情況），O(n)（最壞情況）
• 刪除：O(1)（平均情況），O(n)（最壞情況）

空間復(fù)雜度: O(n)，即存儲(chǔ)元素的數(shù)量。

負(fù)載因子（Load Factor）: 定義為元素?cái)?shù)量與表大小的比率。一般在負(fù)載因子超過一定閾值（如0.7）時(shí)進(jìn)行擴(kuò)容，以保持性能。

代碼實(shí)現(xiàn)

鏈地址法

#include <iostream>
#include <vector>
#include <list>
#include <utility> // for std::pair
#include <functional> // for std::hashtemplate <typename Key, typename Value>
class HashTable {
public:HashTable(size_t size = 10) : table(size), current_size(0) {}void Insert(const Key& key, const Value& value) {size_t index = Hash_(key) % table.size();for (auto& pair : table[index]) {if (pair.first == key) {pair.second = value; // 更新值return;}}table[index].emplace_back(key, value); // 插入新鍵值對(duì)current_size++;if (current_size > table.size() * load_factor) {Resize_();}}bool Get(const Key& key, Value& value) const {size_t index = Hash_(key) % table.size();for (const auto& pair : table[index]) {if (pair.first == key) {value = pair.second;return true;}}return false; // 未找到}bool Remove(const Key& key) {size_t index = Hash_(key) % table.size();auto& cell = table[index];for (auto it = cell.begin(); it != cell.end(); ++it) {if (it->first == key) {cell.erase(it); // 刪除current_size--;return true;}}return false; // 未找到}private:std::vector<std::list<std::pair<Key, Value>>> table; // 哈希表的數(shù)組size_t current_size; // 當(dāng)前存儲(chǔ)的元素?cái)?shù)量const float load_factor = 0.7; // 負(fù)載因子size_t Hash_(const Key& key) const {return std::hash<Key>()(key); // 使用標(biāo)準(zhǔn)哈希函數(shù)}void Resize_() {std::vector<std::list<std::pair<Key, Value>>> old_table = table;table.resize(old_table.size() * 2); // 擴(kuò)容current_size = 0;for (const auto& cell : old_table) {for (const auto& pair : cell) {Insert(pair.first, pair.second); // 重新插入}}}
};int main() {HashTable<std::string, int> hash_table;hash_table.Insert("apple", 1);hash_table.Insert("banana", 2);int value;if (hash_table.Get("apple", value)) {std::cout << "apple: " << value << std::endl; // 輸出: apple: 1}hash_table.Remove("apple");if (!hash_table.Get("apple", value)) {std::cout << "apple not found" << std::endl; // 輸出: apple not found}return 0;
}

代碼解析

1. 數(shù)據(jù)結(jié)構(gòu):
   • 使用 std::vector 存儲(chǔ)鏈表，鏈表用于處理沖突。
   • 每個(gè)鏈表中的元素是 std::pair<Key, Value>，用于存儲(chǔ)鍵值對(duì)。
2. 插入操作:
   • 計(jì)算哈希值并確定索引。
   • 檢查索引處是否存在相同的鍵，如果存在則更新值，否則插入新鍵值對(duì)。
   • 如果當(dāng)前元素個(gè)數(shù)超過負(fù)載因子，則調(diào)用 Resize 擴(kuò)容。
3. 查找操作:
   • 計(jì)算索引，遍歷鏈表查找對(duì)應(yīng)的鍵。
4. 刪除操作:
   • 計(jì)算索引并在鏈表中查找鍵，找到后刪除。
5. 擴(kuò)容:
   • 創(chuàng)建新的、更大的表，重新插入舊表中的元素以保證均勻分布。

開放尋址法

#include <iostream>
#include <vector>
#include <utility> // for std::pair
#include <stdexcept> // for std::out_of_rangetemplate <typename Key, typename Value>
class HashTable {
public:HashTable(size_t size = 10) : table(size), current_size(0), load_factor(0.7) {}void Insert(const Key& key, const Value& value) {if (current_size >= table.size() * load_factor) {Resize_();}size_t index = Hash_(key) % table.size();while (table[index].first != Key() && table[index].first != key) {index = (index + 1) % table.size(); // 線性探測}table[index] = { key, value };current_size++;}bool Get(const Key& key, Value& value) const {size_t index = Hash_(key) % table.size();while (table[index].first != Key()) {if (table[index].first == key) {value = table[index].second;return true;}index = (index + 1) % table.size(); // 線性探測}return false; // 未找到}bool Remove(const Key& key) {size_t index = Hash_(key) % table.size();while (table[index].first != Key()) {if (table[index].first == key) {table[index] = { Key(), Value() }; // 標(biāo)記為刪除current_size--;return true;}index = (index + 1) % table.size(); // 線性探測}return false; // 未找到}private:std::vector<std::pair<Key, Value>> table; // 散列表的數(shù)組size_t current_size; // 當(dāng)前存儲(chǔ)的元素?cái)?shù)量const float load_factor; // 負(fù)載因子size_t Hash_(const Key& key) const {return std::hash<Key>()(key); // 使用標(biāo)準(zhǔn)哈希函數(shù)}void Resize_() {std::vector<std::pair<Key, Value>> old_table = table;table.resize(old_table.size() * 2, { Key(), Value() }); // 擴(kuò)容current_size = 0;for (const auto& pair : old_table) {if (pair.first != Key()) {Insert(pair.first, pair.second); // 重新插入}}}
};int main() {HashTable<std::string, int> hash_table;hash_table.Insert("apple", 1);hash_table.Insert("banana", 2);int value;if (hash_table.Get("apple", value)) {std::cout << "apple: " << value << std::endl; // 輸出: apple: 1}hash_table.Remove("apple");if (!hash_table.Get("apple", value)) {std::cout << "apple not found" << std::endl; // 輸出: apple not found}return 0;
}

代碼解析

1. 數(shù)據(jù)結(jié)構(gòu):
   • 使用 std::vector<std::pair<Key, Value>> 存儲(chǔ)鍵值對(duì)。未使用的槽位初始化為 Key() 和 Value()，用于標(biāo)記空槽。
2. 插入操作:
   • 計(jì)算哈希值并確定初始索引。
   • 如果發(fā)生沖突，使用線性探測法查找下一個(gè)可用的索引。
   • 如果當(dāng)前元素?cái)?shù)量超過負(fù)載因子，則調(diào)用 Resize 方法進(jìn)行擴(kuò)容。
3. 查找操作:
   • 計(jì)算索引并線性探測，直到找到對(duì)應(yīng)的鍵或到達(dá)空槽。
4. 刪除操作:
   • 在查找過程中，如果找到目標(biāo)鍵，則標(biāo)記該位置為已刪除。
5. 擴(kuò)容:
   • 創(chuàng)建一個(gè)更大的數(shù)組并重新插入舊表中的元素，以保持均勻分布。

總結(jié)

散列表是一種高效且靈活的數(shù)據(jù)結(jié)構(gòu)，適合用于需要快速查找和存儲(chǔ)的場景。通過合理設(shè)計(jì)哈希函數(shù)和沖突處理策略，可以實(shí)現(xiàn)良好的性能。