Home

img

HashMap 涉及的技术点非常多，典型的数据结构和算法有机结合，JDK 对 HashMap 优化变化中不断权衡时间复杂和空间复杂度。

# 一。存储结构

1.JDK1.8 之前 HashMap = 数组 (O (1)）+ 单向链表（O (n)）

2.JDK1.8 之后 HashMap = 数组 (O (1)）+ 单向链表（O (n)）+ 红黑树 (O (log n)

HashMap结构图.png

关于结构的几个关键数字：

1. 默认初始化数组容量大小是 16。

2. 数组扩容刚好是 2 的次幂。

3. 默认的加载因子是 0.75。

4. 链表长度超过 8 时将链表转化成红黑树结构。 5. 红黑树节点数减少到 6 的时候退化成链表。

以上几个数字关系，又为什么是上边的几个数字接下来一个个分析。

# 二。操作原理

# 1. put 储存流程

①计算桶的位置，根据 key 的 hashcode 求出 hash 值，位置 index = hash% length。

②判断是否达到扩容条件，threshold=DEFAULT_INITIAL_CAPACITY * loadFactor（16*0.75=12）大于这个阀门值就需要扩容，否则下一步。

③判断桶位置是否为空，如果为空直接在数据插入数据。如果不为空，下一步。

④判断是链表还是红黑树，链表是否到达转化红黑树，当前链表节点数 <=8，插入节点；如果是红黑树插入节点，否则下一步。

⑤链表转化成红黑树，插入节点。

⑥插入节点后计算当前 size 是否需要扩容，如果大于阀门值需要扩容 resize。

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
/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
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;
}

以上是 JDK1.8 的 HashMap 的 get 调用关键方法源码。

# 2. get 获取过程

①计算桶的位置，根据 key 的 hashcode 求出 hash 值，位置 index = hash% length。

②无论是数值，链表还是红黑树，for 循环判断 hash 值冲突就比对 key 是否相等，相等就返回对应的 value。

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
/**
 * Implements Map.get and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
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;
}

以上是 JDK1.8 的 HashMap 的 put 调用关键方法源码。

# 三。数据结构和算法思考

# 1. 为什么选择数组和链表结构？

①数组内存连续块分配，效率体现查询更快。HashMap 中用作查找数组桶的位置，利用元素的 key 的 hash 值对数组长度取模得到。

②链表效率体现增加和删除。HashMap 中链表是用来解决 hash 冲突，增删空间消耗平衡。

扩展： 为什么不是 ArrayList 而是使用 Node<K,V>[] tab？因为 ArrayList 的扩容机制是 1.5 倍扩容，而 HashMap 扩容是 2 的次幂。

# 2. 为什么扩容是 2 次幂，根据 key 的 hashcode 再求 hash 值？
# ①key 的 hash 值计算
1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

代码意思是 hash = hashcode 的高 16 位异化低 16 位，而不是直接 hashcode。

# ②计算桶的位置代码
1
index = (n - 1) & hash

思想：

一是，为了减少 hash 冲突使用 hash% length 计算，求模计算保证了得到的结果一定在 0-length 范围之内。

二是，为了提高运算速度，模运算比不上位运算，当 n 是 2 的次幂才满足 hash% length == （n-1）&hash。

确定公式中（n-1）符合最优等式，剩下考虑 hash 值的最优，hash 值这个因子考虑影响结果尽可能不冲突。

因为计算速度体现在位运算上，条件 n 是 2 的次幂，那么 n-1 的换算成二进制前边都是连续的 0，后边都是连续的 1,。比如 n=16，则 n-1=15，15 的二进制 1111。hash & 1111 = 只要关注的 hash 的二进制的最后四位数进行 & 运算。

（n-1）& length.png

如上图，最终会与 15 的二进制进行 1111 四位运算，如果与 key.hashcode 进行与运算的话，只要 key 的 hashcode 最后四位为 0000 前边无论是什么都没关系，这样出现相同值的概率高很多。所以，引入 hashcode 先高低 16 位进行异或运算，减少 hash 冲突。

扩展： hashcode 与 equals 相等判断对比： 两个 key 的 hashcode 相等，key 不一定 equals。 两个 key 的 equals，hashcode 一定相等。

# 3. 为什么加载因子为 0.75，链表长度大于 8 转成红黑树？

思想：

上边问题不是两个独立问题而是相互相关，目的尽量减少冲突前提提高空间利用率和减少查询成本的折中。

加载因子决定了 HashMap 的扩容的阀门值，如果桶是 16，那么扩容值 16* 0.75=12，也就是 12 的时候就要考虑扩容，还有 4 个没有被利用到，牺牲的空间。如果加载因子是 1，空间利用率高，但是查询速度变慢。

原理：

权衡依据是以上情况符合泊松分布（一种统计与概率学里常见到的离散概率分布，适合于描述单位时间（或空间）内随机事件发生的次数），用 0.75 作为加载因子，每个碰撞位置的链表长度超过８个概率非常低，少于千万分之一。

源码说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins.  In
* usages with well-distributed user hashCodes, tree bins are
* rarely used.  Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0:    0.60653066
* 1:    0.30326533
* 2:    0.07581633
* 3:    0.01263606
* 4:    0.00157952
* 5:    0.00015795
* 6:    0.00001316
* 7:    0.00000094
* 8:    0.00000006
* more: less than 1 in ten million

扩展：

为什么不一开始选择红黑树？

红黑树近乎于平衡二叉树，结构适合均匀分布节点，减少树的深度像链表长度情况。原因主要是插入效率上，红黑树增加节点很可能需要进行左旋，右旋，着色操作，这些时间效率并没有链表形式高。

# 4.HashMap 的 key 选择

1）选择不可变的对象，比如字符串或 int 类型。

2）如果要用一个自定义实体类作为 key：

①类添加 final 修饰符，保证类不被继承。

②保证所有成员变量必须私有，并且加上 final 修饰。

③不提供改变成员变量的方法，包括 setter。

④通过构造器初始化所有成员，进行深拷贝 (deep copy)。

# 5.String 类中的 hashcode 计算
1
2
3
4
5
6
7
8
9
10
11
public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
    char val[] = value;
        for (int i = 0; i < value.length; i++) {
              h = 31 * h + val[i];
          }
          hash = h;
      }
      return h;
}

哈希计算公式：s [0] 31^(n-1) + s [1] 31^(n-2) + … + s [n-1]

# 四。横向扩展

# 1.HashMap 出现线程问题

①多线程扩容，引起的死循环问题（jdk1.8 中，死循环问题已经解决）。

②多线程 put 的时候可能导致元素丢失。

③put 非 null 元素后 get 出来的却是 null。

# 2. 使用线程安全 Map

①HashMap 并不是线程安全，要实现线程安全可以用 Collections.synchronizedMap (m) 获取一个线程安全的 HashMap。

②CurrentHashMap 和 HashTable 是线程安全的。CurrentHashMap 使用分段锁技术，要操作节点先获取段锁，在修改节点。

# 3.Android 提倡使用 ArrayMap

①ArrayMap 数据结构是两个数组，一个存放 hash 值，另一个存放 key 和 value。

②根据 key 的 hash 值利用二分查找在 hash 数组中找出 index。

③根据 index 在 key-value 数组中对应位置查找，如果不相等认为冲突了，会以 key 为中心，分别上下展开，逐一查找。

优势，数据量少时（少于 1000）相比 HashMap 更节省内存。劣势，删除和插入时效率要比 HashMap 要低。

Edited on Views times