深入理解C++ STL Hash表

C++ STL（Standard Template Library）中的哈希表（Hash Table）是一種非常重要的數據結構，它提供了快速的插入、刪除和查找操作

1. 哈希函數（Hash Function）：哈希函數是將輸入的鍵（Key）映射到一個整數值，這個整數值作為數組的索引。一個好的哈希函數應該能夠將不同的鍵映射到不同的索引，以減少沖突的概率。C++ STL中的std::hash是一個常用的哈希函數模板。

2. 桶（Bucket）：哈希表中的每個元素都存儲在一個桶中。當發生哈希沖突時（即兩個不同的鍵具有相同的哈希值），它們將被存儲在同一個桶中。桶的數量決定了哈希表的容量。

3. 沖突解決策略（Collision Resolution Strategy）：當哈希沖突發生時，需要采取一定的策略來解決。常見的沖突解決策略有：鏈地址法（Separate Chaining）、開放尋址法（Open Addressing）和雙重散列法（Double Hashing）。C++ STL中的std::unordered_map和std::unordered_set使用鏈地址法解決沖突。

4. 擴容（Resizing）：當哈希表的負載因子（即已存儲元素數量與桶數量的比值）超過一定閾值時，為了保持性能，需要對哈希表進行擴容。擴容通常涉及重新分配更大的桶數組，并將所有元素重新插入到新的桶中。C++ STL中的std::unordered_map和std::unordered_set會在負載因子超過一定閾值時自動擴容。

下面是一個簡單的C++ STL哈希表示例：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> age_map;

    // 插入元素
    age_map["Alice"] = 30;
    age_map["Bob"] = 25;
    age_map["Charlie"] = 35;

    // 查找元素
    std::cout << "Alice's age: " << age_map["Alice"] << std::endl;

    // 刪除元素
    age_map.erase("Bob");

    return 0;
}

總之，深入理解C++ STL哈希表需要了解其基本概念、哈希函數、桶、沖突解決策略和擴容等關鍵組件。在實際編程中，合理地使用哈希表可以大大提高程序的性能。