HashMap源码分析

2019年9月26日 · 阅读需 15 分钟

HashMap是很重要的数据结构，也是面试的宠儿，这里就HashMap的源码进行分析，以便理解HashMap的实现。

散列表

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。散列函数有直接定址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法等。

解决哈希冲突的方法一般有：开放定址法、链地址法（拉链法）、再哈希法、建立公共溢出区等方法。在开放定址法中解决冲突的方法有：线行探查法、平方探查法、双散列函数探查法等。开放定址法的缺点在于删除元素的时候不能真的删除，否则会引起查找错误，只能做一个特殊标记。只到有下个元素插入才能真正删除该元素。

数据结构

在JDK1.8之前，HashMap采用数组+链表实现，即使用链表处理冲突，同一hash值的节点都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值时，将链表转换为红黑树，这样大大减少了查找时间。

类结构

类常量

// 默认初始容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量为2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子是0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表的数量大于等于8个并且桶的数量大于等于64时链表树化
// hash表某个节点链表的数量小于等于6时树拆分
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

实例变量

// hash桶。在第一次放置元素时初始化，必要时进行扩容（不会缩容），长度一直是2的幂次方。
transient Node<K,V>[] table;
// 键值对的数量
transient int size;
// HashMap结构修改的次数
transient int modCount;
// 扩容的阈值，当键值对的数量超过这个阈值会产生扩容
int threshold;
// 负载因子
final float 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);
}

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

HashMap有4个构造函数。hash桶没有在构造函数中初始化，而是在第一次存储键值对的时候进行初始化。

tableSizeFor

这里重点看下tableSizeFor(initialCapacity)方法，这个方法的作用是，将你传入的initialCapacity做计算，返回一个大于等于initialCapacity最小的2的幂次方。

所以这个操作保证无论你传入的初始化Hash桶长度参数是多少，最后hash表初始化的长度都是2的幂次方。比如你输入的是6，计算出来结果就是8。

【源码】

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

【分析】

先来分析有关n位操作部分：先来假设n的二进制为01xxx...xxx。接着

对n右移1位：001xx...xxx，再位或：011xx...xxx

对n右移2为：00011...xxx，再位或：01111...xxx

此时前面已经有四个1了，再右移4位且位或可得8个1

同理，有8个1，右移8位肯定会让后八位也为1。

综上可得，该算法让最高位的1后面的位全变为1。

最后再让结果n+1，即得到了2的整数次幂的值了。

现在回来看看第一条语句：

int n = cap - 1;

让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000，十进制数值为8。如果不对它减1而直接操作，将得到答案10000，即16。显然不是结果。减1后二进制为111，再进行操作则会得到原来的数值1000，即8。

插入

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;

    // table初始为空，在第一次放置元素时初始化。也就是，并不是通过构造函数初始化，而是在插入时通过扩容初始化。
    // 这样有效防止了初始化HashMap没有数据插入造成空间浪费可能造成内存泄露的情况
    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<K,V> e; K k;

        // 旧键值对的覆盖
        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);

                    // 当链表的长度大于等于树化阈值，并且hash桶的长度大于等于MIN_TREEIFY_CAPACITY（这个条件在treeifyBin中），链表转化为红黑树
                    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;
            }
        }

        // 返回旧值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }

    //map调整次数加1
    ++modCount;

    // 键值对的数量达到阈值需要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

如果插入的键值对是新键值对，如果hash表没有初始化会进行初始化，否则将键值对插入链表尾部，可能需要链表树化和扩容。如果插入的键值对中的key已经存在，则对其value进行更新。

扰动函数

注意看下hash(key)方法，这是计算键值对hash值的方法，下面给出源码：

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

hashCode()是一个int类型的本地方法，也就将key的hashCode无符号右移16位然后与hashCode异或从而得到hash值在putVal方法中（n - 1）& hash计算得到桶的索引位置。那么现在有两个疑问，为什么要计算hash值？为什么不用 hash % n

为什么要计算hash值，而不用hashCode？因为通常n是很小的，而hashCode是32位，如果（n - 1）& hashCode，那么当n大于2的16次方加1，也就是65537后，(n - 1)的高位数据才能与hashCode的高位数据相与；当n很小是只能使用上hashCode低16位的数据。这会产生一个问题，即键值对在hash桶中分布不均匀，导致链表过长。而把hashCode无符号右移16位让高16位间接地与（n - 1）参加计算，从而让键值对分布均匀，降低hash碰撞。

为什么使用（n - 1）& hash而不使用hash% n呢？其实这两种结果是等价的，因为hash桶的长度一直是2的幂次方。但是&的效率比%高，原因因为&运算是二进制直接运算，而计算机天生就认得二进制。

扩容

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;

    // 如果旧hash桶不为空
    if (oldCap > 0) {

        // 如果容量超过最大容量，就将阈值设为整型最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }

        // 新的hash桶的长度2倍扩容没有超过最大长度，将新容量阈值扩容为以前的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }

    // 如果hash表阈值已经初始化过
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;

    // 如果旧hash桶为空，并且hash桶容量阈值没有初始化
    // 那么需要初始化新的hash桶的容量和新容量阈值为默认值
    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;

    // 初始化hash桶
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;

    // 如果旧的hash桶不为空，需要将旧的hash表里的键值对重新映射到新的hash桶中
    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)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order

                    // 如果是多个节点的链表，将原链表拆分为两个链表，两个链表的索引位置，一个为原索引，一个为原索引加上旧Hash桶长度的偏移量
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;

                        // 链表1
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }

                        // 链表2
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);

                    // 链表1存于原索引
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }

                    // 链表2存于原索引加上原hash桶长度的偏移量
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

HaspMap扩容就是就是先计算新的hash表容量和新的容量阈值，然后初始化一个新的hash表，将旧的键值对重新映射在新的hash表里。

如果在旧的hash表里涉及到红黑树，那么在映射到新的hash表中还涉及到红黑树的拆分。

在遍历原hash桶时的一个链表时，因为扩容后长度为原hash表的2倍，把扩容后的hash表分为两半，分为低位和高位。把原链表的键值对，一半放在低位，一半放在高位，这样的索引效率是最高的。

参考文献

HashMap源码分析（JDK 1.8） - 掘金

散列表​

数据结构​

类结构​

类常量​

实例变量​

构造函数​

tableSizeFor​

插入​

扰动函数​

扩容​

参考文献​

散列表