如何实现一个高效的 hashTable

散列法存储的基本思想是：由节点的关键码值决定节点的存储地址。散列技术除了可以用于查找外，还可以用于存储

存储

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表

散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据

hash 算法

• 散列函数的设计不能太复杂
• 散列函数生成的值要尽可能随机并且均匀分布

散列冲突

关于散列冲突解决方法的选择，我对比了开放寻址法和链表法两种方法的优劣和适应的场景。

• 大部分情况下，链表法更加普适。而且，我们还可以通过将链表法中的链表改造成其他动态查找数据结构，比如红黑树，来避免散列表时间复杂度退化成 O(n)，抵御散列碰撞攻击。
• 但是，对于小规模数据、装载因子不高的散列表，比较适合用开放寻址法。

开放选址

线性探测（Linear Probing）
二次探测（Quadratic probing)
双重散列（Double hashing

• 如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。
• 如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中

装载因子

• 过大了怎么办

针对数组的扩容，数据搬移操作比较简单。但是，针对散列表的扩容,数据搬移操作要复杂很多,因为散列表的大小变了，数据的存储位置也变了，所以我们需要通过散列函数重新计算每个数据的存储位置。