HashMap

put 的过程 1.hash 的过程进行hash扰动 将key的高位与地位进行异或，高位与低位进行异或 h = key.hashCode(); hash = h ^ (h >>> 16); 这样做的目的，是把高位信息混入低位。 因为数组下标的计算通常只用到低几位，如果只看原始 hashCode 的低位，容易导致分布不均。 2.根据哈希值定位数组下标 定位方式一般是： index = (n - 1) & hash 这里 n 是数组长度。 这样做比取模更高效，但前提是数组长度必须是 2 的幂次方。 这也是为什么 HashMap 的容量总会被维护成 2 的幂。 3.判断该位置是否为空 如果这个桶位置没有元素，那最简单： 直接创建一个 Node 放到这个位置 put 结束 这说明没有哈希冲突。 4.判断需要覆盖还是挂载 这时会分几种情况： 情况一：桶中第一个节点就是同一个 key 判断条件通常是： hash 相同 并且 key 相等，== 或 equals() 如果是同一个 key，就不是新增，而是 替换旧值。 也就是把旧 value 改成新 value，然后返回旧值。 情况二：当前桶是红黑树 如果这个桶里的结构已经不是链表，而是红黑树，那就按红黑树的方式插入或查找。 情况三：当前桶是链表 那就沿着链表往后找： 找到相同 key：替换 value 没找到：挂到链表尾部 ...