0%

hash

hash

在HashMap和Hashtable中为了减少哈希碰撞,分别采用了不同的hash方法(使用的版本为JDK1.8)

HashMap

1
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

采用了高16位异或低16位来对hashCode进行扰动,防止hashCode高位不同低位相同导致hash冲突

1
(n - 1) & hash

采用与运算来计算索引位置,由于HashMap中的数组容量为2^m,所以对于(n-1)来说,二进制数全为1,该作用相当于对于hash取模运算,但是比取模运算效率高。

Hashtable

1
2
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

首先 看一下0x7FFFFFFF这个十六进制的二进制代表的是多少

1
System.out.println(Integer.toBinaryString(0x7FFFFFFF));//1111111111111111111111111111111

结果是31个1,而它是一个有符号数,第一位为0,所以0x7FFFFFFF表示的是01111111111111111111111111111111,hash & 0x7FFFFFFF 表示的就是取hash值的绝对值(因为hash值是一个int类型的数字,而int的取值范围是-2^31 ~ 2^31 - 1是存在负数的,所以先取绝对值得到正数),然后再与数组长度取模,来保证均匀分布