Java中的Map【七】HashMap类

Dear 丶 2021-09-21 07:46 374阅读 0赞

**      所使用的jdk版本为1.8.0\_172版本**，先看一下 HashMap<K,V> 在JDK中Map的UML类图中的主要继承实现关系：

## ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMDc2MzQ1_size_16_color_FFFFFF_t_70][] ##

# 概述 #

在JDK 1.7 中，HashMap的底层数据结构使用的是 Entry数组 + Entry链表，如果HashMap中的key的hashCode都一样（极端hash碰撞情况）, 那所有数据就会一直都落在同一条Entry链表上, 此时设计初衷为实现快速查找的HashMap就退化为链表, 操作的时间复杂度成为O(n)。JDK 8 中采用 Node数组 + Node链表 + TreeNode 红黑树，优化了极端hash碰撞情况下的查询效率，最坏时间复杂度为O(log n)。

HashMap 的实现**不是同步的**，即线程不安全的。HashMap **允许使用 null 作为键和值**。

# 数据结构 #

## Node<K,V> ##

static class Node<K,V> implements Map.Entry<K,V> {
            //hash值，hash(key)方法计算得出(key.hashCode和扰动函数得出)
            final int hash;
            //键
            final K key;
            //值
            V value;
            //指向下个Node节点的引用
            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;
            }

## TreeNode<K,V> ##

/**
         * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
         * extends Node) so can be used as extension of either regular or
         * linked node.
         */
        /**
         * 红黑树节点
         * 红黑树性质：
         * 1.节点是红色或黑色。
         * 2.根节点是黑色。
         * 3.每个叶子节点都是黑色的空节点（NIL节点）。
         * 4 每个红色节点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
         * 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
         */
        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;    // needed to unlink next upon deletion
            boolean red;
            TreeNode(int hash, K key, V val, Node<K,V> next) {
                super(hash, key, val, next);
            }
    
            //.......

注意到 TreeNode<K,V> 继承了LinkedHashMap 中的 Entry<K,V>，而该 Entry<K,V> 类又继承了 HashMap 中的Node<K,V>（即上面的 Node<K,V>类）：

/**
         * HashMap.Node subclass for normal LinkedHashMap entries.
         */
        static class Entry<K,V> extends HashMap.Node<K,V> {
            Entry<K,V> before, after;
            Entry(int hash, K key, V value, Node<K,V> next) {
                super(hash, key, value, next);
            }
        }

## Node<K,V>\[\] ##

/**
         * The table, initialized on first use, and resized as
         * necessary. When allocated, length is always a power of two.
         * (We also tolerate length zero in some operations to allow
         * bootstrapping mechanics that are currently not needed.)
         */
        /**
         * Node[]数组table在首次使用时初始化，并且根据需要调节大小。
         * 分配大小后，长度总是2的幂。
         * 长度总是2的幂好处：(n - 1) & hash 计算key将被放置的槽位，n 为 table 长度；比 %取模运算效率高
         * （在某些操作中，我们还允许长度为零，以允许使用当前不需要的引导机制。）
         */
        transient Node<K,V>[] table;

# 构造方法 #

HashMap 中提供了四种构造方法：

//默认构造方法，使用默认的加载因子
        public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }
    
        //构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap
        public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
        /**
         *  构造一个带指定初始容量和加载因子的空 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;
            //根据初始容量计算数组下一次触发resize的阈值
            this.threshold = tableSizeFor(initialCapacity);
        }
    
        //构造一个映射关系与指定 Map 相同的新 HashMap
        public HashMap(Map<? extends K, ? extends V> m) {
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            putMapEntries(m, false);
        }

HashMap触发数组下一次 resize 扩容操作的阈值 threshold = capacity(容量) \* load factor（加载因子），HashMap中的映射元素总数超过threshold时，就会触发 resize 扩容操作。

### tableSizeFor方法 ###

/**
         * Returns a power of two size for the given target capacity.
         */
        /**
         * 返回一个比给定整数大且最接近的2的幂次方正整数
         * 原理：通过不断把第一个1开始后面的位变成1，再返回 n + 1,即为2的幂
         */
        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;
        }

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

/**
         * 在此映射中关联指定值与指定键。如果该映射以前包含了一个该键的映射关系，则旧值被替换。
         *
         * @param key 键
         * @param value 值
         * @return 与 key 关联的旧值；如果 key 没有任何映射关系，则返回 null。（返回 null 还可能表示该映射之前将 null 与 key 关联。）
         */
        public V put(K key, V value) {
            //hash(key)：调用扰动函数计算hash值
            return putVal(hash(key), key, value, false, true);
        }
    
        /**
         * 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.
         * @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;
            //通过resize()方法初始化table
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            //(n - 1) & hash 相当于 hash % n；如果数组中该位置为null，即没有被使用，直接构造新的Node节点放入
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {//如果数组中的该位置已经被占用
                Node<K,V> e; K k;
                //如果链表的第一个节点或者树的根节点的key与待放入的key相同，
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;//用一个临时节点e记录
                //如果数组table中的位置不是该键，并且数组中的节点是红黑树节点，则按红黑树节点处理
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                //如果数组table中的位置不是该键，并且数组中的节点是链表结构节点
                else {
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                            //判断链表的长度是否达到了 8 个
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            /*如果数组的长度没有超过64，则进行扩容操作；
                             *如果数组长度超过64，则把冲突的链表结构转换为红黑树结构*/
                                treeifyBin(tab, hash);
                            break;
                        }
                        //如果链表中已经存在了待插入的key，跳出循环
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                //key已经存在的情况，用新值替换旧值，返回旧值
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    //回调方法，提供给 LinkedHashMap 后处理的回调
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            //如果HashMap中映射的数量达到了阈值，则触发扩容操作
            //如果数据量很大，扩容的时间开销不可忽略，要考虑到。
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);//提供给LinkedHashMap使用的回调，这里为空实现
            return null;
        }

## treeifyBin方法 ##

当链表长度大于 8 的时候，会进到terrifyBin（）方法中：

/** 
         * 前提：链表的长度超过了 8  
         * 如果数组的长度没有超过64，则进行扩容操作；
         * 如果数组长度超过64，则把冲突的链表结构转换为红黑树结构
         */
        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);
            }
        }

# 扩容方法 resize() #

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) {
                //扩容前数组长度超过最大值，2^30;此时数组已经很大，不再扩容
                if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                //如果旧数组长度超过了默认容量16，并且旧数组长度的二倍不超过 2^30
                //则把新数组长度设为旧数组长度二倍
                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
                //默认构造方法创建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
            threshold = newThr;
            @SuppressWarnings({"rawtypes","unchecked"})
                Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;
            //扩容后，对新扩容后的table赋值，重新计算元素新的位置
            //扩容时数组长度由2的n次幂变为2的n+1次幂, 而hash根据2的n+1次幂取模的值即是hash转为二进制后的后n位,
            // 所以如果hash的第n位(可用hash & 旧数组长度计算)为0的话数据在扩容后新数组中的位置就和在旧数组中的位置相同, 为1的话数据在扩容后新数组中的位置就是(原位置+旧数组长度位置).
            // 扩容时旧数组在 j 位置上的数据会根据hash的第n位是0还是1拆分为2组, 然后把为0的放到新数组的j位置, 为1的放到 j+旧数组长度位置
            if (oldTab != null) {
                for (int j = 0; j < oldCap; ++j) {
                    Node<K,V> e;
                    //判断当前遍历下的该node是否为空，将j位置上的节点保存到e, 然后将oldTab[j]置为空。
                    if ((e = oldTab[j]) != null) {
                        oldTab[j] = null;
                        //旧数组上的普通节点（没有后缀节点），根据e.hash & (newCap - 1)计算出它在新数组上的位置
                        if (e.next == null)
                            newTab[e.hash & (newCap - 1)] = e;
                        //旧数组上节点已经是红黑树节点的情况：
                        //把旧数组的红黑树节点数据按照上面的逻辑计算位置（得到两个红黑树）重新树化，
                        //如果新树的节点数量 <= UNTREEIFY_THRESHOLD （默认为 6），则把树结构降为链表
                        else if (e instanceof TreeNode)
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else { // preserve order
                            //旧数组节点为链表节点的情况：
                            //上面所述，用e.hash & oldCap得到hash值的第n位，拆成为0和1的两个链表，对应放到原位置j和新位置（j + oldCap）
                            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;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMDc2MzQ1_size_16_color_FFFFFF_t_70]: /images/20210920/d709e6eab4fc4a7bb9f8cc7e9bd2132c.png