你好大佬,可以解释一下为什么String类计算哈希代码要乘31嘛

Replies
2

以字符串"123"为例:字符'1'的ascii码是49,hashCode = (49*31 + 50)*31 + 51或者这样看:hashCode=('1' * 31 + '2' ) * 31 + '3'。可以看作是一种权重的算法,在前面的字符的权重大。这样有个明显的好处,就是前缀相同的字符串的hash值都落在邻近的区间。好处有两点:

1.可以节省内存,因为hash值在相邻,这样hash的数组可以比较小。比如当用HashMap,以String为key时。

2.hash值相邻,如果存放在容器,比好HashSet,HashMap中时,实际存放的内存的位置也相邻,则存取的效率也高。

以31为倍数,原因是31的二进制全是1,在一定程度上可以有效地离散数据。 smile

我来确认一下(这块我确实不懂)

前面的字符权重较大是因为拆开括号后乘的31比较多,对整体哈希值的影响就大,对不对

另外,我认为这不能节约空间。实际使用String当作键的时候,大概率前缀的差异较大,这样会导致数据离散,对于数组这种占用连续的空间的数据结构,这样会看起来密度小,浪费的空间其实大了,实在太多的数据也不会用HashMap实现。我觉得它实际是为了避免太多哈希冲突带来的负面影响

然后我还是不理解为什么全是1了就会数据离散,而且照你前面说的,数据离散不是缺点吗