HashMap 原理及源码分析

HashMap 原理及源码分析 1. 存储结构

HashMap 内部是由 Node 类型的数组实现的。Node 包含着键值对，内部有四个字段，从 next 字段我们可以看出，Node 是一个链表。即数组的每一个位置被当作一个桶，每个桶存储一个链表。HashMap 使用拉链法来解决冲突，同一个桶中存放 hashcode 与数组长度取模运算结果相同的 Node。

static class Node implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Node next;

    Node(int hash, K key, V value, Node next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(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;
    }
}

2. 索引计算

在 HashMap 中，node 在数组中的索引根据 key 的哈希值与数组长度取模运算得到。

如下为 HashMap 中 putVal 方法（put方法的实际执行过程），

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; Node p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // ...
}

可以看到第6行中

i = (n - 1) & hash

其中 i 即为根据 key 计算得到的索引，n 为数组的大小。

这是因为在 HashMap 中, 数组的大小为 2 n 2^n 2n, 则其二进制形式具有如下特点：

令 x = 1 << 4，即 x 为 2 的 4 次方

x   : 0001 0000
x-1 : 0000 1111

令一个数 y 与 x - 1 取与

y   	: 1101 1011
x-1 	: 0000 1111
y&(x-1)	: 0000 1011

这个性质和 y 对 x 取模效果是一样的

y   	: 1101 1011
x	 	: 0001 0000
y%x		: 0000 1011

我们知道，位运算的代价比求模运算小的多，因此使用这种计算时用位运算能够带来更高的性能。

3. put 操作

HashMap 中 put 方法实际执行的是 putVal 方法。

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

下面为 putVal 方法的实现，为了更好的理解 put 操作，源码中有关红黑树及扩容的部分，先使用省略号代替。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; Node p; int n, i;
    // map 刚构造并且未添加元素时，数组为 null，需要进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 计算索引，若索引位置的桶为空，则将其放入桶中
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node e; K k;
        // 若桶的头节点的 key 与要插入的 key 相同，将其赋给 e（e 为需要更新的节点）
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
		// ...
        else {
            // 遍历桶中的链表
            for (int binCount = 0; ; ++binCount) {
                // 如果到达链表尾部，即 map 中不存在该 key 的节点，则将其添加到尾部
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // ...
                    break;
                }
                // 如果在遍历过程中存在 key，则将其赋给 e
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // e 不为空，说明 map 中存在该 key，更新其 value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
	//...
}

总结

put 操作主要步骤为：

遍历该索引位置的桶中元素，比较桶中元素 key 是否与该 key 相同，若相同则更新其 value若桶中不存在该 key，则新建一个 node 放入桶中

4. 扩容

设 HashMap 中数组的长度为 n, 存储的键值对数量为 m, 在哈希函数满足均匀性的前提下，每个链表长度为 m / n。因此查找的时间复杂度为 O(m / n)。

为了减小查找效率，即减小 m / n, 则应该增大 n，即数组的长度。HashMap 使用动态扩容的方式来根据当前键值对的数量，来调整数组的大小，是得空间和时间效率都能得到保证。

和扩容相关的参数主要有：capatity、size、threshold 和 loadFactor

参数	含义
capacity	table 数组的大小，默认为 16
size	键值对数量
threshold	size 的临界值，当 size 大于 threshold 时就必须进行扩容操作
loadFactor	装载因子，默认为 0.75，table 能够使用的比例 threshold = (int) (capacity * loadFactor)

扩容操作在 putVal 中，有两种情况会触发

map 初始时，数组大小为 0，需要扩容当键值对数量超过临界值时，触发扩容

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; Node p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length; 
    // ...
	if (++size > threshold)
        resize(); 
    // ...
}

扩容主要分为两步

对数组容量进行扩容扩容后需要原来数组的所有键插入到新的数组中

final Node[] resize() {
    Node[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 1. 进行扩容
    if (oldCap > 0) {
        // 若容量大于等于最大容量，则无法扩容，将临界值改为 int 的最大值，并返回（因为没有扩容无需重新插入键）
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 容量扩大到原来的两倍，并将临界值修改到原来的两倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; 
    }
    else if (oldThr > 0) // 若数组大小为 0，临界值不为 0，则数组初始大小为临界值（tableSizeFor 方法保证 oldThr 为 2 的 n 次方，下一节介绍）
        newCap = oldThr;
    else {  // 若数组大小为 0，临界值为 0，则初始大小为 16，初始临界值 = 0.75 * 16 = 12
        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;
    Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    // 2. 重新插入键
    if (oldTab != null) {
        // 遍历旧的数组
        for (int j = 0; j < oldCap; ++j) {
            Node 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)e).split(this, newTab, j, oldCap);
                else { // 遍历链表
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node 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;
}

5. 保证数组容量为 2 n 2^n 2n

HashMap 的构造函数允许用户传入初始容量，并且可以不是 2 n 2^n 2n。但是 HashMap 可以将其转为 2 n 2^n 2n 。

先考虑如何求一个数的掩码，对于 1000 0000，它的掩码为 1111 1111。可以使用以下方法得到：

mask |= mask >> 1 	1100 0000
mask |= mask >> 2	1111 0000
mask |= mask >> 4	1111 1111

则 mask + 1 是大于原始数字的最小的 2 的 n 次方

HashMap 通过 tableSizeFor 来保证数组容量为 2 的 n 次方

HashMap 原理及源码分析

Java相关栏目本月热门文章