哈希表是什么？
- 哈希表是一种数据结构
- 哈希表表示了关键码值和记录的映射关系
- 哈希表可以加快查找速度
- 任意哈希表，都满足有哈希函数f(key)，代入任意key值都可以获取包含该key值的记录在表中的地址
与普通的列表不同的地方在于，普通列表仅能通过下标来获取目标位置的值，而哈希表可以根据给定的key计算得到目标位置的值。
哈希表有什么优势？
通过前面的概念了解，哈希表的优点呼之欲出：通过关键值计算直接获取目标位置，对于海量数据中的精确查找有非常惊人的速度提升，理论上即使有无限的数据量，一个实现良好的哈希表依旧可以保持O(1)的查找速度，而O(n)的普通列表此时已经无法正常执行查找操作（实际上不可能，受到JVM可用内存限制，机器内存限制等）。
散列表是算法在时间和空间上作出权衡的经典例子
如果没有内存限制，我们可以直接将键作为（可能是一个超大的）数组的索引，那么所有查找操作只需要访问内存一次即可完成。但这种理想情况不会经常出现，因为当键很多时需要的内存太大。另一方面，如果没有时间限制，我们可以使用无序数组并进行顺序查找，这样就只需要很少的内存。而散列表则使用了适度的空间和时间并在这两个极端之间找到了一种平衡。事实上，我们不必重写代码，只需要调整散列算法的参数就可以在空间和时间之间作出取舍。我们会使用概率论的经典结论来帮组我们选择适当的参数。
使用Hash的查询算法分为两步：
① 用Hash函数将被查找的键转化为数组的一个索引。
理想情况下，不同的键都能转化为不同的索引值。当然，这只是理想情况，所以我们需要面对两个或者多个键都会散列到相同的索引值的情况。
② 处理碰撞冲突的过程
几种常见的Hash算法：
① 除法哈希法
公式：hash(key) = key mod M 注意：M 通常为“素数”
② 乘法哈希法
公式：hash(key) = floor( M/W * ( a * key mod W) )
其中 floor 表示对表达式进行下取整
③ 斐波那契（Fibonacci）哈希法
也就是当 “乘法哈希法” 的 a ≈ W/φ，1/φ ≈ (√5-1)/2 = 0.618 033 988 时情况。而，1/φ ≈ (√5-1)/2 = 0.618 033 988，可称为黄金分割点。
常见的两种解决碰撞的方法
① 拉链法（separate chaining）
一个Hash函数能够将键转换为数组索引，Hash算法的第二部是碰撞处理，也就是处理两个或多个键的Hash值相同的情况。一种直接的办法是将大小为 M 的数组中的每个元素指向一条链表，链表中的每个结点都存储了Hash值为该元素的索引的键值对。这种方法被称为“拉链法”，因此发生冲突的元素都被存储在一个链表中。
作者：tomas家的小拨浪鼓
链接：https://www.jianshu.com/p/07d9b19bb265
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 标签：Hash,哈希,索引,查找,内存,key From： https://www.cnblogs.com/xiaoxiaobai2017/p/18016963