HashMap底层原理及jdk1.8源码解读【吐血整理1.3w字长文】

/**
 * 默认初始容量 - 必须是 2 的幂。
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
 * 最大容量，如果一个更高的值被任何一个带参数的构造函数隐式指定使用。必须是 2 <= 1<<30 的幂。
 * 简单理解为：最大容量2的30次幂，如果带容量也会转化为2的次幂
 */
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
 * 构造函数中未指定时使用的负载因子。经过官方测试测出减少hash碰撞的最佳值
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
 * 使用红黑树的计数阈值，超过8则转化为红黑树
 */
static final int TREEIFY_THRESHOLD = 8;
/**
 * 使用红黑树的计数阈值，低于6则转化为链表
 */
static final int UNTREEIFY_THRESHOLD = 6;
/**
 * 链表转化为红黑树，除了有阈值的限制，还有另外一个限制，需要数组容量至少达到64，才会转化为红黑树。
 * 这是为了避免，数组扩容和树化阈值之间的冲突。
 */
static final int MIN_TREEIFY_CAPACITY = 64;
/**
 * 在首次使用时初始化，并根据需要调整大小。分配时，长度始终是 2 的幂。
 * （我们还在某些操作中允许长度为零，以允许当前不需要的引导机制）
 */
transient Node<K,V>[] table;
/**
 * 保存缓存的 entrySet()，也就是存放的键值对
 */
transient Set<Map.Entry<K,V>> entrySet;
/**
 * 此映射中包含的键值映射的数量，就是数组的大小
 */
transient int size;
/**
 * 记录集合的结构变化和操作次数（例如remove一次进行modCount++）。
 * 该字段用于使 HashMap 的 Collection-views 上的迭代器快速失败。如果失败也就是我们常见的CME
 * （ConcurrentModificationException）异常
 */
transient int modCount;
/**
 * 数组扩容的大小
 * 计算方法 capacity * load factor  容量 * 加载因子
 * @serial
 */
int threshold;
/**
 * 哈希表的负载因子。
 * @serial
 */
final float loadFactor;

/**
 * 构造一个具有指定初始容量和负载因子的构造方法
 * 不建议使用这个构造方法，加载因子经过官方测试是效率最好的，所以为了效率应该保持默认
 */
public HashMap(int initialCapacity, float loadFactor) {
  // 参数为负数会抛出IllegalArgumentException异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    // 传的值超过最大值则使用默认最大值                                     
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    // 哈希表的负载因子。                                      
    this.loadFactor = loadFactor;
    // 初始化的参数默认如果不是2的次幂，直接给你转化为2的次幂
    // 传的参数为11，会自动转化为比参数大的最近的2的次幂的值，也就是16。
    // 我们后面会详细说这个方法怎么进行转化的
    this.threshold = tableSizeFor(initialCapacity);
}
/**
 * 构造一个只有指定初始容量的方法
 */
public HashMap(int initialCapacity) {
    // 我们会发现还是调用上面两个参数的构造方法，自动帮我们设置了加载因子
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
 * 构造一个具有默认初始容量(16) 和默认负载因子(0.75)的构造方法
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
 * 指定map集合，转化为HashMap的构造方法
 */
public HashMap(Map<? extends K, ? extends V> m) {
  // 使用默认加载因子
    this.loadFactor = DEFAULT_LOAD_FACTOR;
  //调用PutMapEntries()来完成HashMap的初始化赋值过程
    putMapEntries(m, false);
}
/**
 * 将传入的子Map中的全部元素逐个添加到HashMap中
 */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
  // 获得参数Map的大小，并赋值给s
    int s = m.size();
    // 判断大小是否大于0
    if (s > 0) {
      // 证明有元素来插入HashMap
      // 判断table是否已经初始化  如果table=null一般就是构造函数来调用的putMapEntries，或者构造后还没放过任何元素
        if (table == null) { // pre-size
          // 如果未初始化，则计算HashMap的最小需要的容量（即容量刚好不大于扩容阈值）。这里Map的大小s就被当作HashMap的扩容阈值，然后用传入Map的大小除以负载因子就能得到对应的HashMap的容量大小（当前m的大小 / 负载因子 = HashMap容量）
            // ((float)s / loadFactor)但这样会算出小数来，但作为容量就必须向上取整，所以这里要加1。此时ft可以临时看作HashMap容量大小
            float ft = ((float)s / loadFactor) + 1.0F;
            // 判断ft是否超过最大容量大小，小于则用ft，大于则取最大容量
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            // 暂时存放到扩容阈值上,tableSizeFor会把t重新计算到2的次幂给扩容数组大小
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 如果当前Map已经初始化,且这个map中的元素个数大于扩容的阀值就得扩容
        // 这种情况属于预先扩大容量，再put元素
        else if (s > threshold)
          // 后面展开说
            resize();
        // 遍历map,将map中的key和value都添加到HashMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            // 调用HashMap的put方法的具体实现方法putVal来对数据进行存放。该方法的具体细节在后面会进行讲解
            // putVal可能也会触发resize
            putVal(hash(key), key, value, false, evict);
        }
    }
}

/**
 * 返回给定目标容量的 2 次方。
 */
static final int tableSizeFor(int cap) {
  // cap = 10
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    // 小于0就是1，如果大于0在判断是不是超过最大容量就是n=15+1 = 16，超过就按最大容量
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

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

/**
* 将指定的值与此映射中的指定键相关联。即当前key应该存放在数组的哪个下标位置
* 如果映射先前包含键的映射，则替换旧的值。
*/
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
/**
* 这才是真正的保存方法
* @param hash         经过hash运算后的key
* @param key          你要添加的key
* @param value        你要添加的value
* @param onlyIfAbsent     如果为真，则不要更改现有值，本次为FALSE，可以替换更改
* @param evict        如果为 false，则表处于创建模式。我们为true
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
              boolean evict) {
   Node<K,V>[] tab; Node<K,V> p; int n, i;
   // 判断table是否为空
   if ((tab = table) == null || (n = tab.length) == 0)
       // 如果空的话，会先调用resize扩容,resize我们后面展开讲解
       n = (tab = resize()).length;
   // 把通过hash得到的值与数组大小-1进行与运算，这个运算就可以实现取模运算，而且位运算还有个好处，就是速度比较快。
   // 得到key所对应的数组的节点，然后把该数组节点赋值给p,然后判断这个位置是不是有元素
   if ((p = tab[i = (n - 1) & hash]) == null)
       // key、value包装成newNode节点，直接添加到此位置。
       tab[i] = newNode(hash, key, value, null);
   // 如果当前数组下标位置已经有元素了，又分为三种情况。
   else {
       Node<K,V> e; K k;
       // 当前位置元素的hash值等于传过来的hash，并且他们的key值也相等
       if (p.hash == hash &&
           ((k = p.key) == key || (key != null && key.equals(k))))
           // 则把p赋值给e，后续需要新值把旧值替换
           e = p;
       // 来到这里说明该节点的key与原来的key不同，则看该节点是红黑树，还是链表
       else if (p instanceof TreeNode)
           // 如果是红黑树，则通过红黑树的方式，把key-value存到红黑树中。后面再讲解这个方法
           e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
       else {
           // 来到这里说明结构为链表，把key-value使用尾插法插到链表尾。
           // jdk1.7 链表是头插入法，在并发扩容时会造成死循环
           // jdk1.8 就把头插入法换成了尾插入法，虽然效率上有点稍微降低一些，但是不会出现死循环
           for (int binCount = 0; ; ++binCount) {
               // 遍历该链表，知道知道下一个节点为null。
               if ((e = p.next) == null) {
                   // 说明到链表尾部，然后把尾部的next指向新生成的对象
                   p.next = newNode(hash, key, value, null);
                   // 如果链表的长度大于等于8
                   if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                       // 则链表转化成为红黑树 后面再补充
                       treeifyBin(tab, hash);
                   break;
               }
               // 如果在链表中找到了相同key的话，直接退出循环
               if (e.hash == hash &&
                   ((k = e.key) == key || (key != null && key.equals(k))))
                   break;
               p = e;
           }
       }
       // 说明发生了碰撞，e代表的是旧值，需要替换为新值
       if (e != null) { // existing mapping for key
           V oldValue = e.value;
           // 判断是不是允许覆盖旧值，和旧值是否为空
           if (!onlyIfAbsent || oldValue == null)
              // 把旧值替换
               e.value = value;
           // hashmap没有任何实现，我们先不考虑
           afterNodeAccess(e);
           // 返回新值
           return oldValue;
       }
   }
   // fail-fast机制每次对结构改变进行+1
   ++modCount;
   // 判断HashMap中的存的数据大小，如果大于数组长度*0.75，就要进行扩容
   if (++size > threshold)
       resize();
   // 也是一个空的实现
   afterNodeInsertion(evict);
   return null;
}

/**
* 根据key获取对应的value
*/
public V get(Object key) {
    Node<K,V> e;
    // 调用后存在就获取元素的value返回
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* 判断key是否在map中存在
*/
public boolean containsKey(Object key) {
  // 调用方法存在及不为null
    return getNode(hash(key), key) != null;
}
/**
* 我们发现底层都是getNode来进行干活的
*/
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 判断数组不能为空，然后取到当前hash值计算出来的下标位置的第一个元素
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 如果hash值和key都相等并不为null，则说明我们要找的就是第一个元素
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            // 返回第一个元素
            return first;
        // 如果不是第一个就接着往下找
        if ((e = first.next) != null) {
          // 如果是红黑树
            if (first instanceof TreeNode)
                // 则以红黑树的查找方式进行获取到我们想要的key对应的值
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 这里说明为普通链表，我们依次往下找即可
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 找不到key对应的值，返回null
    return null;
}

/**
 * 如果key存在，就把元素删除
 */
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
/**
 * 删除方法的具体实现
* @param hash         经过hash运算后的key
* @param key          你要移除的key
* @param value        你要移除的value
 * @param matchValue    如果为真，则仅在值相等时删除，我们为FALSE，key相同即删除
 * @param movable       如果为假，则在删除时不要移动其他节点，我们为TRUE，删除移动其他节点
 */
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 判断table不为空，链表不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 数组中的第一个节点就是我们要删除的节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 要删除的节点给node
            node = p;
        // 第一个不是，并且后面还有节点
        else if ((e = p.next) != null) {
            // 如果是红黑树
            if (p instanceof TreeNode)
              // 在红黑树中找到返回
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
              // 遍历链表
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        // 找到要删除的node
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 这里说明我们要删除的节点已找到
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 如果为红黑树，就按红黑树进行删除
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            //我们要删除的是头节点
            else if (node == p)
                 tab[index] = node.next;// 由于删除的是首节点，那么直接将节点数组对应位置指向到第二个节点即可
            //不是头节点，将当前节点指向删除节点的下一个节点
            else
                p.next = node.next;// p的下一个节点指向到node的下一个节点即可把node从链表中删除了
            // 操作+1
            ++modCount;
            // map大小-1
            --size;
            // 空的实现
            afterNodeRemoval(node);
            // 返回删除的节点
            return node;
        }
    }
    return null;
}