hash函数的设计

  1. static final int hash(Object key) {
  2.     int h;
  3.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  4. }
  • 为了让 key 的 hashcode 的高位也参与 hash 运算

为什么扩容是2的整数倍

  • 由于 hashcode 前后有 40亿 的大小，内存肯定是不可能放下，所以要有 bucket 数组；
  • 在进行 hash 值如何对应 bucket 上的哪个元素时，一般使用 hashcode % length 的方式，但是取余操作比较慢，所以最好用位运算来代替
    • 如果采用 hashcode & (length - 1) 可以代替取余操作，但是前提是 length 必须是 2 的倍速
    • 如果 n 不是 2的幂，那么 hash() & (n - 1) 时， (n-1) 低位就不全是1，在与运算的时候低位不为1的位置计算后都为0，增大了 hash 的碰撞几率

如何解决 hash 碰撞问题

  • 根据 key 二次hash 后根据寻址算法算出 index 后，如果该位置为 null，那么会直接存入，如果该位置有内容，就会出现 hash 冲突
    • 链表插入 1.7是表头，1.8是表尾。表头插入会导致死循环的问题，造成CPU百分百。
    • 链表长度大于8且数组长度大于64的时候转为红黑树，而在红黑树元素小于6时重新回归链表

使用错误

  • 0.75 会扩容，所以设置初始值，不要直接设置 !!! 建议使用 guava 的 newXXXMapWithExpectSize() 方法!!!