Java中的Map HashMap类

2022-09-13 13:27:13

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

概述

       在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;
    }
  • 作者:灵颖桥人
  • 原文链接:https://blog.csdn.net/qq_22076345/article/details/106251406
    更新时间:2022-09-13 13:27:13