在日常的编程活动中，使用 Map 类型是十分常见的，那么你们知道每天使用的 Map 底层是如何实现的呢？今天就带大家来深入了解一下内部的构造。

1. 常见的 Map 类型

  • HashMap
  • HashTable
  • ConcurrentHashMap

2. HashMap

a. 存储结构

HashMap 的底层结构采用可扩容的动态数组，而数组中的每个格子里则存储着另一种结构，它有两种可能性：

  1. 当元素个数较少时，存储的是一个链表结构
  2. 当元素个数大于等于一个阈值（默认是8）时，存储的是一个红黑树（Java 8 才引入的），而在扩容中会去判断是否需要转换成链表结构

引入红黑树的目的是减少链表查找的时间开销，从 ${O(n)}$ 减少到 ${O(\log(n))}$

初始数组大小(capacity)

在 Java 8 中的 HashMap 的初始大小设置为 16，是 ${2^n}$ 的整数次方，之所以选择 16，其实更多的是一种经验值，其实只要是 ${2^n}$ 的大小都是合适的。

之所以选择 ${2^n}$ 作为容量，当数组扩容则是在原来容量的基础上增大一倍，其容量变成 ${2^{n+1}}$，依然是 2 的整数次幂。而这样做的目的是为了减小取模运算的开销，因为对 ${2^n}$ 进行取模操作可以简化为位运算。

数组的下标位置从 0 ~ ${2^n-1}$，而 ${2^n-1}$ 的二进制表示为 ${….1111}$，数组位置的计算从而可以变成如下的位运算：

$${index = hash & (2^n-1)}$$

而当扩容时，重新计算数组新位置的时候，相当于多了一个最新高一位的与运算 ${result = hash & 2^n}$，其结果不是 0 就是 1，因此重新的计算的数组位置就只有以下两种可能，大大减小了 rehash 的开销：

  1. 原来存储的数组位置
  2. 原来位置向后移动 ${2^n}$ 的新位置

那大家可能会问，HashMap 不是支持自定义的初始大小吗，那就不符合上面的简化运算的要求了。而现实是的确考虑到了这一点，所以在初始化时，会计算得到一个比传入数据大的最近的 ${2^n}$ 值，然后赋值为初始容量。

计算最近的 ${2^n}$ 值的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);

public static int numberOfLeadingZeros(int i) {
		// HD, Count leading 0's
		if (i <= 0)
				return i == 0 ? 32 : 0;
		int n = 31;
		if (i >= 1 << 16) { n -= 16; i >>>= 16; }
		if (i >= 1 <<  8) { n -=  8; i >>>=  8; }
		if (i >= 1 <<  4) { n -=  4; i >>>=  4; }
		if (i >= 1 <<  2) { n -=  2; i >>>=  2; }
		return n - (i >>> 1);
}

负载因子(loadFactor)和扩容阈值(threshold)

这里简单介绍一下负载因子和扩容阈值的概念。这两个值有着如下的关系：

${threshold = capacity * loadFactor}$

默认的负载因子是 0.75，即 ${\frac{3}{4}}$，当元素实际个数大于容量的 ${\frac{3}{4}}$ 时则进行扩容操作。

从这个公式可以看出当容量为 ${2^n}$ 时，threashold 是一个整数，不需要进行向下取整操作。

特别

hashmap 是可以存储 key 值为 null 的，其 hashcode 为 0，即会存储在数组位置为 0 的地方。

b. 数组元素结构(Node)

链表结构

  • hash：该位置的 hash 值
  • key：该位置的键值
  • value：该位置的数值
  • next：指向下一个 Node 节点

树结构

继承上述的链表结构，多了一些属性。这里不详细介绍红黑树，下次有机会单独讲解红黑树的知识。

树节点是根据 key 的 hashcode 进行组织的，通常而言，树节点占据的空间要比普通节点大一倍。

  • parent：父亲节点
  • left：左儿子节点
  • right：右儿子节点
  • prev：前面的节点，主要用于删除操作
  • red：判断节点是红色还是黑色

c. 写入操作

在初始化的过程中，并不会进行动态数组的创建，相反是在第一个写入操作时才去创建数组，这样可以减少内存的开销。

  1. 判断数组是否已经创建，没有则创建
  2. 计算插入数据的 hash 值，根据 hash 值计算得到数组的位置
  3. 将数据插入到计算得到的数组位置
    • 数组位置没有任何元素
      • 直接插入
    • 数组位置上已经有元素，判断存储元素的类型
      • 红黑树节点，插入在树中的某个位置
      • 链表，先进行插入操作，然后判断是否需要转换成红黑树，当底层数组小于 64 时，不会转化成红黑树而是直接扩容
  4. 插入完成后，判断是否需要进行扩容，如需要则进行扩容操作

d. 读取操作

  1. 根据 key 值计算得到 hash 值，进而得到数组的位置
  2. 取出数组位置的元素，判断是否为空，进而判断是否是想找的元素
  3. 判断节点类型
    • 树节点，在树中进行查找
    • 链表节点：在链表中进行查找
  4. 没有找到，则返回空

e. 删除操作

删除操作和查找操作非常类似，只是在最后需要进行删除操作（元素存在的情况下），不过需要注意删除根节点的情况，即删除数组位置里的第一个元素

2. HashTable

HashTable 可以认为是 HashMap 的线程安全版，很多方面都是类似的。这里主要分析以下两者的差异

初始容量的不同

HashTable 的初始容量为 11，扩容的大小为原来的两倍加一，而 HashMap 的初始容量为 16，扩容为原来的两倍。这里可以看出 HashTable 的容量并不是 ${2^n}$，因此它在计算数组位置的时候采用的是取模操作，因此在效率上要差一些的。

另一点不同则是 HashTable 在初始化的时候就已经分配了数组的空间。

所有操作都加了 synchronized 关键字

由于在方法上加了同步锁，HashTable 的并发性能并不是很好。而利用 modcount 进行类似版本的管理（悲观锁）导致性能更差。

是否允许插入 Null 值

HashMap 允许插入 Null 值的 Key 和 Value 的，而 HashTable 则不允许。主要是无法在并发操作中无法区分是元素是否存在还是为空。

迭代机制

HashMap 是 fail-fast，而 HashTable fail-safe 的。

fail-safe：安全失败机制，此次读到的值不一定是最新的，允许并发修改

fail-fast：快速失败机制，是集合的一种机制，在迭代过程中对元素的修改会立刻报错

3. ConcurrentHashMap

HashMap 不支持并发，而 HashTable 性能又这么差，那并发的需求我们到底应该使用什么呢？哈哈，其实 Java 还有 ConcurrentHashMap。

线程安全的实现

Java 8 采用 CAS + synchronized 的方式来实现并发，抛弃了 Java 7 采用的 Segment 分段锁的方式。并用 volatile 关键字去保证 Map 中数值的可见行。

其中 CAS 主要用于数组元素为空，即第一次插入到该数组位置中；而 synchronized 则用于数组位置已经存在元素的情况，在进行操作时，锁住该位置上的节点。

CAS(Compare And Swap)：是一种乐观锁的实现，同时也是一种轻量级锁。其原理首先记录拿到的原来的值，然后操作数据，等到要真正更新数据时，再次那一次值，并跟记录的原来的值进行相等的判断，如果不相等，则重新进行该操作，如果相等则可以真正更新数据。为了更好地知道数值是否更改过，可以记录版本号、时间戳等信息。

synchronized 获取锁（锁升级）的过程

  1. 偏向锁
  2. CAS 轻量级锁，并有短暂的自旋
  3. 重量级锁

与 HashMap 操作的不同

  1. ConCurrentHashMap 在插入过程中是首先插入，进而再去判断是否需要将链表结构转换成红黑树结构，而 HashMap 则是先判断，再插入。

读取操作

通过使 Node 节点元素 val 和 next 指针设置为 volatile，使得可以不通过加锁的方式就能够读取相应的值。
值得注意的是在扩容状态下读取时，可能会去新的数组下进行查找。另外也有可能是红黑树结构，需要通过读写锁在红黑树下进行查找。

扩容操作

数组用 volatile 修饰来保证在数组扩容的时候对各个扩容线程保证其可见性。

看完这篇文章，有没有让你对 Java Map 有更深的了解呢？如果内容对你有所帮助，请点赞支持哦！

更多精彩内容请关注扫码：

KnowledgeCollision 微信公众号

Knowledge Collision 激发思维碰撞，IDEA 丛生