问一个关于HashMap取模运算离散度的问题

Question

老师你好,我想问一下,就是HashMap在计算桶的位置也就是tab索引位置时候,使用了hash&(n-1),这个式子在n=2^n时候表示hash%n,也就是取模运算,也就是说他模的是一个偶数,但是我看有些学科上说,模一个素数的话,离散度会比较高,这里是我理解有问题还是说,他本身考虑了计算的快捷而没有考虑hash冲突不均匀的场景呢?

Answer 1

翔仔 2020-11-25 00:38:31

同学好，我理解应该是这样性能比较高，并且符合计算机思维，毕竟这样做能够按位去做运算，也能按照固定的规则进行扩容，如果按照素数取模的话，规则制定相对麻烦些

• 提问者 爱学习的plhh #1

  好的，老师

• 提问者 爱学习的plhh #2

  老师，你有没有发现hashtable是对素数取模，他先把一个hashcode转成了正数，然后%length，这个的初衷又是啥啊?，难道这就是常说的舍取问题嘛？

• 翔仔 回复 提问者 爱学习的plhh #3

  我理解是的，因为hashtable这样做确实分布更均匀，但是hashmap这样做主要是为了后续操作上的方便和快捷

点开查看后面1条评论

Answer 2

提问者 爱学习的plhh 2020-11-25 00:05:01

老师,也不是我钻牛角尖,我只是想知道一下