# 介紹
散列表（Hash table，也叫哈希表），是通過 `鍵` 對數據進行映射存儲的一種線性結構。
簡單的說，就是 `鍵-值` 對的數據結構。
## JS 中的 對象 和 Map
JS 中其實已經有了散列表的實現：[一般二叉樹](%E4%B8%80%E8%88%AC%E4%BA%8C%E5%8F%89%E6%A0%91.md)
- 對象（Object）：鍵只能是字符串
- ES6 中的 映射(Map）：鍵可以是各種類型
~~~
// 對象
const people = {
name: 'tom',
age: 10
}
console.log(people.name)
console.log(people.age)
// 映射
const people = new Map()
people.set('name', 'tom')
people.set('age', 10)
console.log(people.get('name'))
console.log(people.get('age'))
~~~
## 散列函數
散列表中的值也是保存在數組中的，但數組只能通過下標訪問，如何能夠通過鍵來訪問呢？
通過散列函數進行映射：
我們需要設計一個函數處理鍵，然后把鍵映射到數組中的某一個下標上。
好的散列函數有以下特點：
* 不能太復雜
* 計算出來的值要盡可能的隨機并且均勻的分布
選擇散列函數時還跟數據類型有關：
- 整數：直接對數組長度求模即可
- 字符串：每個字母都對應一個 ASCII 碼，所以可以對字符串中的每個字母求 ASCII 碼并求和，轉成數字。
~~~
function simpleHash(data, length) {
var total = 0;
for (var i = 0; i < data.length; ++i) {
total += data.charCodeAt(i);
}
return total % length
}
~~~
有沒有可能不同的鍵在經過 hash 函數計算之后得到兩個相同的值呢？
答：絕對有。
所以為了盡量減少計算出相同值的情況，我們可以優化一下 hash 函數：
~~~
function betterHash(data, length) {
const H = 131 // 任意的一個質數，31,131,3131...
var total = 0;
for (var i = 0; i < data.length; ++i) {
total += H*total + data.charCodeAt(i);
}
return total % this.table.length;
}
~~~
## 散列沖突
散列沖突是無法避免的，所以當遇到沖突時我們一般有兩種解決辦法：
* 開放尋址法
* 鏈表法
### 開放尋址法
適用場景：數組容器遠大于實際要保存的數據的量。
當發現在數組中相應下標的位置已經被其他元素占用了，那么就找這個元素后面的元素，如果為空就放進去，如果也被占用了，就再向后一個元素查找直到遇到一個空的位置為止。
比如：
1. 計算的 hash 值是 2但發現數組中 下標為 2 的位置被其他元素占用了
2.向后挪一位，發現也被占用了：
3. 再向后挪一位：發現這個位置是空的，就放進去
### 鏈表法
數組中每個位置上放一個鏈表，相關鍵的元素都掛到鏈表上：
# 代碼實現
開放尋址法的散列表：
