HashMap那点事儿

HashMap那点事儿

薛定谔的汪
  2018-07-14 18:01:54 2018-07-14 18:01:54 Created   2023-11-17 19:37:37 2023-11-17 19:37:37 Updated    

HashMap 也是一个非常重要的key-value 映射集合，在开发中经常用到，底层是数组+单向链表的数据结构。在jdk1.7 和 1.8中实现略有不同，jdk8引入红黑树，提升了查询性能，并在扩容算法上做了优化，省去重新计算hash 的时间。

HashMap 数据结构图

jdk1.7：

jdk1.8:

HashMap 源码（1.8）

核心属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 默认容量
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * 最大容量
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 默认负载因子
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 *  key发生hash碰撞后，数组上存链表，当链表的长度达到8时，由链表转红黑树，提高查询速度
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 真正存放元素的Node数组
 */
transient Node<K,V>[] table;

/**
 * 存放 Entry的set，供遍历使用
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * HashMap的长度
 */
transient int size;

/**
 * 当前负载因子和table 数组长度决定的最大Node个数，threshold = table.lentgth * loadFactor
 * 推荐此属性在初始化 HashMap 时就指定，减少 rehash 和 数据拷贝，提升性能。
 */
int threshold;

/**
 * 初始化 HashMap 时设置的负载因子
 */
final float loadFactor;

负载因子的概念

决定 HashMap何时扩容，当 table 数组中 Node 的数量等于 table 总长度乘以负载因子的值时会发生扩容，通常保持默认即可，不建议修改这个值。

静态内部类 Node

在前面回顾 LinkedList 源码时也存在一个 Node，LinkedList 的 Node 是一个双向链表，而 HashMap 的 Node 是单向链表，保存了 K-V 键值对：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; //只有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;
    }
}

正好对应了前面结构图中的 “数组+链表” 结构。

常用方法

添加 put

1
2
3
4
public V put(K key, V value) {
    //对 key 做 hash 运算
    return putVal(hash(key), key, value, false, true);
}

putVal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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) //如果tab 为空则进行resize扩容
        n = (tab = resize()).length;
    /*根据key做 hash 计算出 key 对应的数组索引i 判断索引i处是否为null
    * 如果是 null，则在索引i 处创建新的节点
    * 代码拆分： i = (n - 1) & hash p = tab[1]  if(p == null){..}
    */
    if ((p = tab[i = (n - 1) & hash]) == null) 
        //采用头插法
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        //判断key 在tab[i]处如已存在直接覆盖
        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 { //tab[i]处为链表 遍历获取链表长度、当遍历到链表末尾时添加元素节点。
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //添加新节点后如果链表长度大于8，则将此单向链表转为红黑树 (源码真是恶心啊，可读性太差了)
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //在遍历链表的过程中，如果key已存在链表的某个节点就直接覆盖，退出循环
                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;
            //空方法，由子类 LinkedHashMap 实现
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //计算添加后的 size 如果大于当前集合的最大容量，就扩容
    if (++size > threshold)
        resize();
    //空方法，由子类 LinkedHashMap 实现
    afterNodeInsertion(evict);
    return null;
}

resize

当添加数据后，新的size 大于当前集合的容量时就发生扩容，执行此方法，主要执行的操作有：

  1. 初始化一个新的Node 数组；
  2. 将老数据复制到新数组中；
  3. HashMap 的 table 指向新的数组
  4. 计算并更新 threshold

resize 扩容很消耗性能，所以当我们使用 HashMap 时最好能提前预估 HashMap 的长度并为其初始化一个容量threshold，这样往里 put 的时候避免或减少 resize 操作。

源码虽然写的极好，但是jdk8引入红黑树后可读性太差，我就不粘贴了，自己理解了就好^_^

get方法

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

getNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //将key 进行 hash，计算索引，根据索引获得桶（可能是单Node、Node链表、红黑树）
    //如果 table 为空，或桶为空直接返回 null
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //如果key查询到返回此 Node
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //如果第一个不是
        if ((e = first.next) != null) {
            //先判断如果是红黑树则去树中取出来目标Node
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                //前面情况排除后只能是Node链表了， 遍历循环依次往下找，找到后返回
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

在jdk1.7时，没有引入红黑树，当发生 hash 碰撞时，会在数组对应索引处添加链表，当hash 碰撞频繁时，链表长度越来越大，查询的时候要逐步遍历，效率极低，jdk1.8引入红黑树，极大提高了查询效率

线程不安全

我们知道，HashMap 不是线程安全的，当多线程同时往HashMap里 put 元素时，可能会出现多次resize 操作，容易出现环形链表，这样当获取一个不存在的key 时，就会无限循环遍历改环形链表，导致死循环，多线程下推荐使用 ConcurrentHashMap（后面会分析）。

遍历 HashMap

1
2
3
4
5
6
//初始化HashMap
Map<Integer, String> hashMap = new HashMap(3){{
    put(1, "A");
    put(2, "B");
    put(3, "C");
}};

jdk1.7遍历 HashMap 的方式主要有一下几种：

keyset

先取出所有的 key 集合，再遍历 key 集合，根据 key 取 value。

获取hashMap 的所有 key 集合，然后使用 foreach 遍历（本质还是迭代器遍历，前面提到过）

1
2
3
for (Integer key : hashMap.keySet()) {
    System.out.println("key = " + key + ", value = "+hashMap.get(key));
}

entrySet

一次性取出 key-value 的 Entry 集合再遍历

1
2
3
for (Map.Entry<Integer, String> entry : hashMap.entrySet()) {
    System.out.println("key = "+ entry.getKey() + ", value = " + entry.getValue());
}

只取 value

只能遍历 value，无法获取key

1
2
3
for (String value : hashMap.values()){
    System.out.println(value);
}

jdk1.8

可以使用 lambda 遍历，更为简洁

1
2
3
hashMap.forEach((key,value) -> {
    System.out.println("key = " + key + ", value = "+ value);
});

总结

  1. resize 扩容是非常耗性能的，所以当我们在使用HashMap的时候，预估 HashMap的大小，初始化的时候给一个大致的数值，避免或减少频繁的扩容。
  2. jdk1.8引入红黑树大程度优化了HashMap的性能。
  3. HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap
  4. entrySet 方式在遍历 HashMap 时一次性把 key-value 查出来，推荐使用这种方式，如 jdk 版本是1.8 以上也可以使用 lambda 的方式遍历，更为简洁方便。
  • Title: HashMap那点事儿
  • Author: 薛定谔的汪
  • Created at : 2018-07-14 18:01:54
  • Updated at : 2023-11-17 19:37:37
  • Link: https://www.zhengyk.cn/2018/07/14/java/HashMap/
  • License: This work is licensed under CC BY-NC-SA 4.0.
On this page
HashMap那点事儿
  1. HashMap 数据结构图
  2. HashMap 源码（1.8）
    1. 核心属性
    2. 静态内部类 Node
    3. 常用方法
    4. 线程不安全
    5. 遍历 HashMap
  3. 总结