# 2. 哈希表 映射 集合
# 定义
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接查询与访问的数据结构。
存放记录的数组叫哈希表。
通常通过映射函数(哈希函数)将关键字直接对应到表中某个位置, 从而加快查找速度
JavaScript中的对象实际上是使用哈希表本身实现的
# 哈希函数
- 把要存储的值映射到某个位置(下标)
# 工程实践
- 电话号码簿
- 用户信息表
- 缓存(LRU Cache)
- 键值对存储(Redis)
# 哈希碰撞
# 解决哈希碰撞
- 拉链法
# 复杂度
# 拉链法
hash碰撞解决方式，拉链法 与开放定址法相比，拉链法有如下几个优点：
拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。
# 拉链法的缺点
拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。
# 参考
Data Structures 101: implement hash tables in JavaScript (opens new window)