集合

hashMap的寻址算法

❒ hash计算过程

//  hash计算key

public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}

// 对hash值右移16位再与原来的hash值做异或运算

static final int hash(Object key) {
 int h;
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// (n-1)&hash:得到数组中的索引，代替取模，性能更好数组长度必须是2的n次幂

final V putVal(int hash, K key, V value, boolean onlylfAbsent, boolean evict) {
 ......
 if ((p = tab[i = (n - 1) & hash]) == null)
 ......
}

❒ 为何HashMap的数组长度一定是2的次幂?

1.计算索引时效率更高:如果是2 的n次幂可以使用位与运算代替取模
2.扩容时重新计算索引效率更高:hash & oldCap ==0的元素留在原来位置，否则新位置=旧位置 + oldCap

❒ hashMap的寻址算法
✔ 计算对象的hashCode()再进行调用hash()方法进行二次哈希，hashcode值右移16位再异或运算，让哈希分布更为均匀
✔ 最后(capacity- 1) & hash得到索引
❒ 为何HashMap的数组长度一定是2的次幂?
✔ 计算索引时效率更高:如果是2的n次幂可以使用位与运算代替取模扩容时重新计算索引效率更高
✔ hash &oldCap==0的元素留在原来位置，否则新位置=旧位置+oldCap