如何实现一个高效的 hashTable
散列法存储的基本思想是：由节点的关键码值决定节点的存储地址。散列技术除了可以用于查找外，还可以用于存储
存储
散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表
散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据
hash 算法
- 散列函数的设计不能太复杂
- 散列函数生成的值要尽可能随机并且均匀分布
散列冲突
关于散列冲突解决方法的选择，我对比了开放寻址法和链表法两种方法的优劣和适应的场景。
- 大部分情况下，链表法更加普适。而且，我们还可以通过将链表法中的链表改造成其他动态查找数据结构，比如红黑树，来避免散列表时间复杂度退化成 O(n)，抵御散列碰撞攻击。
- 但是，对于小规模数据、装载因子不高的散列表，比较适合用开放寻址法。
开放选址
线性探测（Linear Probing）
二次探测（Quadratic probing)
双重散列（Double hashing
- 如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。
- 如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中
装载因子
- 过大了怎么办
针对数组的扩容，数据搬移操作比较简单。但是，针对散列表的扩容,数据搬移操作要复杂很多,因为散列表的大小变了，数据的存储位置也变了，所以我们需要通过散列函数重新计算每个数据的存储位置。