好的哈希函数应该尽可能让计算的过程变得简单，提高计算的效率
(1)哈希表的主要优点是它的速度，所以在速度上不能满足，那么就达不到设计的目的了
(2)提升速度的一个方法就是让哈希函数中尽量少的有乘法和除法，因为它们的性能是比较低的
设计好的哈希函数应该具备哪些优点呢？
- 快速的计算
- 哈希表的优势在于效率，所以快速获取到对应的HashCode非常重要
- 我们需要通过快速的计算来获取到元素对应的HashCode
- 均匀的分布
- 哈希表中，无论是链地址法还是开放地址法，当多个元素映射到同一个位置的时候，都会影响效率
- 所以，优秀的哈希函数应该尽可能的将元素映射到不同的位置，让元素在哈希表中均匀的分布
快速计算：霍纳法则
在前面，我们计算哈希值的时候使用的方式：cats = 3 * 27^3 + 1 * 27^2 + 20 * 27 + 19 = 60337
这种方式是直观的计算结果，那么这种计算方式会进行几次乘法和几次加法呢？
当然，我们可能不止4项，可能有更多项,我们抽象一下，这个表达式其实是一个多项式a(n)x^n+a(n-1)x^(n-1)+...+a(1)x+a(0);
现在问题就变成了多项式有多少次乘法和加法：
- 乘法次数：
n + (n-1) + ... + 1 = n(n+1)/2 - 加法次数: n次
多项式的优化:霍纳法则
解决这类求值问题的高效算法-霍纳法则，在中国，霍纳法则也被称为秦九韶算法
通过如下编号我们可以得到一种快得多的算法，即Pn(x) = anx^n+a(n-1)x^(n-1)+...+a1x+a0Pn(x) = ((...(((anx + a(n-1))x + a(n-2))x + a(n-3))...)x+a1)x + a0
这种求值的安排我们称为霍纳法则
变换后，我们需要多少次乘法，多少次加法呢？
- 乘法次数：N次
- 加法次数：N次
如果使用大O表示时间复杂度的话，我们直接从O(N^2)降到了O(N)
均匀的分布
在设计哈希表中，我们已经有办法处理映射到相同下标值的情况：链地址法或者开放地址法
但是无论哪种方案，为了提供效率，最好的情况还是让数据在哈希表中均匀分布
因此，我们需要在使用常量的地方，尽量使用质数
哪些地方我们会使用到常量呢？
质数的使用：
- 哈希表的长度
- N次幂的底数(我么之前使用的是27)
为什么它们使用质数，会让哈希表分布更加均匀呢？
- 哈希表的长度最好使用质数
(1)再哈希法中质数的重要性：
假设表的容量不是质数，例如：表长为15(小标志0~14)
有一个特定关键字映射到0，步长为5.探测序列是多少呢？
0 - 5 - 10 - 0 - 5 - 10,依次类推，循环下去
算法只尝试这三个单元，如果这三个单元已经有了数据，那么会一致循环下去，直到程序崩溃
如果容量是一个质数，比如13，探测序列是多少呢？
0 - 5 - 10 - 2 - 7 - 12 - 4 - 9 - 1 - 6 - 11 - 3,一直这样下去
不仅不会产生循环，而且可以让数据在哈希表中更加均匀的分布
(2)链地址法中质数没有那么重要，甚至在java中故意是2的N次幂
java中的哈希表采用的是链地址法
HashMap的初始长度是16，每次自动扩展(我们还没有聊到扩展的话题),长度必须是2的次幂
这时为了服务于Key映射到index的算法
HashMap中为了提高效率，采用了位运算的方式
HashMap中index的计算公式：Index = HashCode(key) & (length - 1)
比如book的hashcode,结果为十进制的3029737,二进制的101110001110101110 1001
假定HashMap长度是默认的16，计算length - 1 的结果为十进制的15，二进制的1111
把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以index = 9
这样的方式相对于取模来说性能是高的，因为计算机更运算计算二进制的数据
但是，我发现js中进行较大数据的位运算时会出现问题，所以我的代码实现还是使用了取模
另外，我这里为了方便代码之后向开放地址法中迁移，容量还是选择使用质数