小撒是一只好學(xué)的小鴨子，這天，小撒在學(xué)習(xí)算法
散列表實(shí)現(xiàn)了INSERT玄渗，SEARCH和DELETE的字典操作。在散列表中查找一個(gè)元素的期望時(shí)間是O(1)狸眼，而最壞情況下則是O(n)藤树。
散列表的實(shí)現(xiàn)在于提供一個(gè)直接尋址技術(shù)。在這里我們認(rèn)為數(shù)組下標(biāo)取值是直接尋址的拓萌，因此我們將通過數(shù)組來實(shí)現(xiàn)散列表岁钓。我們將介紹什么是散列算法，以及什么是碰撞、如何處理碰撞屡限。
散列函數(shù)
散列函數(shù)通常將一個(gè)鍵（例如一個(gè)字符串等）轉(zhuǎn)換為一個(gè)自然數(shù)（對應(yīng)數(shù)組的下標(biāo)）品嚣，從而實(shí)現(xiàn)直接尋址。
一個(gè)好的散列函數(shù)钧大，應(yīng)當(dāng)是盡可能均勻分布的翰撑，并且散列值與鍵的相似度盡可能無關(guān)。想象如果我們需要在一個(gè)散列表中存儲一系列手機(jī)號拓型，而我們的數(shù)據(jù)恰好都是173開頭的额嘿，我們自然不希望這些鍵的散列值因此頻繁發(fā)生碰撞瘸恼。
通常使用的散列方法包括除法散列劣挫、乘法散列、全域散列东帅。
其中全域散列的目的是避免最差情況：所有散列后的值進(jìn)入同一個(gè)槽中压固。因此全域散列將設(shè)計(jì)一系列將關(guān)鍵字散列至[0, m-1]的散列函數(shù)|H|，它們滿足對于所有的不相等關(guān)鍵字x和y靠闭，使x和y的散列值相等的散列函數(shù)的個(gè)數(shù)等于|H|/m帐我。在散列表創(chuàng)建時(shí)，隨機(jī)從中選擇一個(gè)散列函數(shù)并使用愧膀，如果對于某個(gè)特定的數(shù)據(jù)集沖突頻繁拦键，那重新選擇一個(gè)并重建散列表就好啦~
關(guān)于全域散列具體的內(nèi)容小撒在這里就不展開啦（因?yàn)樾∪霾⒉欢?code>_(:3」∠)_）~
碰撞
由于用于存儲數(shù)據(jù)的數(shù)組的長度是固定的，而鍵是多變的檩淋，因此就可能會(huì)發(fā)生沖突（或稱碰撞芬为，Collision）。為了解決碰撞蟀悦，我們通常會(huì)使用鏈接法與開放尋址法媚朦。
鏈接法
鏈接法處理碰撞的方式為，在每一個(gè)槽中使用鏈表來存儲數(shù)據(jù)日戈，如果新加入的數(shù)據(jù)的鍵的哈希發(fā)生了沖突询张，則把它放進(jìn)鏈表。需要注意的是我們不僅要把值放入鏈表浙炼，也需要將原本的鍵一同放入鏈表份氧，這樣在查找時(shí)才能確定哪一個(gè)是我們的數(shù)據(jù)。
使用鏈接法弯屈，插入的性能為O(1)半火，而查找在最糟的情況下則是O(n)（全部進(jìn)入同一個(gè)槽從而創(chuàng)建了長長的鏈表）。
開放尋址法
在開放尋址法中季俩，如果散列發(fā)生了碰撞钮糖，則對散列的結(jié)果再次散列，直至尋找到空槽。因此在散列函數(shù)的設(shè)計(jì)上店归，我們要使得散列函數(shù)能遍歷到所有的槽阎抒。
在開發(fā)尋址法中，描述散列表擁擠程度的裝載因子 = 關(guān)鍵字個(gè)數(shù) / 槽個(gè)數(shù)將不會(huì)大于1消痛。
代碼實(shí)現(xiàn)（Javascript）
最后且叁，我們將參照Java中的HashMap來實(shí)現(xiàn)一個(gè)接受以字符串作為鍵的散列表：
const Symbols = {
array: Symbol('array'),
hash: Symbol('hash'),
size: Symbol('size'),
};
class HashMap {
constructor() {
this[Symbols.array] = [];
this[Symbols.size] = 0;
}
size() {
return this[Symbols.size];
}
has(key) {
const index = this[Symbols.hash](key);
return !!this[Symbols.array][index];
}
get(key) {
const index = this[Symbols.hash](key);
const list = this[Symbols.array][index];
if (!list) return undefined;
let value;
list.some((item) => {
if (item.key === key) {
value = item.value;
return true;
}
return false;
});
return value;
}
set(key, value) {
const index = this[Symbols.hash](key);
let list = this[Symbols.array][index];
if (!list) {
list = this[Symbols.array][index] = [];
}
const found = list.some((item) => {
if (item.key === key) {
item.value = value;
return true;
}
return false;
});
if (!found) {
list.push({
key,
value,
});
this[Symbols.size] += 1;
}
}
[Symbols.hash](key) {
let hashCode = 0;
for (let i = 0; i < key.length; i++) {
hashCode = (hashCode << 5) - hashCode + key.charCodeAt(i);
}
return hashCode;
}
}
關(guān)于ASCII碼請參考這里。
這里對于碰撞我們使用了鏈接法來處理秩伞，大家可以使用Aa和BB逞带，AaBB和BBAa等來測試發(fā)生碰撞的情況。
大家也許注意到了(hashCode << 5) - hashCode的操作纱新，其實(shí)這就是相當(dāng)于hashCode * 31展氓，不過我們手動(dòng)通過位移操作進(jìn)行了優(yōu)化。而整型的溢出會(huì)自然而然的進(jìn)行取模操作脸爱。
這里我們沒有實(shí)現(xiàn)散列表的刪除遇汞、獲取所有鍵等方法。同時(shí)我們（相當(dāng)于）在一開始就創(chuàng)建了一個(gè)巨大的數(shù)組簿废，而Java中的哈希表為了合理利用內(nèi)存還進(jìn)行了復(fù)雜的resize操作空入。感興趣的童鞋可以自己了解一下~
