HashMap

核心参数

1. Capacity(容量)：桶(Bucket)数目
2. LoadFactor(负载因子)：桶填满程度的最大比例 -> map.size() > Capacity * LoadFactor -> Capacity = 2 * Capacity

hash()

   // 计算hash：高16bit不变，低16bit与高16bit异或 -> hash -> 在n较小时也能保证高低位bit均参与hash的计算，且开销较小
   int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }
   //计算index：(n-1) & hash -> index = Key.hash/Capacity
   //注：n == map.size() == Capacity ； 取模用与操作会比较快，所以Capacity永远是2的N次方

put()

Entry通过next属性实现多个Entry以单向链表存放

get()

1. 无冲突直接命中
2. 有冲突key.equals(k)遍历
   1. 树：O(logn)
   2. 链表：O(n)

HashMap

原文：https://www.cnblogs.com/xuanmingxi/p/14359137.html