散列表（Hash Table）

散列表其实就是数组+hash函数构成。
所以它就具有了数组和hash函数的所有优点。
数组，支持按索引随机访问数组中的任意数据；
hash函数，可以将任意类型的数据映射成为一个整数（数组下标）。
所以当我们存储数据的时候，将数据存储到按hash函数计算出来的索引下面，查询的时候通过hash函数就可以找到数据所在位置的下标，就可以在O(1)时间内取到数据。

这里肯能遇到的问题是，两个key可能映射到了同一个下标值，我们把这种现象称为hash冲突。显然不能直接覆盖，否则之前存的数据就没有了。常用的解决方法有两个：

• 开放寻址法
  如果hash函数计算出来的下标索引下面已经有数据了，就找该下标之后第一个没有数据的位置存放数据。

• 链表法
  在每个元素中存储一个链表，将相同hash 值的所有元素都存储在这个链表上面

  
  image.png