JDK1.8 HashMap源码浅读

目录

1、几个重要的属性

• DEFAULT_INITIAL_CAPACITY
  默认初始容量

     /**
     * The default initial capacity - MUST be a power of two.
     * 默认初始容量，必须为2的幂
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    //每个hashmap的最大容量即数组最大长度
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     * 默认加载因子，先记住这么个属性
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //链表长度大于等于8，转变为红黑树
    static final int TREEIFY_THRESHOLD = 8;
    //链表长度小于等于6，转为链表
    static final int UNTREEIFY_THRESHOLD = 6;
    //红黑树最大可容纳容量
    static final int MIN_TREEIFY_CAPACITY = 64;
    //数组加链表的结构数据
    transient Node<K,V>[] table;
    
    transient Set<Map.Entry<K,V>> entrySet;
    //长度
    transient int size;
   
    transient int modCount;
    //阈值，值为容量*加载因子。此值主要用于扩容，在扩容时，不可能等所有桶都有数据了再去扩容，
    //所以有了阈值，即当前数组可以使用的最大长度
    int threshold;
    //加载因子
    final float loadFactor;

2、结构

  HashMap的结构为数组加链表的形式，而在jdk1.8中，新增了红黑树，结构大概是下图的样子。
  我们可以看到table就是数组，容量默认为16，我们可以把数组中每个存储空间叫做桶。而数组中所存放的就是以Node类型为节点的链表，当某个桶中的链表长度，即数据长度>=8个的时候,HashMap会转换链表为红黑树结构。

3、节点

  上述已经看到HashMap是由数组(桶)+链表构成的，下面是链表中每个节点在HashMap中的定义，Node<K,V>[] table，就是这个结构

//这里实现了一个Map.Entry<K,V>的接口
static class Node<K,V> implements Map.Entry<K,V> {
        //定义当前节点的hash值
        final int hash;
        //key值
        final K key;
        //value值
        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;
        }
        //得到当前节点的key值
        public final K getKey()        { return key; }
        //得到当前节点的value值
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }
        //计算当前节点的hashCode
        public final int hashCode() {
            //通过Object运算key和value的hash值，并作位运算
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
        //设置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;
        }
    }

4、构造方法

  结构有了，属性有了，下面是构造方法开始使用。从下面可以看到3个构造方法

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

    
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    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);
    }

5、put和get方法

  经过上面的介绍，我们已经能大致了解到HashMap结构，以及存放的节点结构，下面就介绍HashMap底层究竟是怎么去存值和取值的。
  首先介绍put方法，其中又夹杂了许多其他核心方法，也一起在下面的源码中解释。

    //首先，当我们去调用put方法时，底层帮我们调用了putVal(hash(key), key, value, false, true)方法
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    //官方参数解释
    @param hash key的hash值
    @param key  键
    @param value  值
    @param onlyIfAbsent 如果为true不能改变已经存在的值
    @param evict 如果为false此表处于创建模式
    //上面的put方法传过来的后两个参数是false和true，即现在可以改变已经存在的值，并且改hashmap处于非创建模式
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //定义一些变量
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //令tab等于此hashmap的节点数组（指的就是hashmap存放节点的存储结构，下文都叫成节点数组），如果为空，或者长度为0，证明此时hashmap中还没有任何数据
        if ((tab = table) == null || (n = tab.length) == 0)
            //那么初始化数据数组，得到长度赋值给n
            n = (tab = resize()).length;
        //当有节点数组，或初始化完毕后，继续判断
        //（n-1）& hash计算出将要把新的节点存放到哪个桶中
        //计算过后，如果当前桶中没有任何的节点，那么直接新建节点存入hash值，key，value，并令后置节点为null（这个是当前桶中无数据的时候，直接新建节点即可）
        //p 当前桶中链表的头节点 
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
       //当前桶中有数据，即为hash冲突。此时需要判断新插入节点的key是否已经在当前桶中的链表节点中存在。
        else {
            Node<K,V> e; K k;
            //既然桶中存在链表，那么先于链表的头节点比较，如果hash和key都相同。令e=头节点
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
                //判断是否为红黑树
            else if (p instanceof TreeNode)
                //通过红黑树规则进行插入节点
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                //如果key不与头节点相同，节点类型也不是红黑树
                //那么循环判断链表中的每个节点
                for (int binCount = 0; ; ++binCount) {
                    //循环过程中，并没有出现相等，并且后面已经没有节点了，直接向链表尾部插入新节点
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //插入后判断是否满足转换红黑树条件（链表长度>=8），这里-1是因为binCount是从0开始算的
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果中间节点key值有相等的，那么跳出循环，此时e指向key值相同的那个节点
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //e经过上面的判断已经有了节点的选择，要么就是在链表中已经存在的节点，要么就是null
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                //不为空的情况，即在原数据上更改值，先判断当前hashmap是否可更改或者原值是否为空
                if (!onlyIfAbsent || oldValue == null)
                //覆盖原有的值
                    e.value = value;
                //LinkedHashMap的回调，不用管
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //不是在元数据上更改值的时候，判断添加后size大于阈值，进行扩容
        if (++size > threshold)
            resize();
        //也是LinkedHashMap的回调     
        afterNodeInsertion(evict);
        return null;
    }

  resize(）方法：resize用于初始化或者扩容hashmap的节点数组，之前讲到过，当桶的使用数量达到阈值的时候，那么就对hash表进行扩容。
  可以参考文章： jdk1.7和jdk1.8的扩容机制

final Node<K,V>[] resize() {
        //用oldTab引用现有的链表数组（指需要扩容或需要初始化的table）
        Node<K,V>[] oldTab = table;
        //得到旧的容量
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //得到旧的阈值
        int oldThr = threshold;
        int newCap, newThr = 0;
        //如果当前链表数组容量>0，证明需要扩容
        if (oldCap > 0) {
        	//大于最大的容量时（此时不能继续增大容量）
            if (oldCap >= MAXIMUM_CAPACITY) {
                //令阈值变为最大（这里为什么只更改了阈值，没有改容量--因为容量已经为最大了，不能再扩容）
                threshold = Integer.MAX_VALUE;
                //直接返回
                return oldTab;
            }
            //未达到最大容量（可以对容量进行扩充）
            //令新的容量等于原来的2倍，判断是否是大于默认容量并且小于最大容量
            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引用newtable
        table = newTab;
        if (oldTab != null) {
            //遍历旧节点数组，将每个桶中的数据移到新的桶中
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //令e等于当前遍历到的桶中的头节点
                if ((e = oldTab[j]) != null) {
                    //e已经引用了头节点，令当前桶为空
                    oldTab[j] = null;
                    //e没有下一个节点，证明当前桶中只有一个节点
                    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
                        //lo和hi把原桶中的链表根据重新计算hash分开成为两个链表
                        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);
                        //上面拆分完毕，lo的链表放在原位处的桶中
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        //hi放在原位置+一倍容量的位置的桶中
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        //扩容并转移数据完毕
        return newTab;
    }

关于桶位置的计算，可以参考HashMap中的hash算法总结
上面数据的put以及节点数组的扩容已经OK,之后进行取值，HashMap的取值也很简单，值是怎么存进去的就怎么取出来就好了

public V get(Object key) {
        Node<K,V> e;
        //底层调用getNode(hash(key), key)方法
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        /*可以从节点数组查到数据的前提是：
          1、当前节点数组不为空
          2、不为空的情况下，长度>0
          3、有长度后，通过hash找到所在位置的桶，桶不为空
        */
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //当前桶中头节点的hash值与所要查询的key的hash相等，并且key值也相等，那么这个头节点就是所要查询的节点，直接返回
            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;
    }

本文地址：https://blog.csdn.net/qq_42768505/article/details/111597804