String的hashCode算法系数为什么是31总结


s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
为什么选择31作为String.hashCode算法的系数?简单的讲和hash算法缺陷有关。
选出来系数目标是减少hash冲突
减少hash冲突的方法有2种:
1)让结果“均匀”分布在散列的区间内(减少数据的扎堆)
2)扩大散列的区间

选择31具体有如下3点愿意:
尽量减少数据扎堆:质数能够使得它和其他数相乘后得到的结果比其他方式更容易产成唯一性;
计算机底层是二进制操作,与2相乘等价于位移运算。
尽量增加散列区间:选择系数的时候要选择尽量长且乘法尽量不要溢出的系数;
在java乘法中如果数字相乘过大会导致溢出的问题,从而导致数据的丢失。大于如果选择大于31 = 11111[2]的数,结果更易溢出
考虑性能:即用位移和减法代替乘法;
31有个很好的特性,可以得到很好的性能:31*i=(1<<5)-1。现在的VM可以自动完成这种优化
选择31的原因在《java技术核心技术卷》和《Effective Java》都可以找到