jdk1.8中HashMap

「爱情、让人受尽委屈。」 2022-12-16 10:56 143阅读 0赞

jdk1.8中底层数据结构使用数组+链表+红黑树  
查看源码定义

public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable { 
    
        private static final long serialVersionUID = 362498820763181265L;
    
        /** * The default initial capacity - MUST be a power of two. */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始容量 16
    
        /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */
        static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量2^30
    
        /** * The load factor used when none specified in constructor. */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认负载因子
    
        /** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. */
        static final int TREEIFY_THRESHOLD = 8;//链表转换为红黑树的阈值，也就是8个结点及以上转换为红黑树
    
        /** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */
        static final int UNTREEIFY_THRESHOLD = 6;//红黑树转换为链表的阈值，<=8，红黑树转换为链表
    
        /** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. */
        static final int MIN_TREEIFY_CAPACITY = 64;//红黑树的最小容量
    
        /** * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */
        static class Node<K,V> implements Map.Entry<K,V> { //存储结点
            final int hash;//hash值
            final K key;//key
            V value;//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;
            }

先看构造方法

/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */
        public HashMap(int initialCapacity, float loadFactor) { 
            if (initialCapacity < 0)//初始容量<0,抛出不合法初始容量异常
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)//初始容量>最大容量(2^30)
                initialCapacity = MAXIMUM_CAPACITY;
            if (loadFactor <= 0 || Float.isNaN(loadFactor))//负载因子<=0或负载因子不是合法浮点数
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
            this.loadFactor = loadFactor;//设置负载因子
            this.threshold = tableSizeFor(initialCapacity);//返回与initialCapacity最近的>=initialCapacity的2的整数次幂
          
        }
    
        /** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity. * @throws IllegalArgumentException if the initial capacity is negative. */
        public HashMap(int initialCapacity) { 
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
        /** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). */
        public HashMap() { 
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }
    
        /** * Constructs a new <tt>HashMap</tt> with the same mappings as the * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with * default load factor (0.75) and an initial capacity sufficient to * hold the mappings in the specified <tt>Map</tt>. * * @param m the map whose mappings are to be placed in this map * @throws NullPointerException if the specified map is null */
        public HashMap(Map<? extends K, ? extends V> m) { 
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            putMapEntries(m, false);
        }

然后看一下tableSizeFor方法

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;
            //比如有一个二进制数0100 0000 0000 0000 0000 0000 0000 0000
        //执行n|=>>1 执行后变为0110 0000 0000 0000 0000 0000 0000 0000
        //执行n|=>>2 执行后变为0111 1000 0000 0000 0000 0000 0000 0000
        //执行n|=>>4 执行后变为0111 1111 1000 0000 0000 0000 0000 0000
        //执行n|=>>8 执行后变为0111 1111 1111 1111 1000 0000 0000 0000
       //执行n|=>>16 执行后变为0111 1111 1111 1111 1111 1111 1111 1111
       //即该方法使得最高位及后面的位都变为了1
        }

然后看put方法

public V put(K key, V value) { 
            return putVal(hash(key), key, value, false, true);
        }

然后看一下hash方法

static final int hash(Object key) { 
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//先通过hashCode方法计算出一个hash值，再将该值与该值的右移16做运算，比如计算出的hashCode为0101 0000 1000 1100 0000 0000 0001 0001
     //h 0101 0000 1000 1100 0000 0000 0001 0001
     //^
     //h^16 0000 0000 0000 0000 0101 0000 1000 1100
     //result 0101 0000 1000 1100 0101 0000 1001 1101
          //这样得出的结果再与length-1(因为很多时候length非常小，所以这使得hashcode只有低位参与运算，所以冲突会很多) 进行&操作时候，就使得hashcode的高位也参与运算，通过这种方法大大降低hashCode的散列型，使得与length-1进行&运算的随机性增加
          //为什么用^不用&或|,因为用&或|会偏向0或1，随机性不强，使用^比较均匀
        }

然后看一下putVal方法

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)//tab位null时候或tab长度位0时候
                n = (tab = resize()).length;//扩容并获取新长度
            if ((p = tab[i = (n - 1) & hash]) == null)//(n - 1) & hash的到一个数组下标i，tab[i]为null时候，也就是tab[i]位置没有元素时候
                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))))//要put结点的key等于当前结点的key
                    e = p;
                else if (p instanceof TreeNode)//如果p是红黑树
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else { 
                    for (int binCount = 0; ; ++binCount) { //计算链表结点数目，遍历链表
                        if ((e = p.next) == null) { //当遍历到链表结尾时候，此时肯定没有该key
                            p.next = newNode(hash, key, value, null);//在尾部插入一个结点，尾插法
                            if (binCount >= TREEIFY_THRESHOLD - 1) // 链表结点>=7，引入以及插入了一个新的结点，所以就是>=8时候
                                treeifyBin(tab, hash);//链表转换为红黑树
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))//如果该结点存在key
                            break;
                        p = e;
                    }
                }
                if (e != null) {  //存在key时候
                    V oldValue = e.value;//保存旧值
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;//替换旧值
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            if (++size > threshold)//如果添加了元素且当前key-value的数量>=threadshold
                resize();//扩容
            afterNodeInsertion(evict);
            return null;
        }

然后看一下resize扩容方法代码

final Node<K,V>[] resize() { 
            Node<K,V>[] oldTab = table;//保存旧table
            int oldCap = (oldTab == null) ? 0 : oldTab.length;//保存table长度
            int oldThr = threshold;//保存旧table阈值
            int newCap, newThr = 0;
            if (oldCap > 0) { 
                if (oldCap >= MAXIMUM_CAPACITY) { //>=最大容量2^30
                    threshold = Integer.MAX_VALUE;//threshold为0x7fffffff
                    return oldTab;
                }
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)//新容量的两倍小于最大容量2^30
                    newThr = oldThr << 1; // 新的threshold变为旧table threadshold的两倍
            }
            else if (oldThr > 0) // initial capacity was placed in threshold，oldCap==0时候且oldThr>0，也就是null table时候
                newCap = oldThr;
            else {                // zero initial threshold signifies using defaults oldThr==0时候吗，使用默认容量和threshold
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) { //新threshold为0，//threshold=newCap * loadFactor
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            threshold = newThr;
            //通过以上oldTab，threshold的判断就得到了newCap，newThr
            @SuppressWarnings({ "rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//new新的数组
            table = newTab;//把新数组赋给table
            if (oldTab != null) { 
                for (int j = 0; j < oldCap; ++j) { //遍历旧数组
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) { //如果当前结点不为null
                        oldTab[j] = null;//将oldTab[j]置为null，便于gc
                        if (e.next == null)//只有一个结点的时候
                            newTab[e.hash & (newCap - 1)] = e;//直接将当前结点赋给newTab[i]
                        else if (e instanceof TreeNode)//如果e是红黑树
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);//在红黑树插入一个结点
                        else {  // preserve order，如果是链表且>1个结点
                            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;//返回新数组容量
        }