HashMap

张林

2022-08-19 (Updated: 2022-11-25)

面试 › Java

Java, 数据结构与算法

认识HashMap

HashMap是平时开发中常用一种数据结构。其底层精妙的设计大大提高了我们开发出来的产品的底层性能。那么它是如何实现的，我们来一探究竟

底层数据结构

JDK1.7及之前桶数组（bucket） + 链表

JDK1.8之后当链表达到一定长度时会转化为红黑树

其实就是哈希散列法中的“拉链法”，只不过当一条链长度过长时，为了增加查询数据的性能，在JDK1.8之后就会将链条树化（红黑树）

构造函数

// 默认构造函数 加载因子为默认值0.75f
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}

// 包含另一个“Map”的构造函数
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

// 指定了容器大小的构造函数
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);
}

一般常用的就是构建一个空的HashMap，别的构造函数涉及到了一些需要知道的概念，借此机会一次性说掉

门限值

门限值Threshold就是扩容机制触发的一个阈值计算公式为：

门限值 = 数组容量 X 负载因子

其中负载因子会在下面做出说明

初始化容量

指的就是桶数组（bucket）的初始化大小默认为16

为什么是16呢简单的解释就是使用2的次方的容量可以在HASH取模运算后使得散列更加均匀学过数据结构的朋友应该都有印象书上建议初始化大小为2的次幂在这里JDK开发者选择了16作为默认的值

这些说明了为什么扩容时都是乘以2 就是为了保证桶数组的容量为2的次幂

在构造函数中若指定了一个初始的大小则初始容量会进行计算找到一个最近的2次幂数

1	this.threshold = tableSizeFor(initialCapacity);

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

乍看是不是很懵逼这个算法十分精妙来理解一下

比如要求17对应的2次幂数易得出是32

那么这个算法如何实现的呢就是先将17 -1 得到 16 二进制就是 10000

只要将二进制数第一个为1的位置开始，后面的数字全变为1 最后再加上1 就是我们要的2次幂数了 10000 -> 11111(31) -> 31 + 1 -> 32

这个算法就是实现将后面数全变为1的操作那为什么是逻辑右移1，2，4，8，16 就结束了呢

这样思考一个位置为1 右移1位就得到了两个1 此时右移2位就得到了4各个1 以此类推当右移16位时刚好一个int类型位数操作完自然可以得到任何int类型数据的所要求的二次幂数

负载因子

负载因子可以自定义，默认为0.75f

该参数用于调节散列效果例如当负载因子为1时数组需要到达容量大小则才开始扩容不可避免会出现很多HASH冲突导致某个节点的链条过长影响查询性能当负载因子为0.5时每当数组容量使用了一半时就开始扩容了虽然会大大降低HASH冲突的概率但散列效果却会不尽如人意于是取中间值0.75作为默认的负载因子开发者可以根据需求自由调节

扰动函数

HashMap中有这样一个方法专门用于求键值的HASH值

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

可见，在key求hashcode之后又将其与自己逻辑右移16位后的结果做了按位与操作，那么有两个问题

为什么要做按位与
- 保留hashcode的结果特征增强散列效果
为什么是16位
- 因为hashcode表示数据范围是int类型数据范围众所周知 int由32个bit组成因此逻辑右移16位（一半距离）以此结合一个hashcode高位和低位的特征以降低在对桶数组容量取模运算后的hash冲突

个人理解：这些参数的存在，就是为了数据有一个较好的散列效果，以增强数据查询插入的效率，以达到高性能的效果

HashMap基本操作和遍历

先循环插入一些数

HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < 14; i++) {
    map.put(i, (int) (Math.random() * 100));
}
System.out.println("直接输出HashMap");
System.out.println(map);

1 2	直接输出HashMap {0=43, 1=14, 2=54, 3=22, 4=75, 5=36, 6=73, 7=37, 8=46, 9=77, 10=69, 11=23, 12=63, 13=85}

这里可见HashMap以键值对的形式返回了数据

4种遍历方式

// ====ForEach循环遍历====
System.out.println("Iterate entries using ForEach loop:");
for (Map.Entry<Integer, Integer> stringStringEntry : map.entrySet()) {
    System.out.println("Key = " + stringStringEntry.getKey() + ", Value = " + stringStringEntry.getValue());
}


// ====ForEach迭代键值对方式====
System.out.println("Iterate keys / values using ForEach loop:");
for (Integer key : map.keySet()) {
    System.out.println("Key=" + key);
}
for (Integer value : map.values()) {
    System.out.println("Value=" + value);
}


// ====迭代器遍历===
System.out.println("Iterate using Iterator with generics=v:");
Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<Integer, Integer> entry = iterator.next();
    System.out.println("Key=" + entry.getKey() + " Value=" + entry.getValue());
}


// ====Java Lambda表达式遍历====
System.out.println("Iterate using Java 8 Lambda Expression:");
map.forEach((K, V) -> System.out.println("key: " + K + " value:" + V));

打印结果太多就不展示了可以自己试一下个人觉得Lambda表达式简直爱了好吗 Elegant And Concise 优雅且简洁

底层数据结构的构建

下面就来看看所谓的桶数组+链表+红黑树到底是怎么构建让我们一起撕开神秘的面纱

节点类

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    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;
    }

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

这便是HashMap中最基本的一个节点的构成它实现了Map.Entry<K,V> Entry是Map的一个静态内部类，用于存放键值对

值得注意的是，这里Node的equals方法，是比较Key和Value的equals方法，在开发中，如果有需求要进行个性化的比较，就需要重写我们自己的Object类的equals方法了

插入节点的putVal()方法

此方法是一个内部方法，仅在内部调用。在我们插入一个节点时，就会调用该方法

1
2
3

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

putVal方法也详细的展示了怎么构建这么一个精妙的数据结构的

先上源码前方高能~~~

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> 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);
    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);
                    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;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

头疼的来了看看怎么拆解怎么理解

做好预备工作

这里进行一系列的初始化 tab即是桶数组容器 p就是插入的单个节点若一上来table为null 则说明HashMap仅仅是做了初始化还没有一个初始化的大小空间那么就resize()方法分配初始空间这里只要知道resize方法就是用来分配空间的具体细节后面会做分析

第一种情况（当前位置为null）

HASH分配到的偏移位置还没有插入节点，那么二话不说，直接塞入新节点

1 2	if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);

值得注意的是数组偏移是通过 (n - 1) & hash 得到的其实这就是将hash对数组容量做了一个取默运算只不过数组偏移是从0开始的所以是n-1 非常精妙

第二种情况（hash分配的位置相同且Key相同）

说明这是节点更新，直接将当前节点更新

1
2
3

if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;

第三种情况（加入红黑树节点）

1 2	else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                               int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    TreeNode<K,V> root = (parent != null) ? root() : this;
    for (TreeNode<K,V> p = root;;) {
        int dir, ph; K pk;
        if ((ph = p.hash) > h)
            dir = -1;
        else if (ph < h)
            dir = 1;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            if (!searched) {
                TreeNode<K,V> q, ch;
                searched = true;
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    return q;
            }
            dir = tieBreakOrder(k, pk);
        }

        TreeNode<K,V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            Node<K,V> xpn = xp.next;
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

具体怎么加入的，需要先了解红黑树，这里不做多说明

第四种情况（加入链表节点）

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

遍历链表，若hash值Key值均一样，则直接退出循环

若链表长度即将大于树化的门槛值，则要靠考虑进行树化

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

首先会判断桶数组容量是否达到可以树化的最低标准，没有则先进行桶数组的扩容再HASH，达到了则将链表转化为红黑树

HashMap的resize()方法

在HashMap中，采用二次方扩容法

当HashMap在元素达到负载因子阈值时，便会自动扩容，以保证HASH得到很好的散列

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

resize()方法的一开始，进行一系列的初始化。下面分种情况来讨论

无参构造的空HashMap

由于是一个空的HashMap，oldTable oldCap oldThr均为空

于是直接初始化容量为16，门限值为0.75*16 = 12

达到门限值需要扩容

如果原来的桶数组大小已经超过最大限定容量(1 << 30)了，那么将门限值设定为Integer数据类型的最大值（1 << 31）
否则，就直接按照2次幂扩展规则，将桶数组容量和门限值都扩大为原先的2倍

接着，不可避免的，需要rehash

大概结构如下：遍历每个节点，进行调整

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<K,V> loHead = null, loTail = null;
            // 一系列操作
           	......
        }
    }
}

数组的调整

if ((e = oldTab[j]) != null) {
    oldTab[j] = null;  // 这一步将原数组对应位置的节点设为NULL
    if (e.next == null)  // 如果该节点的下一个为空，则说明此处既不是链表，也不是红黑树，直接进行哈希再分配
        newTab[e.hash & (newCap - 1)] = e;
  	......
    }
}

链表的调整

if ((e = oldTab[j]) != null) {
    oldTab[j] = null;
    // 单个节点
    ......
    // 红黑树
    ......
    // 链表
    else { // preserve order
        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;
        }
    }
}

乍一看很复杂，是的。

首先，要明白高低位链表是什么：

将每个节点HASH值与oldCap按位与，如果为0，则加入低位链表，如果高位为1，则加入高位链表

为什么会这样呢，举个例子，oldCap为16

若7(00111) & 16(10000) => 00000 则加入低位链表

若17(10001) & 16(10000) => 10000 则加入高位链表

下面看看怎么通过循环构建两根链表

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

将loHead loTail分别指向低位链表的头尾节点

将hiHead hiTail分别指向高位链表的头尾节点

接着将两条链表加入新的桶数组中

if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

最后，借互联网上的一张图来帮助理解

红黑树的调整

if ((e = oldTab[j]) != null) {
    oldTab[j] = null;
    // 单节点
    ......
    // 红黑树
    else if (e instanceof TreeNode)
        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
   // 链表
    ......
}

其中split函数细节为：

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

看起来有些复杂，其实和链表一样的。根据HASH将红黑树分出高低位链表来。再将两条链表树化塞入新的桶数组中。其中，有很多细节和特殊情况，暂不做讨论。关于红黑树的理论和实现，这里也不再详细赘述。

这样，对于HashMap是如何进行扩容的，我们有了一个基本的认识