HashMap源码详解

标签: Java

保留所有版权,请引用而不是转载本文(原文地址 https://yeecode.top/blog/01/ )。

HashMap是Java开发中常用的一种数据接口,常用于完成key:value结构的存储。而同时,HashMap又是HashSet、HashTable、ConcurrentHashMap这三种数据结构的基础。

本篇文章我们详细分析HashMap的源码,后面我们会在此基础上介绍HashSet、HashTable、ConcurrentHashMap的源码,并比较他们与HashMap的异同。

1 基本结构

HashMap使我们非常常用的一种数据结构,常用来存储各种键值数据。同时,它也是最为简单的。这里我们的讲解以Java 1.8 为例。

HashMap的结构示意图如下: 图片

1.1 动态数组

我们先看最上层。

通过结构图我们看出,HashMap就是一个可以扩容的动态数组。考虑到扩容的需要,该动态数组有着以下属性:

1.2 数组元素

数组中的每个元素是一个Node,它的属性有:

1.3 列表或者树

对于每个Node元素,我们发现它有一个next属性。而通过它,挂载到数组同一个位置的多个Node就组成了列表或者树。

在Java1.7阶段,是不存在树的,即挂载到数组同一个位置的多个Node通过next属性构成了一个单向链表。

而在Java1.8中,当单项链表中元素大于等于8时,单项列表会变为一棵树。该树为红黑树。该转化操作是由final void treeifyBin(Node[] tab, int hash)函数实现的。

因为链表的查找时间复杂度为O(N),而红黑树查找的时间复杂度为 O(logN)。因此,在数组的同一位置挂载的节点较多时,Java1.8的设计会降低时间复杂度。

2 初始化操作

HashMap的初始化操作非常简单,就是确定initialCapacity,loadFactor的初始值的过程。

平时,我们调用无参构造函数public HashMap()时,所有的值会采用默认值。即loadFactor=0.75。

如果我们传入initialCapacity,loadFactor,则会调用下面的方法。

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);
    }

但是有一点要注意,在进行初始化操作时,只是初始化了创建数组的相关参数,并没有真正创建动态数组。真正动态数组的创建是在第一次进行数据写入时引发的。

这样实际上是一种懒加载操作,防止了初始化后而不用的内存浪费。

3 数据写入操作

向HashMap中写入数据的过程,简单总结起来分为这么几步:

实际的操作要比这些复杂以下,我们直接结合源码进行分析。相关关键步骤我添加了注释。

// 供外部调用的方法
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }


final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 这里如果发现动态数组为null则会初始化数组。因此第一次放入值时会在这里初始化数组
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 通过hash发现要放入的元素的数组位置为null,则直接把该元素放在这里即可
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 如果要放入的位置已经有元素了
        Node<K,V> e; K k;
        // 判断原位置第一个元素是否和新元素key完全一致
        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 {
            // 说明是列表,按照列表方法放入新节点
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 如果放入列表后列表过长,则将列表转为红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                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;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

4 数据读取操作

相比于数据写入,数据读取操作要简单一些。总体过程总结为:

到达任何一步发现没有结果,则说明key在map中不存在,直接返回null即可。

代码和相关注释如下:

// 供外部调用的方法
public V get(Object key) {
        Node<K,V> e;
        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;
    // 判断数组存在且不为空,否则直接返回null
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            // 第一个节点key与要查找的完全一致
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 第一个节点key与要查找的不一致
            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;
}

5 扩容操作

谈数组扩容之前,我们先带着一个疑问:为什么数组大小必须是2^n?

我们知道扩容分两步:

第一步操作只需增加一块存储区域而已,而第二步操作则需要消耗巨大的计算资源。如果扩容前已经存在5万个元素,则需要把这5万个元素的hash值重新计算一遍,并根据新的结果移动它的位置。该操作叫做重哈希操作,是一次代价极高的操作。

因此,能提升重哈希的性能变得非常重要。

而数组大小必须是2^n,就可以提升重hash的性能。这是一个数学问题。我们一步步来分析。

5.1 哈希与重哈希

无论是读还是写,我们每次都要用到hash,那HashMap中所用的hash函数是怎样的呢?

它就是:

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

最终,我们得到一个int数字。而这个数字最终要被映射到数组的某个位置i。

数组长度为n,则i的计算为:

tab[i = (n - 1) & hash]

该计算在HashMap源码中出现了多次。

(n-1)为数组中的最大位置,hash为哈希的结果,两者进行了逻辑与操作。我们到二进制中去理解,那逻辑与操作我们可以理解为hash值的二进制数在(n-1)的二进制数上的求交集操作,我们即为p。最终得到的结果肯定小于等于(n-1)。

那在扩容时,n变为原来的两倍大小,记为m。那在二进制上,m就相当于在n的二进制基础上高位增加了一个1。那么,hash的二进制数和m的二进制数求交集后结果记为q。则除了最高位以外,q和hash值的二进制数在(n-1)的二进制数上的求交集的结果p是一致的。因此,q要么等于p,要么等于p+n。

以上两段的结论简单说来就是:设原来table的长度为a,扩展后变为b,且b=2a。则会将原来table[i]中的元素,经过重hash后,会分拆到新的数组newTable[i]和newTable[i+a]这两个位置上。因此,这样就减少了计算和移动量。

5.2 扩容

解决了这个疑问之后,我们可以直接根据HashMap源码查看扩容操作。

但是因为相关源码比较长,我进行了相关的删减。

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) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 如果长度过长,则不进行扩展
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        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 = newTab;
    if (oldTab != null) {
        // 轮询操作,对所有元素重哈希
        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)
                    // 树元素重hash
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 略:链表元素重hash
                }
            }
        }
    }
    return newTab;
}

6 总结

HashMap是Java中常用的类,本文HashMap的结构和源码进行了详细的梳理和分析。包括HashMap的数据结构、数据存取、数据写入、扩容等方法。

接下来的文章我们会在此文基础上介绍HashSet、HashTable、ConcurrentHashMap的源码,并比较他们与HashMap的异同。

本文首发于个人知乎:易哥(https://www.zhihu.com/people/yeecode),欢迎关注。

作者书籍推荐