HashMap源码详细分析(JDK1.8)

喜欢ヅ旅行 2022-12-05 00:59 218阅读 0赞

`HashMap`是我们日常开发中最最最常用的集合之一，本文通过对`HashMap`中重要属性和常用的方法进行分析，但是由于`HashMap`的源码有两千多行，所以只针对部分源码进行分析。

##### HashMap的构造函数 #####

从源码中可以看到，HashMap的构造方法有四个，构造方法做的事情也比较简单，都是初始化一些变量loadFactor、threshold。

// 无参的构造方法是使用场景最多的
    public HashMap() { 
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
        
    // 有参构造方法-1，通常在已知map容量的时候使用，可以尽量避免扩容，提升效率
    public HashMap(int initialCapacity) { 
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    	
    // 有参构造方法-2
    public HashMap(int initialCapacity, float loadFactor) { 
        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;
        this.threshold = tableSizeFor(initialCapacity);
    }
    
    // 有参构造方法-3
    public HashMap(Map<? extends K, ? extends V> m) { 
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

有参构造方法-1通常在已知map大小的时候使用，调用了构造方法-2，这样子可以减少扩容带来的性能消耗，提升效率。有参构造方法-2只是设置了initialCapacity和loadFactor。有参构造方法-3不是很常用，将一个map复制到自己的map中来。

##### 初始容量、负载因子、阈值 #####

一般情况下我们使用无参构造方法来创建HashMap，基本上不用去调整`initialCapacity`和`loadFactor`参数就可以满足需求了。但是在我们对效率有一定的要求时，可能就需要手动去设置`initialCapacity`和`loadFactor`参数。通过这两个参数的设置，可以进一步影响阈值大小。

<table> 
 <thead> 
  <tr> 
   <th>名字</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>initialCapacity</td> 
   <td>HashMap的初始容量大小，默认16</td> 
  </tr> 
  <tr> 
   <td>loadFactor</td> 
   <td>负载因子</td> 
  </tr> 
  <tr> 
   <td>threshold</td> 
   <td>当前 HashMap 所能容纳键值对数量的最大值，超过这个值，则需扩容 threshold = capacity * loadFactor</td> 
  </tr> 
  <tr> 
   <td>TREEIFY_THRESHOLD</td> 
   <td>默认值8，当链表的长度大于8，转化为红黑树</td> 
  </tr> 
  <tr> 
   <td>UNTREEIFY_THRESHOLD</td> 
   <td>默认值6，红黑树的节点小于6的时候，退化为链表</td> 
  </tr> 
 </tbody> 
</table>

相关的代码如下：

/** The default initial capacity - MUST be a power of two. */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    
    /** The load factor used when none specified in constructor. */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    final float loadFactor;
    
    /** The next size value at which to resize (capacity * load factor). */
    int threshold;
    
    static final int TREEIFY_THRESHOLD = 8;
    
    static final int UNTREEIFY_THRESHOLD = 6;

##### 查找 #####

查找的方法非常简单，这里不做过多的说明，直接看源码。

public V get(Object key) { 
        Node<K,V> e;
        // 调用getNode方法
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    
    final Node<K,V> getNode(int hash, Object key) { 
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 定位键值对所在桶的位置
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != 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) { 
            	// 如果 first 是 TreeNode 类型，则调用黑红树查找方法
                if (first instanceof TreeNode)
                    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);
            }
        }
        return null;
    }

##### 遍历 #####

遍历map是在平时工作中非常常用的方法，常用的方法有：

for(Object key : map.keySet()) { 
        // do something
    }

或者

for(Map.Entry entry : map.entrySet()) { 
        // do something
    }

遍历的逻辑其实跟简单，基本上就是对map的key集合或者entry集合进行遍历。在对key集合进行遍历的时候，编译之后会转换成迭代器遍历，等同如下效果：

Set keys = map.keySet();
    Iterator ite = keys.iterator();
    while (ite.hasNext()) { 
        Object key = ite.next();
        // do something
    }

下面是遍历相关的代码

public Set<K> keySet() { 
        Set<K> ks = keySet;
        if (ks == null) { 
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }
    
    /** * 键集合 */
    final class KeySet extends AbstractSet<K> { 
        public final int size()                 {  return size; }
        public final void clear()               {  HashMap.this.clear(); }
        public final Iterator<K> iterator()     {  return new KeyIterator(); }
        public final boolean contains(Object o) {  return containsKey(o); }
        public final boolean remove(Object key) { 
            return removeNode(hash(key), key, null, false, true) != null;
        }
        // 省略部分代码
    }
    
    /** * 键迭代器 */
    final class KeyIterator extends HashIterator 
        implements Iterator<K> { 
        public final K next() {  return nextNode().key; }
    }
    
    abstract class HashIterator { 
        Node<K,V> next;        // next entry to return
        Node<K,V> current;     // current entry
        int expectedModCount;  // for fast-fail
        int index;             // current slot
    
        HashIterator() { 
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) {  // advance to first entry 
                // 寻找第一个包含链表节点引用的桶
                do { } while (index < t.length && (next = t[index++]) == null);
            }
        }
    
        public final boolean hasNext() { 
            return next != null;
        }
    
        final Node<K,V> nextNode() { 
            Node<K,V>[] t;
            Node<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            if ((next = (current = e).next) == null && (t = table) != null) { 
                // 寻找下一个包含链表节点引用的桶
                do { } while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }
        //省略部分代码
    }

如上面的源码，遍历所有的键时，首先要获取键集合`KeySet`对象，然后再通过 `KeySet` 的迭代器`KeyIterator`进行遍历。`KeyIterator` 类继承自`HashIterator`类，核心逻辑也封装在 `HashIterator` 类中。`HashIterator` 的逻辑并不复杂，在初始化时，`HashIterator` 先从桶数组中找到包含链表节点引用的桶。然后对这个桶指向的链表进行遍历。遍历完成后，再继续寻找下一个包含链表节点引用的桶，找到继续遍历。找不到，则结束遍历。

##### 插入数据 #####

插入数据的源码是最长最复杂的，涉及到插入逻辑、扩容、链表树化和红黑树链化等过程，下面我们通过源码一一分析。

*  首先我们先看一下put方法

public V put(K key, V value) { 
    	// 其实是调用putVal方法
        return putVal(hash(key), key, value, 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;
        // 如果桶数组是空，在第一次插入数据时进行扩容，大小为16
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 如果根据key的hash值在数组中查找索引位置上没有值，则直接插入（尾插法）
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else { 
        	// 如果索引位置有值，则直接覆盖
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 如果是红黑树，则调用红黑树的插入方法
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else { 
            	// 对链表进行遍历
                for (int binCount = 0; ; ++binCount) { 
                    if ((e = p.next) == null) { 
                        p.next = newNode(hash, key, value, null);
                        // 如果链表的长度大于TREEIFY_THRESHOLD，则转化成红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 当条件为true时，则表示当前链表包含将要插入的值，则终止遍历
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) {  // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 这是一个空实现的函数，用作LinkedHashMap重写使用
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 键值对数量超过阈值时，则进行扩容
        if (++size > threshold)
            resize();
        // 这是一个空实现的函数，用作LinkedHashMap重写使用 
        afterNodeInsertion(evict);
        return null;
    }

我在代码里进行了详细的注释，插入的方法不是很难，应该可以看懂，我再进行一次总结：

1.  在第一次插入的时候，如果桶数组为空，则进行第一次扩容，默认扩容大小为16
2.  如果通过key的hash值在数组的索引位置上没有值，则直接插入（尾插法）
3.  如果插入的键值对已经存在，则直接覆盖旧值
4.  如果是红黑树，则直接调用红黑树的方法进行插入
5.  遍历链表，如果链表的长度大于阈值，则转化成红黑树
6.  判断键值对的长度是否大于阈值来决定是否进行扩容

*  扩容机制

HashMap同ArrayList一样是有扩容机制的，扩容机制是一个非常重要的机制，接下来我们简单聊一下HashMap的扩容机制。

在HashMap中，桶数组的长度均是2的幂，阈值大小为桶数组长度与负载因子的乘积（默认是16 \* 0.75 = 12）。当 HashMap中的键值对数量超过阈值时，进行扩容。源码如下：

final Node<K,V>[] resize() { 
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        // 如果 table 不为空，表明已经初始化过了
        if (oldCap > 0) { 
            // 当 table 容量超过容量最大值，则不再扩容
            if (oldCap >= MAXIMUM_CAPACITY) { 
                threshold = Integer.MAX_VALUE;
                return oldTab;
            } 
            // 按旧容量和阈值的2倍计算新容量和阈值的大小
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        } else if (oldThr > 0) // initial capacity was placed in threshold
            /* * 初始化时，将 threshold 的值赋值给 newCap， * HashMap 使用 threshold 变量暂时保存 initialCapacity 参数的值 */ 
            newCap = oldThr;
        else {                // zero initial threshold signifies using defaults
            /* * 调用无参构造方法时，桶数组容量为默认容量， * 阈值为默认容量与默认负载因子乘积 */
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        
        // newThr 为 0 时，按阈值计算公式进行计算
        if (newThr == 0) { 
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        // 创建新的桶数组，桶数组的初始化也是在这里完成的
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) { 
            // 如果旧的桶数组不为空，则遍历桶数组，并将键值对映射到新的桶数组中
            for (int j = 0; j < oldCap; ++j) { 
                Node<K,V> e;
                if ((e = oldTab[j]) != null) { 
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        // 重新映射时，需要对红黑树进行拆分
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else {  // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        // 遍历链表，并将链表节点按原顺序进行分组
                        do { 
                            next = e.next;
                            if ((e.hash & oldCap) == 0) { 
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else { 
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 将分组后的链表映射到新桶中
                        if (loTail != null) { 
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) { 
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

在 `HashMap` 中，桶数组的长度均是2的幂，阈值大小为桶数组长度与负载因子的乘积。当 `HashMap` 中的键值对数量超过阈值时，进行扩容。`HashMap` 按当前桶数组长度的2倍进行扩容，阈值也变为原来的2倍（如果计算过程中，阈值溢出归零，则按阈值公式重新计算）。扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去。以上就是`HashMap`的扩容机制。

##### 删除 #####

public V remove(Object key) { 
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }
    
    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;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            // 1. 定位桶位置
            (p = tab[index = (n - 1) & hash]) != null) { 
            Node<K,V> node = null, e; K k; V v;
            // 如果键的值与链表第一个节点相等，则将 node 指向该节点
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {   
                // 如果是 TreeNode 类型，调用红黑树的查找逻辑定位待删除节点
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else { 
                    // 2. 遍历链表，找到待删除节点
                    do { 
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) { 
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            
            // 3. 删除节点，并修复链表或红黑树
            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;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

删除的操作也是map中非常常用的操作，源码中已经做了比较详细的描述，这里总结一下删除操作，其实在理解了之前内容之后，删除的操作也比较好理解了。

1.  定位桶位置
2.  遍历链表并找到键值相等的节点
3.  删除节点

##### HashMap1.8比1.7的优化 #####

*  1.8版本采用尾插法，1.7是头插法
 *  1.8的HashMap由数组+链表+红黑树组成，1.7是数组+链表，优化了性能

##### 总结 #####

本文针对`HashMap`中的构造方法、插入、扩容、查询、遍历、删除和一些重要的常量进行了分析，但因为`HashMap`的源码值得学习的太多，本文没有将所有的点都分析到，不过一些基本的思路也都说了个大概，通过本文也对`HashMap`有了更加全面的认识。