一周一源码之HashMap源码解析

待我称王封你为后i 2022-05-22 07:22 238阅读 0赞

原文链接：[https://blog.csdn.net/u011291072/article/details/80726185][https_blog.csdn.net_u011291072_article_details_80726185]

## 简介 ##

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。其继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。  
实际上，HashMap是个链表数组的结构，数组的每一个元素都是hash值相同的链表。Java1.8时，HashMap为链表+数组+红黑树的数据结构。当每个数组中的链表节点超过一个阈值时，这个节点里的链表将会转换成红黑树的结构。

## 源码分析 ##

HashMap一共有2300余行代码，在这里不会对诸多的方法一一详细介绍，只针对核心、常用的代码分为几个部分来解析，以探究ArrayList的实现与特性。

### 继承实现关系 ###

![HashMap继承关系][HashMap]

### 核心成员变量 ###

#### table ####

transient Node<K,V>[] table;
       
        
         1

HashMap的链表数组，数据都保存在这个数组里。

### 其他成员变量 ###

// 默认初始容量16
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
        // 最大容量1073741824
        static final int MAXIMUM_CAPACITY = 1 << 30;
        // 默认加载因子
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
        // 一个桶的树化阈值，当一个桶中的元素个数超过8时，自动转换成红黑树结构
        static final int TREEIFY_THRESHOLD = 8;
        // 一个树的链表还原阈值，当扩容时，一个桶中的元素小于6时，则从红黑树还原回链表结构
        static final int UNTREEIFY_THRESHOLD = 6;
        // 哈希表的最小树形化容量，当哈希表中的容量大于这个值时，表中的桶才能进行树形化，否则桶内元素太多时会扩容，而不是树形化。 
        // 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
        static final int MIN_TREEIFY_CAPACITY = 64;
        transient Set<Map.Entry<K,V>> entrySet;
        // 加载因子
        final float loadFactor;
        transient int modCount;
        // HashMap的大小
        transient int size;
        // 下一次扩容时的阈值，容量*加载因子
        int threshold;
       
        
         1
         2
         3
         4
         5
         6
         7
         8
         9
         10
         11
         12
         13
         14
         15
         16
         17
         18
         19
         20
         21

### 四个构造方法 ###

#### 无参构造方法 ####

将加载因子赋值成默认值。

public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; 
        }
       
        
         1
         2
         3

#### 接收初始容量和自定义加载因子 ####

对传入的值进行合法性校验，然后使用tableSizeFor方法获取初始的扩容阈值。

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);
        }
       
        
         1
         2
         3
         4
         5
         6
         7
         8
         9
         10

#### 接收初始容量 ####

实际上就是调用了上一个构造方法，传入了默认的加载因子。

public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
       
        
         1
         2
         3

#### 接收一个map ####

初始化默认加载因子，调用putMapEntries方法填充map

public HashMap(Map<? extends K, ? extends V> m) {
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            putMapEntries(m, false);
        }
    
        final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
            int s = m.size();
            if (s > 0) {
                if (table == null) { // pre-size
                    // 根据传入的map的size和当前map的加载因子生成新的加载因子
                    float ft = ((float)s / loadFactor) + 1.0F;
                    int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                             (int)ft : MAXIMUM_CAPACITY);
                    if (t > threshold)
                        threshold = tableSizeFor(t);
                }
                else if (s > threshold)
                    // 扩容
                    resize();
                // 你看，HashMap的源码都是用这种方式遍历的
                for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                    K key = e.getKey();
                    V value = e.getValue();
                    // 循环遍历每个entryset填充到当前的HashMap
                    putVal(hash(key), key, value, false, evict);
                }
            }
        }    
       
        
         1
         2
         3
         4
         5
         6
         7
         8
         9
         10
         11
         12
         13
         14
         15
         16
         17
         18
         19
         20
         21
         22
         23
         24
         25
         26
         27
         28

### 常用私有方法 ###

有几个很常用的私有方法，会被公有方法调用。在这里先看看这些私有方法的逻辑。

#### hash(Object key) ####

属于一个很核心的私有方法，计算key的hash值。

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

这里我们可以看到，是用这个key的hashCode和经过无符号右移16位后的值做异或运算得到的。

#### resize() ####

扩容方法，在put方法中会用到。

final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) {
                // 原始容量大于0，则校验是否超过最大值，如果没有则尝试容量翻倍，下一次扩容的阈值也翻倍
                if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                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
                newCap = oldThr;
            else {               // zero initial threshold signifies using defaults
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) {
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            threshold = newThr;
            @SuppressWarnings({
         "rawtypes","unchecked"})
                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;
        }
       
        
         1
         2
         3
         4
         5
         6
         7
         8
         9
         10
         11
         12
         13
         14
         15
         16
         17
         18
         19
         20
         21
         22
         23
         24
         25
         26
         27
         28
         29
         30
         31
         32
         33
         34
         35
         36
         37
         38
         39
         40
         41
         42
         43
         44
         45
         46
         47
         48
         49
         50
         51
         52
         53
         54
         55
         56
         57
         58
         59
         60
         61
         62
         63
         64
         65
         66
         67
         68
         69
         70
         71
         72
         73
         74
         75

#### 其他核心私有方法 ####

putVal、getNode方法在下面涉及到的地方会进行分析。

### 添加元素与扩容 ###

#### putVal ####

HashMap的put方法有三个：

*  put(K key, V value)：最常用的传入key value
 *  putAll(Map < ? extends K, ? extends V> m)：传入一个map
 *  putIfAbsent(K key, V value)：如果存在key，则不进行value的覆盖

因为全部的put操作的核心是putVal方法，在只看putVal方法的实现逻辑。

/** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode.如果为false，则按照创建模式执行 * @return previous value, or null if none */
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            if ((tab = table) == null || (n = tab.length) == 0)
                // 如果table为空，则用resize方法初始化table
                n = (tab = resize()).length;
            if ((p = tab[i = (n - 1) & hash]) == null)
                // 根据hash值找到数组对应的位置，如果当前位置不存在值，则创建新的node将keyvalue存入，否则要加入链表的最后位置
                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))))
                    // 如果key相同则将当前（链表的第一个）节点赋值给e
                    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);
                            if (binCount >= TREEIFY_THRESHOLD - 1) 
                                // 超过红黑树阈值则将链表转为树
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            // 如果hash值和key值都相等，则跳出，在下面逻辑将传入值覆盖当前节点的值
                            break;
                        p = e;
                    }
                }
                if (e != null) { // existing mapping for key
                    // 覆盖key相同的值
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }
       
        
         1
         2
         3
         4
         5
         6
         7
         8
         9
         10
         11
         12
         13
         14
         15
         16
         17
         18
         19
         20
         21
         22
         23
         24
         25
         26
         27
         28
         29
         30
         31
         32
         33
         34
         35
         36
         37
         38
         39
         40
         41
         42
         43
         44
         45
         46
         47
         48
         49
         50
         51
         52
         53
         54
         55
         56
         57
         58
         59
         60

通过代码来简单总结一下HashMap在存入新节点时都发生了什么事情。

*  首先，算出hash值，找到链表数组中应该保存的位置，然后看当前位置是否已经有值。  
    
    
     *  如果为空，则创建一个新节点保存，结束；
     *  如果有值，则对比当前传入key与首节点的key值是否相同。
     *  如果相同，则覆盖当前节点的value
     *  如果不同，则判断当前节点是否为树节点，如果是则调用putTreeVal方法将传入key value保存到树节点中
     *  否则，沿着链表遍历。  
        
        
         *  当发现key值相同的节点，则break，然后在下方逻辑覆盖value
         *  如果没有key值相同的节点，则在链表末端创建新节点，将传入的key value保存到新节点

其中，如果数组中链表长度大于树形化阈值，则会调用treeifyBin(Node

final void treeifyBin(Node<K,V>[] tab, int hash) {
            int n, index; Node<K,V> e;
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                resize();
            else if ((e = tab[index = (n - 1) & hash]) != null) {
                TreeNode<K,V> hd = null, tl = null;
                do {
                    TreeNode<K,V> p = replacementTreeNode(e, null);
                    if (tl == null)
                        hd = p;
                    else {
                        p.prev = tl;
                        tl.next = p;
                    }
                    tl = p;
                } while ((e = e.next) != null);
                if ((tab[index] = hd) != null)
                    hd.treeify(tab);
            }
        }
       
        
         1
         2
         3
         4
         5
         6
         7
         8
         9
         10
         11
         12
         13
         14
         15
         16
         17
         18
         19
         20

### 取值 ###

#### get ####

HashMap的get方法有两个：

*  get(Object key)：获取key的值
 *  getOrDefault(Object key, V defaultValue)：获取key的值，如果不存在则返回传入的默认defaultValue

两个get方法的核心都是由getNode方法实现的。

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) {
                    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;
        }
       
        
         1
         2
         3
         4
         5
         6
         7
         8
         9
         10
         11
         12
         13
         14
         15
         16
         17
         18
         19

实际上与put的核心处理逻辑类似，都是根据key的hash值，去链表数组的对应位置取值。如果数组的第一个节点保存的就是传入的key，则直接返回，否则遍历链表找到对应的值。

#### containsKey(Object key) ####

获取传入key对应的值，如果不存在则返回false

public boolean containsKey(Object key) {
            return getNode(hash(key), key) != null;
        }
       
        
         1
         2
         3

#### containsValue(Object value) ####

判断是否存在value，这个厉害了，遍历了整个数组和数组中的每个链表。

public boolean containsValue(Object value) {
            Node<K,V>[] tab; V v;
            if ((tab = table) != null && size > 0) {
                for (int i = 0; i < tab.length; ++i) {
                    for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                        if ((v = e.value) == value ||
                            (value != null && value.equals(v)))
                            return true;
                    }
                }
            }
            return false;
        }
       
        
         1
         2
         3
         4
         5
         6
         7
         8
         9
         10
         11
         12
         13

### 修改 ###

#### replace(K key, V value) ####

找到传入key值的节点，将其value替换为传入的value。如果没有对应的值则返回null。

public V replace(K key, V value) {
            Node<K,V> e;
            if ((e = getNode(hash(key), key)) != null) {
                V oldValue = e.value;
                e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
            return null;
        }
       
        
         1
         2
         3
         4
         5
         6
         7
         8
         9
         10

#### replace(K key, V oldValue, V newValue) ####

这里传入了期望值，也就是说，如果key对应的值是期望值，则用新值覆盖并返回true，否则不进行覆盖操作并返回false。

public boolean replace(K key, V oldValue, V newValue) {
            Node<K,V> e; V v;
            if ((e = getNode(hash(key), key)) != null &&
                ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
                e.value = newValue;
                afterNodeAccess(e);
                return true;
            }
            return false;
        }
       
        
         1
         2
         3
         4
         5
         6
         7
         8
         9
         10

### 移除元素 ###

#### remove ####

remove方法有三个：

*  remove(Object key)：移除传入key对应的节点
 *  remove(Object key, Object value)：如果key对应的value是传入的期望value，则移除

二者的核心方法都是removeNode方法

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 &&
                (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 = 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 = 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;
                    ++modCount;
                    --size;
                    afterNodeRemoval(node);
                    return node;
                }
            }
            return null;
        }
       
        
         1
         2
         3
         4
         5
         6
         7
         8
         9
         10
         11
         12
         13
         14
         15
         16
         17
         18
         19
         20
         21
         22
         23
         24
         25
         26
         27
         28
         29
         30
         31
         32
         33
         34
         35
         36
         37
         38
         39
         40

其实也是和put与get的核心逻辑类似，都是找到对应的节点。这里将节点从链表中删去。

#### clear() ####

将size置为0并遍历table将每一个元素置为空。

public void clear() {
            Node<K,V>[] tab;
            modCount++;
            if ((tab = table) != null && size > 0) {
                size = 0;
                for (int i = 0; i < tab.length; ++i)
                    tab[i] = null;
            }
        }
       
        
         1
         2
         3
         4
         5
         6
         7
         8
         9

### 其他方法 ###

#### entrySet() ####

返回entrySet，一个泛型为Map.Entry

### 内部类 ###

#### Node ####

static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
    
            Node(int hash, K key, V value, Node<K,V> next) {
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
    
            public final K getKey()        { return key; }
            public final V getValue()      { return value; }
            public final String toString() { return key + "=" + value; }
    
            public final int hashCode() {
                return Objects.hashCode(key) ^ Objects.hashCode(value);
            }
    
            public final V setValue(V newValue) {
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
    
            public final boolean equals(Object o) {
                if (o == this)
                    return true;
                if (o instanceof Map.Entry) {
                    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                    if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                        return true;
                }
                return false;
            }
        }
       
        
         1
         2
         3
         4
         5
         6
         7
         8
         9
         10
         11
         12
         13
         14
         15
         16
         17
         18
         19
         20
         21
         22
         23
         24
         25
         26
         27
         28
         29
         30
         31
         32
         33
         34
         35
         36
         37
         38
         39

#### EntrySet ####

在调用entrySet()方法的时候，如果entrySet为null，则返回一个EntrySet对象。

final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
            public final int size()                 { return size; }
            public final void clear()               { HashMap.this.clear(); }
            public final Iterator<Map.Entry<K,V>> iterator() {
                return new EntryIterator();
            }
            public final boolean contains(Object o) {
                if (!(o instanceof Map.Entry))
                    return false;
                Map.Entry<?,?> e = (Map.Entry<?,?>) o;
                Object key = e.getKey();
                Node<K,V> candidate = getNode(hash(key), key);
                return candidate != null && candidate.equals(e);
            }
            public final boolean remove(Object o) {
                if (o instanceof Map.Entry) {
                    Map.Entry<?,?> e = (Map.Entry<?,?>) o;
                    Object key = e.getKey();
                    Object value = e.getValue();
                    return removeNode(hash(key), key, value, true, true) != null;
                }
                return false;
            }
            public final Spliterator<Map.Entry<K,V>> spliterator() {
                return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
            }
            public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
                Node<K,V>[] tab;
                if (action == null)
                    throw new NullPointerException();
                if (size > 0 && (tab = table) != null) {
                    int mc = modCount;
                    for (int i = 0; i < tab.length; ++i) {
                        for (Node<K,V> e = tab[i]; e != null; e = e.next)
                            action.accept(e);
                    }
                    if (modCount != mc)
                        throw new ConcurrentModificationException();
                }
            }
        }
       
        
         1
         2
         3
         4
         5
         6
         7
         8
         9
         10
         11
         12
         13
         14
         15
         16
         17
         18
         19
         20
         21
         22
         23
         24
         25
         26
         27
         28
         29
         30
         31
         32
         33
         34
         35
         36
         37
         38
         39
         40
         41

KeySet和Values与此类似。

## 最后 ##

### todo ###

在读代码的时候，有一个点一直搞不懂，就是entrySet是怎么维护的。因为源码中没有见到在put时有对entrySet处理的过程，但是当新增节点之后，entrySet里面就已经存在这个节点了，一直让我不是很理解。之后需要研究一下这里是怎么实现的。还有一点，就是对于红黑树的原理并不是很了解，因此这也是下一步需要研究的。

### 参考资料 ###

[深入分析hashmap][hashmap]  
[二进制的位运算][Link 1]

[https_blog.csdn.net_u011291072_article_details_80726185]: https://blog.csdn.net/u011291072/article/details/80726185
[HashMap]: /images/20220522/40fdbfd219e24d4190f0a308d0310edb.png
[hashmap]: https://blog.csdn.net/lianhuazy167/article/details/66967698
[Link 1]: https://blog.csdn.net/allenjay11/article/details/51475676