>[success] # 散列表 ~~~ 1.散列表英文叫HashTable，散列表用的是数组支持按照下标随机访问数据的特性， 所以散列表其实就是数组的一种扩展，由数组演化而来 2.其实js 的对象就是'基于哈希表结构的' ~~~ [js 的对象就是'基于哈希表结构的'](https://zhuanlan.zhihu.com/p/24291761) >[danger] ##### 散列函数 ~~~ 1.这里要举一个例子： 当在一些运动项目的时候，经常看到运动员身上的编号，这些编号相当于表示一个运动员这样，方便 我们快速找到，这个就很像 js的对象这种数据结构，key，value的形式 2.上面的例子和散列函数有什么关系，在简单的情况下确实只要记住就是对应的key即可，但是复杂的情况下 我们需要对这个key 进行转换，从而进行一些键值对的映射，这种转换的方法就是'散列函数'，计算出来的 这种key 就叫'散列值'或者叫'哈希值' ~~~ * 引用极客时间王争数据结构与算法文章的图  >[danger] ##### 散列函数设计的基本要求 ~~~ 1.散列函数计算得到的散列值是一个非负整数； 2.如果 key1 = key2，那 hash(key1) == hash(key2)； 3.如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。 注：其中的第三条在本质上是无法避免的，这个举个例子说明，例如我们的'散列函数'是将传入进来的值转换 成对应的asii 码，通过这个asii码作为'散列值'不同的单词通过字母组合可能会出现相同的asii码。这时候虽然 满足 key1 ≠ key2，但不满足 hash(key1) ≠ hash(key2)，这个就叫散列冲突 ~~~ >[danger] ##### 解决散列冲突的方法 ~~~ 1.开放寻址法：开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入 2.链表法：在散列表中，每个'桶（bucket）'或者'槽（slot）'会对应一条链表，所有散列值相同的元素 我们都放到相同槽位对应的链表中 ~~~ * 链表法如图