HashMap定位
- 取key的HashCode值
- 高位运算
- 计算索引
求HashCode值
- Integer: value
public static int hashCode(int value) {
return value;
}
- Long: 于高位做异或
public static int hashCode(long value) {
return (int)(value ^ (value >>> 32));
}
- Double： 变成long型，按long取HashCode
public static int hashCode(double value) {
long bits = doubleToLongBits(value);
return (int)(bits ^ (bits >>> 32));
}
- String: h = 31 * h + val[i];
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
- 为什么是 31 呢？
因为 31 是一个素数。（素数又称质数：指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。）
根据素数的特性，与素数相乘得到的结果比其他方式更容易产生唯一性，也就是说产生 hash 值重复的概率比较小。
Java 中如果相乘的数字太大会导致内存溢出问题，从而导致数据丢失。
高位运算
高16位异或低16位
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
计算索引
- 定位table：
取模计算慢
用 hash&(table.length-1) （eg: 1111取‘&与’）
table.length为2的幂次方时，相当于对length取模 - 有值转为链表
- 超过8个转为红黑树
扩容
超过capacity * 0.75扩容
扩为2 * capacity
