# 介绍
散列表（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. 再向后挪一位：发现这个位置是空的，就放进去
### 链表法
数组中每个位置上放一个链表，相关键的元素都挂到链表上：
# 代码实现
开放寻址法的散列表：
