Java HashMap 简介

发表于 | 分类于 | 阅读次数

存储一个键值对（key-value），根据键的 hashCode 值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null ，允许多条记录的值为 null 。HashMap 非线程安全，即任一时刻可以有多个线程同时写 HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以使用 ConcurrentHashMap 。

基本概念

Hash：译作“散列”，“哈希”。将任意长度的数据映射为固定长度的数据，这个过程的返回值被叫做散列值、哈希值、哈希码，这个过程就叫哈希/散列。散列值的空间通常远远小于输入的空间，不同的输入可能会被散列成相同的输出，因此不能从散列值来唯一的确定输入值。一个使用场景就是哈希表，哈希表被广泛用于快速搜索数据。

哈希表

哈希表是一种能实现关联数组的抽象数据结构，能把很多「键」映射到很多「值」上。哈希表使用哈希函数来计算索引，一个索引对应一个值。

  • 槽 Slot
    哈希表中的一个位置称为一个桶。
  • 装填/负载因子 load_factor
    装填因子 = 表中记录个数/散列表长度。

冲突/碰撞 Collision

通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突/碰撞。

哈希函数

实现哈希过程的函数就是哈希函数，一种将任意长度的消息压缩到某一固定长度的消息摘要函数。

构造原则

  • 定义域包含全部需要存储的关键字，值域依赖于散列表大小
  • 尽可能等概率，均匀分布到整个地址空间，降低冲突发生几率
  • 散列函数计算应尽量简单

常用方法

  • 直接定址法：取关键字的线性函数值
    Hash(key)=a*key+b：不会冲突，但当关键字分布不连续时，空位很多。
  • 除留余数法：最简单常用的方法
    散列表长度是 m，选取一个不大于 m 但最接近或等于 m 的质数 p：Hash(key)=key % p，可能会有冲突。
  • 数字分析法
    假设关键字是以 r 为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。共 r 个数码（0~r-1），所选的位应是各种符号在该位上出现的频率大致相同。
  • 平方取中法
    取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
  • 折叠法
    将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。

处理冲突的方法

  • 开放定址法
    如果选择的一个其它位置仍有冲突，则再选下一个，直到找到没有冲突的位置。
  • 链地址法/拉链法
    以每个哈希地址作为一个指针，指向一个链，即分配指针数组，将所有关键字为相同的记录存储在同一线性链表中。

HashMap 的实现原理

利用 key 的 hashCode 重新 hash 计算出当前对象的元素在数组中的下标：

  • 存储时
    如果出现 hash 值相同的 key，则覆盖原始值；如果 key 不同，则将当前的 key-value 放入链表中。
  • 获取时
    直接找到 hash 值对应的下标，在进一步判断 key 是否相同，如果相同从链表中找到对应值。

存储结构

HashMap 核心就是使用了数组+链表的存储方式，然后将冲突的 key 的对象放入链表中（也就是使用拉链法解决冲突），Java 1.8 中链表长度大于 8 时，链表转换为红黑树结构。

0042-hashMap-data-struct.png

Node 本质是就是一个映射（键值对），源码定义： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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) {...}
    public final K getKey()        {...}
    public final V getValue()      {...}
    public final String toString() {...}
    public final int hashCode() {...}
    public final V setValue(V newValue) {...}
    public final boolean equals(Object o) {...}
}

关键字段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 默认容量大小为 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;
// 链表转换为红黑树的门限值
static final int TREEIFY_THRESHOLD = 8;
// 
static final int UNTREEIFY_THRESHOLD = 6;
// 
static final int MIN_TREEIFY_CAPACITY = 64;

// 存储 key-value 的表，是一个数组
transient Node<K,V>[] table;
// 当前 key-value 对的数量
transient int size;
// 门限值，超过后将调整容量
int threshold;
// 负载因子
final float loadFactor;

table 索引对应的键值对叫做“桶”（bucket），它存储了链表的第一个元素。key 的 hashcode() 方法用来找到对象所在的桶，如果两个 key 有相同的 hash 值，他们会被放在 table 数组的同一个桶里面，以链表的形式保存。

  • loadFactor
    负载因子 = 表中记录个数/散列表长度。默认的负载因子 0.75 是对空间和时间效率的一个平衡选择。如果内存空间很多而又对时间效率要求很高，可以降低负载因子的值；相反如果内存空间紧张而对时间效率要求不高，可以增加负载因子值，这个值可以大于 1 。

  • threshold
    门限值，HashMap 中 Node(键值对)个数超过门限值后，将重新调整容量。threshold = table.length * LoadFactor，也就是说在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。

HashMap 中数组 table.length 必须为 2 ^ n 次方。

哈希函数及索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static final int hash(Object key) {
    int h;
    // 1. h = key.hashCode() 获取 key 的 hashCode
    // 2. 确保 h 的高 16 位和低 16 位都能参与异或运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// jdk1.7 的源码，jdk1.8 没有这个方法  
// 但是计算索引值（数组下标）时都是这个思路
// 可以在 put, resize 中看到索引计算
static int indexFor(int h, int length) {  
    // 3. 实现取模运算，实现均匀散列
    return h & (length - 1);
}

索引值计算如果 indexFor 返回值相同，表示出现冲突。前面提到 table.length 必须为 2 的 N 次方，换句话说 length - 1 的值换成二进制永远是全部为 1，正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。而哈希函数混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来，所以 indexFor 能实现均匀的散列值。
根据数学规律，就是如果 length 是 2 的 N 次方，那么模运算和按位与运算是等价的，也就是 h%length <=> h&(length-1)。

数组的扩容机制

再次强调，数组的长度是 2 的幂。如果当前数量大于门限值（size > threshold），或者说表中填满了 loadFactor （75%） 后，数组就需要自动扩容了（直接扩容到当前容量 2 倍大小）。当然 Java 里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组。 

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
54
55
56
57
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)
            // 扩容，2 的幂
            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)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 普通链表  
                else { // preserve order
                    ...
                }
            }
        }
    }
    return newTab;
}

添加或修改键值对

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
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);
                    // 如果长度超过门限 8，链表转换为红黑树
                    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;
}

删除键值对

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
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 确定键值对存在
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            // 红黑树
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // 普通链表
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 红黑树删除键值对
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // 链表根节点
            else if (node == p)
                tab[index] = node.next;
            // 普通链表其他节点
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

获取键值对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 找到指定键值对
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 红黑树中查找并返回
            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;
}

红黑树

二叉查找树

也称有序二叉树（ordered binary tree），或已排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

  • 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值
  • 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值
  • 任意节点的左、右子树也分别为二叉查找树
  • 没有键值相等的节点（no duplicate nodes）

红黑树基本特点

是一个二叉查找树，接近平衡。红黑树的 5 个性质：

  • 每个结点要么是红的要么是黑的
  • 根结点是黑的
  • 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的
  • 如果一个结点是红的，那么它的两个儿子都是黑的
  • 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点

红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为 O(log n)。

HashMap 中的应用

即使负载因子和哈希函数设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响 HashMap 的性能。于是在 JDK1.8 版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过 8 ）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高 HashMap 的性能，其中会用到红黑树的插入、删除、查找等算法。

并发

在多线程使用场景中，应该尽量避免使用线程不安全的 HashMap，而使用线程安全的 ConcurrentHashMap。那么为什么说 HashMap 是线程不安全的，当重新调整 HashMap 大小的时候，确实存在条件竞争（race condition）。因为如果两个线程都同时试着调整大小时，Java 1.7 中会将存储在链表中的元素的次序会反过来，如果条件竞争发生了，那么就会出现死循环。在 Java 1.8 中并没有反序，但是在调整容量大小时，依次在末端添加新元素，可能会出现数据丢失的现象。

总结

HashMap 使用了数组 + 链表的存储方式，存储的节点元素包含 key-value，每个数组元素中放的是链表的第一个对象，这个链表长度大于 8 时会转换为红黑树。

  • 扩容是一个特别耗性能的操作，所以在使用 HashMap 时尽量估算 map 的大小，初始化的时候给一个合理的数值，避免频繁扩容
  • 负载因子是可以修改的，也可以大于 1，但是建议不要轻易修改，除非情况非常特殊
  • HashMap 是线程不安全的，并发环境中使用 ConcurrentHashMap

参考文档

0%