JDK8中HashMap的工作原理剖析

不念不忘少年蓝@ 2022-06-01 12:42 182阅读 0赞

在Java语言里，HashMap无疑是使用频率非常高的一个类，了解它的内部实现将有助于更好的使用它。

在jdk8中的HashMap是由三种数据结构组成：数组 + （ 链表 or 红黑树 ）

图示如下：

![image][]

而在jdk8之前还只是数组+链表两种数据结构，在这里简单提下数组和链表的区别：

数组

优点：物理地址连续+按下标随机访问效率高O（1）

缺点：插入，删除效率低，

链表

优点：存储地址不连续，可灵活的扩展自己的长度，插入，删除效率高

缺点：访问效率低O（n）

而哈希表（Hash类数据结构）正是结合了两者的优点，而衍生出来的的一种高效的数据存储结构，本质上是采用空间换时间的方式，提高了读写的效率。

HashMap的继承结构如下：

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

这里我们能发现HashMap中K，V都是泛型的，所以可以支持任何类型作为key或者value，但实际开发中用的最多的都是以String类型的字符串作为key。

在这里泛型Key的hashCode和equals方法非常重要，因为它们会影响HashMap存储的数据分布和读写是否正确

上面说过HashMap可以看成是一个大的数组，然后每个数组元素的类型是Node类型，源码里定义如下：

transient Node<K,V>[] table;

注意Node类还有两个子类：TreeNode和Entry

TreeNode<K,V> extends Entry<K,V> extends Node<K,V>

上图中的链表就是Node类，而红黑树正是TreeNode类

接着我们来看下HashMap的一些成员变量：

//默认table数组buckets的数目，必须是2的平方，默认值是16
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    
        //默认table最大的长度约10亿多(1073741824)最大的buckets数目
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        //默认负载因子
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        //当单个链表的个数超过8个节点就转化为红黑树存储
        static final int TREEIFY_THRESHOLD = 8;
    
        //如果原来是红黑树，后来被删除一些节点后，只剩小于等于6个，会被重新转成链表存储
        static final int UNTREEIFY_THRESHOLD = 6;
    
        //当数组的长度（注意不是map的size而是table.length）大于64的时候，
        //会对单个桶里大于8的链表进行树化
        static final int MIN_TREEIFY_CAPACITY = 64;
        
        //用来实现遍历map的set,依次遍历table中所有桶中的node或者treeNode
        transient Set<Map.Entry<K,V>> entrySet;
    
        //当前存储的实际数据量=map.size而不是table.length
        transient int size;
    
        //修改次数，用来判断是否该map同时被多个线程操作，
        //多线程环境下会抛出异常ConcurrentModificationException
        transient int modCount;
    
        //当前数组中的阈值 table.length * loadFactor，如果超
        //过这个阈值，就要进行扩容 (resize)
        int threshold;
    
        //负载因子
        final float loadFactor;

成员变量主要两部分组成，一部分是处理化时候的常量，一部分是变量会在运行时改变，这里还需要注意的是HashMap本身不是线程安全的，所以尽量避免在多线程环境下使用，如果非要使用，就用线程安全的Map，如下：

` （1）Map m = Collections.synchronizedMap(new HashMap(...)) 
      （2）ConcurrentHashMap map=new ConcurrentHashMap();

此外，HashMap还有几个构造方法：

`   //1
     `   public HashMap() { 
            this.loadFactor = DEFAULT_LOAD_FACTOR; 
        }
        
        
        //2
         public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
         
         //3
            public HashMap(Map<? extends K, ? extends V> m) {
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            putMapEntries(m, false);
        }
        
        //4
            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);
        }

（1）第一个是默认的构造方法，我们看到只对影响扩容负载因子做了初始化，默认是0.75

（2）第二个和第四个其实是一个方法逻辑，可以传入指定的table数组的大小，负载因子用默认的。

（3）第三个可以传入一个Map集合直接赋值给该map，里面用了putMapEntries方法，这个方法可以理解为迭代传入的Map然后将数据赋值给new的Map

（4）第四个是同时指定初始化table数组的大小和负载因子，中间有一些逻辑判断，这里需要提下tableSizeFor这个方法：

源码如下：

/**
         * Returns a power of two size for the given target capacity.
         */
        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;
        }

这个方法，保证指定的设置的table数组的长度必须是2的n次方，比如你初始化传入的是5，但是实际运行后你会发现table数组的长度是8，这是因为2的n次方，对于数组的扩容和重新赋值有比较大的好处，所以如果你传入的不是2的n次方，那么经过这个方法出来的值一般都是大于你传入的参数最接近的2的n次方。

下面我们看下HashMap是如何存数据的？

源码中的put方法如下：

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

这里我们看到put方法里面调用了hash方法，来得到该key的hashCode，那么我们来看下其内部是如何实现的：

static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

这里能看到hash方法并不是直接取的hashCode值，而是用hashCode()的高16位异或低16位实现的，这么做可以保证高低bit位都能参与到Hash的计算中，一句话就是为了减少hash冲突的几率。

然后在putVal方法中，实现数据的插入操作，注意数组的下标的计算方式是：

i = (table.length - 1) & hash

等价于使用转化后hash值对数组长度取模

h % table.length

但是位运算比模运算效率更高

在putVal插入数据的方法中，第一次会调用扩容方法，此外插入时还会判断该节点是链表还是红黑树，他们分别对应不同的赋值方法，并且如果单个bucket的节点数量大于8，还会将链表转化为红黑树，在插入完成后还会继续判断下一次是否需要扩容。

这里重点介绍下扩容方法：

final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = table;
            //上一次table的长度赋值
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            //阈值等于当前成员变量的值
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) {
                if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                //否则就将cap和thr进行*2扩容  
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; 
            }
            else if (oldThr > 0) //如果旧table没有初始化，就把阈值作为table的长度
                newCap = oldThr;
            else { //第一次没有传入任何构造函数时，table.length=16
                newCap = DEFAULT_INITIAL_CAPACITY;
                //阈值=16*0.75=12
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) {
            	//如果新的阈值等于0，那么会根据新的table.length和负载因子，重新计算
            	//并判断是否超过最大值，如果超过就取最大值
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            //将新计算的阈值，重新赋值给成员变量
            threshold = newThr;
            @SuppressWarnings({
       "rawtypes","unchecked"})
            //用新的table的大小，构造一个数组
                Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;//赋值给成员变量
            if (oldTab != null) {
            	//将旧table中的数据给重新计算到新table数组中
                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 { // preserve order
                        	//表示原链表中的node位置，要么不变要么是table[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;
                            }
                        }
                    }
                }
            }
             //返回扩容后的新table数组
            return newTab;
        }

注意，扩容后的table数组的长度，一定是2的n次方。

最后我们来看下get方法：

public V get(Object key) {
            Node<K,V> e;
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }

可以看到get方法也同样调用了hash方法获取hashCode，接着调用了getNode方法：

final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            //判断table不等于null，table.length必须大于0
            //然后同样通过位运算得到数组访问的下标接着从数组中取的第一个元素
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
            	//如果hash值相等，key相等，并且key不等于null，检索的key等于第一个元素的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);
                }
            }
            //如果最终还没有找到就返回null
            return null;
        }

HashMap读取的效率：

（1）如果在第一个节点命中，那就是O(1)

（2）如果在红黑树中查询，那就是O(logn)

（3）如果是在链表中查询，那就是O(n)

在这里，我们就会发现红黑树的结构的引入，其实是为了提升检索效率。

注意上面查询过程中还有一个小细节，就是判断key是否null，因为在HashMap中其key和value 都可以允许为null值，有时候你get一个null值出来，可能会有两种情况，那么value就是null， 要么是因为你的key传入的是null，而刚好这个null这个key，对应的value也是null。

演示的代码如下：

HashMap<String, Integer> map=new HashMap<String, Integer>();
            map.put(null, null);//k和v都允许为null
            map.put("5", null);
           
           //判断是否存在null的key
            System.out.println(map.containsKey(null));
            
            System.out.println(map.get(null));//null
            System.out.println(map.get("5"));//null

这里可以通过containsKey方法判断是否有null的key

总结：

本文对JDK8中的HashMap的工作原理做了一个剖析，并介绍了一些核心的方法和注意事项，通过了解它的内部运行机制，以帮助我们更加合理的在实际开发中使用。

参考文章：

[https://www.jianshu.com/p/aa017a3ddc40][https_www.jianshu.com_p_aa017a3ddc40]

[https://www.geeksforgeeks.org/internal-working-of-hashmap-java/][https_www.geeksforgeeks.org_internal-working-of-hashmap-java]

[https://www.cdn.geeksforgeeks.org/java-util-hashmap-in-java/][https_www.cdn.geeksforgeeks.org_java-util-hashmap-in-java]

[https://www.javacodegeeks.com/2017/11/java-hashmap-detail-explanation.html][https_www.javacodegeeks.com_2017_11_java-hashmap-detail-explanation.html]

[http://blog.csdn.net/zxt0601/article/details/77413921][http_blog.csdn.net_zxt0601_article_details_77413921]

[http://lingmeng.github.io/archives/][http_lingmeng.github.io_archives]

[image]: https://note.youdao.com/yws/public/resource/c79695db6fcca007cbfa03f7080f8a58/xmlnote/53F21FD98C2F4E8792A18789FFAD93A5/40723
[https_www.jianshu.com_p_aa017a3ddc40]: https://www.jianshu.com/p/aa017a3ddc40
[https_www.geeksforgeeks.org_internal-working-of-hashmap-java]: https://www.geeksforgeeks.org/internal-working-of-hashmap-java/
[https_www.cdn.geeksforgeeks.org_java-util-hashmap-in-java]: https://www.cdn.geeksforgeeks.org/java-util-hashmap-in-java/
[https_www.javacodegeeks.com_2017_11_java-hashmap-detail-explanation.html]: https://www.javacodegeeks.com/2017/11/java-hashmap-detail-explanation.html
[http_blog.csdn.net_zxt0601_article_details_77413921]: http://blog.csdn.net/zxt0601/article/details/77413921
[http_lingmeng.github.io_archives]: http://lingmeng.github.io/archives/