（源码分析）JDK1.8 HashMap源码分析

Myth丶恋晨 2024-04-17 06:24 99阅读 0赞

### 目录 ###

*   *  成员变量
     *  构造方法
     *  Node<K,V>
     *  TreeNode<K,V>
     *  put(K key, V value)
     *  get(K key)
     *  remove(Object key)
     *  containsKey(Object key)
     *  containsValue(Object value)
     *  keySet()
     *  values()
     *  entrySet()
     *  clear()
     *  size()
     *  isEmpty()
 *  总结

**说明：当前HashMap的版本为JDK1.8.0\_144**

## 成员变量 ##

transient int modCount; // 修改次数，当进行put、remove等操作时将会加1
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认大小为16
    static final float DEFAULT_LOAD_FACTOR = 0.75f; // 加载因子，当HashMap中的元素到达当前大小*0.75时，HashMap将会扩容为原来的2倍
    int threshold; // 阈值，为当前HashMap容量*加载因子的值
    transient int size; // HashMap元素的个数
    static final int MAXIMUM_CAPACITY = 1 << 30; // HashMap设置的最大容量
    transient Node<K,V>[] table; // Node数组
    transient volatile Set<K> keySet = null; // HashMap中key的set集合
    static final int TREEIFY_THRESHOLD = 8; // 阈值，链表中到达8个元素后将链表转换成红黑树
    static final int UNTREEIFY_THRESHOLD = 6; // 阈值，当红黑树的元素到达6个时将红黑树还原成链表

## 构造方法 ##

*  HashMap()：无参构造方法

/** * 使用HashMap默认的加载因子0.75，在new HashMap()的时候并未对HashMap进行初始化，它是在第一次执行put()方法时进行初始化的 */
    public HashMap() { 
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }

*  HashMap(int initialCapacity)：指定初始化容量

/** * 指定HashMap初始化大小，使用默认的加载因子0.75 */
    public HashMap(int initialCapacity) { 
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

*  HashMap(int initialCapacity)：指定初始化容量和加载因子

/** * 指定HashMap初始化大小和加载因子 */
    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);
    }
    
    /** * 计算阙值 */
    static final int tableSizeFor(int cap) { 
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

*  HashMap(Map<? extends K, ? extends V> m)

/** * 使用Map实现类来创建HashMap */
    public HashMap(Map<? extends K, ? extends V> m) { 
        this.loadFactor = DEFAULT_LOAD_FACTOR; // 默认加载因子为0.75
        putMapEntries(m, false);
    }
    
    /** * 添加Map */
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 
        int s = m.size();
        if (s > 0) { 
            if (table == null) { 
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); // 获取新HashMap的容量
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {  // 遍历Map，将元素一个一个添加到新的HashMap中
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

## Node<K,V> ##

**内部类Node说明：**

> 1、Node主要包含三个成员变量，key：HashMap的key；value：HashMap的value；next：指向下一个Node  
> 2、HashMap其实可以看做是一个Node的集合，每一个key和value都封装在Node元素中  
> 3、JDK1.7中的Entry和JDK1.8中的Node基本相同

**HashMap原理图：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1NjIwNTAx_size_16_color_FFFFFF_t_70]

**内部类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;
        }
    }

## TreeNode<K,V> ##

**内部类TreeNode说明：**

> 1、内部类TreeNode是对红黑树的实现  
> 2、HashMap在节点数大于8链表转换成红黑树

**内部类TreeNode源码：**

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) { 
            super(hash, key, val, next);
        }
    
        /** * 在红黑树中寻找元素 */
        final TreeNode<K,V> find(int h, Object k, Class<?> kc) { 
            TreeNode<K,V> p = this;
            do { 
                int ph, dir; K pk;
                TreeNode<K,V> pl = p.left, pr = p.right, q;
                if ((ph = p.hash) > h)
                    p = pl;
                else if (ph < h)
                    p = pr;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                else if (pl == null)
                    p = pr;
                else if (pr == null)
                    p = pl;
                else if ((kc != null ||
                          (kc = comparableClassFor(k)) != null) &&
                         (dir = compareComparables(kc, k, pk)) != 0)
                    p = (dir < 0) ? pl : pr;
                else if ((q = pr.find(h, k, kc)) != null)
                    return q;
                else
                    p = pl;
            } while (p != null);
            return null;
        }
    
        /** * 获取红黑树元素 */
        final TreeNode<K,V> getTreeNode(int h, Object k) { 
            return ((parent != null) ? root() : this).find(h, k, null);
        }
    
        /** * 向红黑树中添加元素 */
        final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) { 
            Class<?> kc = null;
            boolean searched = false;
            TreeNode<K,V> root = (parent != null) ? root() : this;
            for (TreeNode<K,V> p = root;;) { 
                int dir, ph; K pk;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) { 
                    if (!searched) { 
                        TreeNode<K,V> q, ch;
                        searched = true;
                        if (((ch = p.left) != null &&
                             (q = ch.find(h, k, kc)) != null) ||
                            ((ch = p.right) != null &&
                             (q = ch.find(h, k, kc)) != null))
                            return q;
                    }
                    dir = tieBreakOrder(k, pk);
                }
    
                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) { 
                    Node<K,V> xpn = xp.next;
                    TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    xp.next = x;
                    x.parent = x.prev = xp;
                    if (xpn != null)
                        ((TreeNode<K,V>)xpn).prev = x;
                    moveRootToFront(tab, balanceInsertion(root, x));
                    return null;
                }
            }
        }
    
        /** * 删除红黑树中的Node元素 */
        final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                  boolean movable) { 
            int n;
            if (tab == null || (n = tab.length) == 0)
                return;
            int index = (n - 1) & hash;
            TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
            TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
            if (pred == null)
                tab[index] = first = succ;
            else
                pred.next = succ;
            if (succ != null)
                succ.prev = pred;
            if (first == null)
                return;
            if (root.parent != null)
                root = root.root();
            if (root == null || root.right == null ||
                (rl = root.left) == null || rl.left == null) { 
                tab[index] = first.untreeify(map);  // too small
                return;
            }
            TreeNode<K,V> p = this, pl = left, pr = right, replacement;
            if (pl != null && pr != null) { 
                TreeNode<K,V> s = pr, sl;
                while ((sl = s.left) != null) // find successor
                    s = sl;
                boolean c = s.red; s.red = p.red; p.red = c; // swap colors
                TreeNode<K,V> sr = s.right;
                TreeNode<K,V> pp = p.parent;
                if (s == pr) {  // p was s's direct parent
                    p.parent = s;
                    s.right = p;
                }
                else { 
                    TreeNode<K,V> sp = s.parent;
                    if ((p.parent = sp) != null) { 
                        if (s == sp.left)
                            sp.left = p;
                        else
                            sp.right = p;
                    }
                    if ((s.right = pr) != null)
                        pr.parent = s;
                }
                p.left = null;
                if ((p.right = sr) != null)
                    sr.parent = p;
                if ((s.left = pl) != null)
                    pl.parent = s;
                if ((s.parent = pp) == null)
                    root = s;
                else if (p == pp.left)
                    pp.left = s;
                else
                    pp.right = s;
                if (sr != null)
                    replacement = sr;
                else
                    replacement = p;
            }
            else if (pl != null)
                replacement = pl;
            else if (pr != null)
                replacement = pr;
            else
                replacement = p;
            if (replacement != p) { 
                TreeNode<K,V> pp = replacement.parent = p.parent;
                if (pp == null)
                    root = replacement;
                else if (p == pp.left)
                    pp.left = replacement;
                else
                    pp.right = replacement;
                p.left = p.right = p.parent = null;
            }
    
            TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
    
            if (replacement == p) {   // detach
                TreeNode<K,V> pp = p.parent;
                p.parent = null;
                if (pp != null) { 
                    if (p == pp.left)
                        pp.left = null;
                    else if (p == pp.right)
                        pp.right = null;
                }
            }
            if (movable)
                moveRootToFront(tab, r);
        }
    
        /** * */
        final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { 
            TreeNode<K,V> b = this;
            // Relink into lo and hi lists, preserving order
            TreeNode<K,V> loHead = null, loTail = null;
            TreeNode<K,V> hiHead = null, hiTail = null;
            int lc = 0, hc = 0;
            for (TreeNode<K,V> e = b, next; e != null; e = next) { 
                next = (TreeNode<K,V>)e.next;
                e.next = null;
                if ((e.hash & bit) == 0) { 
                    if ((e.prev = loTail) == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                    ++lc;
                }
                else { 
                    if ((e.prev = hiTail) == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                    ++hc;
                }
            }
    
            if (loHead != null) { 
                if (lc <= UNTREEIFY_THRESHOLD)
                    tab[index] = loHead.untreeify(map);
                else { 
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                        loHead.treeify(tab);
                }
            }
            if (hiHead != null) { 
                if (hc <= UNTREEIFY_THRESHOLD)
                    tab[index + bit] = hiHead.untreeify(map);
                else { 
                    tab[index + bit] = hiHead;
                    if (loHead != null)
                        hiHead.treeify(tab);
                }
            }
        }
    }

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

**put(K key, V value)执行原理：**

> 1、获取key的hash值  
> 2、判断HashMap是否需要进行扩容(table为null或长度为0)  
> 3、根据hash值获取该key在此HashMap在table的下标  
> 4、判断table下标处是否存在元素，如果不存在元素直接table\[i\]=新节点  
> 5、先判断table下标处链表首节点key是否是相同然后获取Node节点  
> 6、再判断Node节点是否是TreeNode，如果是使用内部类TreeNode中的put方法进行添加元素  
> 7、如果不是TreeNode节点，先添加新节点，当table数组的长度小于64，优先扩容，否则当该链表节点数是否大于8时，将该链表转换成红黑树  
> 8、如果数组大小大于阙值，将对HashMap进行扩容

**put(K key, V value)源码：**

/** * 添加元素 */
    public V put(K key, V value) { 
        return putVal(hash(key), key, value, false, true);
    }
    
    /** * 获取key的哈希值 */
    static final int hash(Object key) { 
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    /** * 添加元素 */
    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为null并且table数组的长度为0时，即为使用构造方法新建HashMap对象时，在第一次执行put()时需要进行扩容
            n = (tab = resize()).length; // 对table数组进行扩容
        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) // 如果p为TreeNode内部类的实现，则使用内部类中的put方法添加元素
                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); // 创建新的Node节点
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { 
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e); // 空实现
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold) // 如果容量size超过threshold阙值
            resize(); // 对HashMap进行扩容
        afterNodeInsertion(evict); // 空实现
        return null;
    }
    
    /** * 为table数组扩容 */
    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) { 
            if (oldCap >= MAXIMUM_CAPACITY) {  // 判断当前的table的容量是否到达HashMap所能容纳的最大值，确保容量不会越界
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 当oldThr*2<HashMap最大值并且oldCap>16时
                newThr = oldThr << 1; // oldThr * 2
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {  // 对未初始化的HashMap进行初始化
            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 { 
                        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;
    }
    
    /** * 将链表转换为红黑树 */
    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);
        }
    }

## get(K key) ##

**get(K key)执行原理：**

> 1、获取key的hash值  
> 2、根据hash值获取该key在此HashMap在table的下标  
> 3、判断Node节点是否是TreeNode内部类，如果是，使用内部类TreeNode中的get方法获取Node元素，如果不是，遍历table下标处的链表查找是否此key

**get(K key)源码：**

/** * 获取元素 */
    public V get(Object key) { 
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    
    /** * 获取key的哈希值 */
    static final int hash(Object key) { 
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    /** * 根据key的哈希值和可以获取Node节点 */
    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) {  // 获取first节点(就是第一个节点)
            if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) { 
                if (first instanceof TreeNode) // 当为红黑树Node节点时
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do { 
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))  // 当不为红黑树Node节点时
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

## remove(Object key) ##

**remove(Object key)执行原理：**

> 1、获取key的hash值  
> 2、根据hash值获取该key在此HashMap在table的下标  
> 3、循环遍历table数组下标为处的链表，判断Node元素是否是TreeNode节点，如果是使用TreeNode内部类中的get方法获取Node元素，如果不是则遍历table下标处的链表  
> 4、将第三步获取的Node节点删除，如果Node元素是TreeNode节点，使用TreeNode内部类中的remove方法删除Node元素，如果不是则使用普通链表删除的方式

**remove(Object key)源码：**

/** * 删除指定key的Entry元素 */
    public V remove(Object key) { 
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }
    
    /** * 获取key的哈希值 */
    static final int hash(Object key) { 
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    /** * 删除Node节点 */
    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内部类中的get方法获取节点信息
                    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) // 当Node节点为红黑树时，使用TreeNode内部类中的remove方法删除节点
                    ((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;
    }

## containsKey(Object key) ##

**containsKey(Object value)执行原理：**

> 1、获取key的哈希值  
> 2、根据hash值获取该key在此HashMap在table的下标处的链表  
> 3、然后遍历该下标处的链表，如果存在此Node元素，则返回true，不存在则返回null

**containsKey(Object value)源码：**

/** * 判断此HashMap中是否存在此key */
    public boolean containsKey(Object key) { 
        return getNode(hash(key), key) != null;
    }
    
    /** * 获取key的哈希值 */
    static final int hash(Object key) { 
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    /** * 根据key的哈希值和可以获取Node节点 */
    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) {  // 获取first节点(就是第一个节点)
            if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) { 
                if (first instanceof TreeNode) // 当为红黑树Node节点时
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do { 
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))  // 当不为红黑树Node节点时
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

## containsValue(Object value) ##

**containsValue(Object value)执行原理：**

> 1、循环遍历table数组和下标

**containsValue(Object value)源码：**

/** * 判断此HashMap中是否存在此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;
    }

## keySet() ##

**keySet()执行原理：**

> 1、判断keySet是否为null，如果为null则new KeySet()  
> 2、但是在内部类KeySet中和其父类的构造方法中并没有将HashMap中的key保存在keySet中，所以在new KeySet()时该set集合是空的，它是通过迭代器遍历时去遍历HashMap中的Node元素中的key值  
> 3、和JDK1.7的基本没有变化

**keySet()源码：**

/** * 获取Entry元素中key值的set集合 */
    public Set<K> keySet() { 
        Set<K> ks = keySet;
        if (ks == null) { 
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }
    
    /** * HashMap内部类KeySet继承自抽象类AbstractSet */
    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;
        }
        public final Spliterator<K> spliterator() { 
            return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super K> 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.key);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }
    
    /** * 返回内部类KeyIterator的实例 */
    final class KeyIterator extends HashIterator implements Iterator<K> { 
        public final K next() {  return nextNode().key; }
    }
    
    /** * 内部抽象类HashIterator */
    abstract class HashIterator { 
        Node<K,V> next;
        Node<K,V> current;
        int expectedModCount;
        int index;
    
        HashIterator() { 
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) { 
                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;
        }
    
        public final void remove() { 
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

## values() ##

**values()执行原理：**

> 1、判断keySet是否为null，如果为null则new KeySet()  
> 2、但是在内部类KeySet中和其父类的构造方法中并没有将HashMap中的key保存在keySet中，所以在new KeySet()时该set集合是空的，它是通过迭代器遍历时去遍历HashMap中的Node元素中的key值  
> 3、和JDK1.7的基本没有变化

**values()源码：**

/** * 获取Entry元素中value值的Collection集合 */
    public Collection<V> values() { 
        Collection<V> vs = values;
        if (vs == null) { 
            vs = new Values();
            values = vs;
        }
        return vs;
    }
    
    /** * HashMap内部类Values继承自抽象类AbstractCollection */
    final class Values extends AbstractCollection<V> { 
        public final int size()                 {  return size; }
        public final void clear()               {  HashMap.this.clear(); }
        public final Iterator<V> iterator()     {  return new ValueIterator(); }
        public final boolean contains(Object o) {  return containsValue(o); }
        public final Spliterator<V> spliterator() { 
            return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super 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.value);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }
    
    /** * 返回内部类ValueIterator的实例 */
    final class ValueIterator extends HashIterator implements Iterator<V> { 
        public final V next() {  return nextNode().value; }
    }
    
    /** * 内部抽象类HashIterator */
    abstract class HashIterator { 
        Node<K,V> next;
        Node<K,V> current;
        int expectedModCount;
        int index;
    
        HashIterator() { 
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) { 
                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;
        }
    
        public final void remove() { 
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

## entrySet() ##

**entrySet()执行原理：**

> 1、entrySet()的执行原理和keySet()基本一致  
> 2、判断entrySet是否为null，如果为null则new EntrySet()  
> 3、但是在内部类EntrySet中和其父类的构造方法中并没有将HashMap中的Entry元素保存在entrySet中，所以在new EntrySet()时该set集合是空的，它是通过迭代器遍历时去遍历HashMap中的Node元素  
> 4、和JDK1.7的基本没有变化

**entrySet()源码：**

/** * 获取Entry元素set集合 */
    public Set<Map.Entry<K,V>> entrySet() { 
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }
    
    /** * 静态内部类EntrySet，继承自抽象类AbstractSet */
    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();
            }
        }
    }
    
    /** * 返回迭代器静态内部类EntryIterator */
    final class EntryIterator extends HashIterator implements Iterator<Map.Entry<K,V>> { 
        public final Map.Entry<K,V> next() {  return nextNode(); }
    }
    
    /** * 内部抽象类HashIterator */
    abstract class HashIterator { 
        Node<K,V> next;
        Node<K,V> current;
        int expectedModCount;
        int index;
    
        HashIterator() { 
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) { 
                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;
        }
    
        public final void remove() { 
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

## clear() ##

**clear()执行原理：**

> 1、循环table数组，将数组中的元素设置为null  
> 2、相比于JDK1.7的clear()方法，在JDK1.8中对table进行了判断

**clear()源码：**

/** * 将HashMap中的元素清空 */
    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;
        }
    }

## size() ##

**size()执行原理：**

> 1、直接返回此HashMap中的元素个数  
> 2、和JDK1.7一样

**size()源码：**

/** * 返回此HashMap中的元素个数 */
     public int size() { 
    	return size;
     }

## isEmpty() ##

**isEmpty()执行原理：**

> 1、判断此HashMap中的元素个数是否为0  
> 2、和JDK1.7一样

**isEmpty()源码：**

/** * 判断此HashMap中的元素个数是否为0 */
    public boolean isEmpty() { 
        return size == 0;
    }

# 总结 #

*  JDK1.8的HashMap底层是使用数据+链表+红黑树实现的
 *  HashMap是线程不安全的，内部使用fast-fail机制当在使用HashMap中出现了线程安全问题时，将会抛出ConcurrentModificationException来提交你，避免你继续错下去
 *  HashMap中的元素都可以看做是一个Node元素，Node主要包含三个成员变量，key：HashMap的key；value：HashMap的value；next：指向下一个Node，每一个key和value都封装在Node元素中
 *  keySet()、values()、entrySet()方法返回的都是空的内部实现类，该内部类在返回的时候内部并没有元素，同时HashMap在put()的时候也并未特意将元素添加到内部类中，它是在迭代器遍历的时候遍历table数据中的Entry元素，也可以使用foreach遍历(底层也是使用迭代器遍历)，set集合和collection集合中并未提供get()方法，所以不能使用普通for循环来遍历
 *  当链表中的元素大于8时，如果table数组长度小于64，优先对table数组扩容，否则将会把链表转换成红黑树，当红黑树中的节点小于6时，红黑树会还原成链表，这里阙值设置成6而不设置成8是为了避免频繁切换链表和红黑树造成性能的损失
 *  默认的加载因子为0.75，它是在空间上和时间的折中，增大加载因子，能够存储更多的元素，但是查询时会增加开销；减小加载因子，会使查询加快，但是存储同样的元素会使得占用更多的内存空间

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1NjIwNTAx_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/d5158249e614498a9889c95c2ff04f99.png

发表评论取消回复

表情：

评论列表（有 0 条评论，99人围观）

还没有评论，来说两句吧...

相关阅读

相关（源码分析）JDK1.8 HashMap源码分析

目录 * * 成员变量 * 构造方法 * Node<K,V> * TreeNode<K,V> * put(K ...

Myth丶恋晨/ 2024年04月17日 06:24/ 0 赞/ 100 阅读

相关 HashMap JDK7源码分析

概述 HashMap是基于哈希表(散列表)，实现Map接口的双列集合，数据结构是“链表散列”，也就是数组+链表，key唯一的value可以重复，允许存储null 键nu

ゝ一纸荒年。/ 2022年12月30日 08:26/ 0 赞/ 302 阅读

相关 HashMap JDK8 源码分析

概述 HashMap是基于哈希表(散列表)，实现Map接口的双列集合，数据结构是“链表散列”，也就是数组+链表，key唯一的value可以重复，允许存储null 键nu

朱雀/ 2022年12月30日 08:13/ 0 赞/ 313 阅读

相关【Java源码分析】HashMap源码分析

类的定义 public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>

谁践踏了优雅/ 2022年09月23日 09:00/ 0 赞/ 383 阅读

相关 HashMap源码分析

[https://mp.weixin.qq.com/s/lgYpJhKHoKh3avjPux6Rvg][https_mp.weixin.qq.com_s_lgYpJhKHoKh

小灰灰/ 2022年05月26日 07:15/ 0 赞/ 392 阅读

相关 HashMap源码分析

作为Collection集合类中的一个重要成员，HashMap无论在应用、笔试还是面试中都占了很大的比例，纵观网上的源码分析，很多都基于了JDK 1.8以前的版本进行了分析，但

布满荆棘的人生/ 2022年05月23日 02:28/ 0 赞/ 362 阅读

相关 hashmap源码分析

文章目录 hashmap源码分析简介 hashmap数据结构 hashmap的数据结构实现桶，链表的

我不是女神ヾ/ 2022年05月22日 07:56/ 0 赞/ 340 阅读

相关 JDK11源码--HashMap源码分析

文章目录欢迎关注本人公众号概述 hashmap数据结构基本参数 \`MAXIMUM\_CAPACITY\`为什么设置成1 <<

ゝ一纸荒年。/ 2022年03月16日 04:50/ 0 赞/ 409 阅读

相关 JDK源码分析－－Properties源码分析

注：以下分析基于JDK1.8.0\_74。一、概述 1、Properties类表示一组持久属性。属性列表中的每个键及其对

深碍√TFBOYSˉ_/ 2022年02月27日 03:38/ 0 赞/ 536 阅读

相关（源码分析）JDK1.7 HashMap源码分析

目录成员变量：构造方法 Entry<K,V> put(K key, V value) get(K

喜欢ヅ旅行/ 2021年10月19日 06:28/ 0 赞/ 561 阅读