理論與進階主題
雜湊函式
雜湊函式接受一個鍵——字串、數字、任何資料——把它壓縮成一個固定大小的數，常用作一個桶陣列的索引。可以把它想成寄物處的工作人員：你遞上一件任意形狀的外套，拿回一個帶號碼的小牌子。它的意義在於，把「我該把它存到哪、又去哪找？」從一次搜尋變成一次計算：把鍵餵給函式，得到桶號，直奔那裡。
用於資料結構的好雜湊函式有三個特點。它要快，因為每次查找都要算它一遍。它要確定——同一個鍵必須永遠算出同一個數，否則你永遠找不回存進去的東西。它還要把鍵均勻地撒到各個桶裡，讓相近的鍵也落到不同位置，使各桶大致均衡，而不是把所有東西都堆進一個桶。具備這些性質，雜湊表平均就能以 O(1) 找到一個鍵。
有一個躲不掉的坑：碰撞是不可避免的。當你把一個龐大的可能鍵空間映射到有限個桶時，鴿籠原理保證總會有兩個不同的鍵落進同一個桶——鴿子就是比籠子多。好的雜湊函式能讓碰撞稀少且分布均勻，卻無法讓它絕跡，因此任何基於雜湊的結構還得有一套辦法（如鏈結法或開放定址法），來應對兩個鍵相撞時該怎麼辦。
// deterministic, fast, spreads keys across m buckets
int hash(const std::string& key, int m) {
unsigned long h = 1469598103934665603ULL; // a seed
for (char c : key) {
h ^= (unsigned char)c;
h *= 1099511628211ULL; // mix the bits
}
return (int)(h % m); // confine to [0, m)
}相同輸入永遠得到相同的桶；取模把它限定在 [0, m) 內。
密碼學雜湊（如 SHA-256）追求的是另一個目標——難以逆推。資料結構裡的雜湊只需快、且把鍵撒得均勻。
又稱
另見