陣列與線性結構
雜湊表
雜湊表存放鍵值對，讓你能憑鍵幾乎瞬間查到值。訣竅在於：把鍵交給一個雜湊函數變成一個數字，再用這個數字（對陣列大小取模）作為一個桶陣列的索引。與其去掃描「alice」，不如算出「alice」必然落在哪裡，然後直奔過去。
平均而言，插入、查找和刪除都是 O(1)——雜湊一步就把你指到正確的桶。麻煩在於碰撞：兩個不同的鍵可能雜湊到同一個桶。雜湊表用鏈結法（每個桶掛一條小鏈結串列）或開放定址法（探查鄰近槽位）來處理。配上好的雜湊函數和合理的裝載因子（太滿時會擴充重雜湊），碰撞就很少見，O(1) 得以保持。在極壞的最壞情況下——大量碰撞——操作會退化為 O(n)。
這份速度的代價是雜湊表沒有順序：走訪得到的鍵是任意的、依賴雜湊的次序，你也無法廉價地問「最小的鍵是誰」。當你需要有序時，平衡樹（如 std::map）是替代方案；當你只需要按鍵快速查找時，雜湊表更勝一籌。
#include <unordered_map>
#include <string>
std::unordered_map<std::string, int> age;
age["alice"] = 30; // average O(1) insert
age["bob"] = 25;
int a = age["alice"]; // average O(1) lookup -> 30
// buckets: [0] -> ...
// [3] -> ("alice",30) -> ("bob",25) <- a collision, chained
bool has = age.count("carol"); // 0 (not present)hash(key) % buckets 選出一個桶；碰撞在桶內以鏈結相連。
平均 O(1) 的前提是好的雜湊函數和有界的裝載因子；若鍵是對抗性的或雜湊很差，查找可能退化為 O(n)。
又稱
另見