集合容器框架源码学习笔记

发表于 | 分类于 | 阅读数

本文为近期学习JDK源码中集合类相关记录的笔记，因为是学习过程中的随笔，没有很仔细整理过。

虽然在日常使用中只需要关注这些类的api如何使用即可，但是对于进阶的提升，可以在源码中更加熟悉各类的使用方式，以及学习到更多好的设计和处理问题的思路。

ps：公司内网已经不能访问github等开源网站，代码一直提不上去github，写了一些笔记都不能及时更新。

HashMap

jdk1.7

HashMap 里面是一个数组，然后数组中每个元素是一个单向链表。

  • capacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。
  • loadFactor：负载因子，默认为 0.75。
  • threshold：扩容的阈值，等于 capacity * loadFactor
    HashMap扩容是长度的2倍，且长度永远是2的次幂，存储下标：index = h&(length-1)

put过程

  1. 判断当前数组是否需要初始化
  2. 如果key为null则put一个null进去
  3. 根据key计算出hashcode
  4. 根据hashcode得出table的下标所在位置的桶
  5. 如果桶是链表则遍历里面每个对象的hashcode、key和传入的key是否相当，相等则覆盖
  6. 如果桶是空新增一个entry写入到当前位置（addEntry）
  7. addEntry：判断是否需要扩容，计算公式如上，
    需要扩容则两倍扩容，并且将当前key重新hash定位,扩容后的位置要么是再原下标的位置，另一种是在下标为 <原下标+原容量> 的位置。
  8. createEntry：当前位置的桶传入到新建的桶中，如果当位置有桶则生成链表

get过程

  1. 根据key计算出heshcode，然后得到对应的下标
  2. 判断是否为链表，不是链表就根据key的hashcode进行比较，是则返回值；如果是链表则遍历链表同上进行比较。
  3. 没获取到返回null

jdk1.7的缺点

当Hash冲突严重时，在Node上形成的链表会变的越来越长，这样在查询时的效率就会越来越低；时间复杂度为O(N)。jdk1.8主要优化的就是这个。

jdk1.8

数据结构修改，数组+链表/红黑树
当链表长度超过8之后，会转换为红黑树，如果低于6会转换回链表
7中用entry标识每一个数据节点，8中修改为Node

put过程

  1. 判断当前table是否为空，空则进行初始化（resize中会判断是否进行初始化）
  2. 根据key得到hashcode定位到具体桶的位置，为空则没有hash冲突创建一个新的node。
  3. 如果有hash冲突，则比较entry的hashcode与当前位置的key的hashcode是否相等，相等则进行赋值。
  4. 如果当前桶为红黑树则按照红黑树的写入方式进行写入，如果是链表则在当前entry下创建形成链表。
  5. 判断当前链表大小是否超过预设阈值（TREEIFY_THRESHOLD）8，超过则转换为红黑树。
  6. 最后判断是否扩容

get

  1. 根据key得到hashcode定位到桶的位置，为空直接返回null。
  2. 遍历table的每一个entry，比较key是否相等，相等则返回value。
  3. 如果是红黑树则按照红黑树的方法进行查找，如果是链表则遍历进行查找。

HashMap在多线程并发时的问题是什么，哪里线程不安全

在HashMap扩容的时候会调用resize()方法，就是这里的并发操作容易在一个桶上形成环形链表；这样当获取一个不存在的 key时，计算出的index正好是环形链表的下标就会出现死循环。

ConcurrentHashMap

jdk1.7

由segment组成，每一个segment继承自reentrantlock（重入锁），所以每次加锁是对于每一个段进行加锁，从而保证全局的线程安全。

  • concurrencyLevel：并行并发数、segment数，默认是16，是控制ConcurrentHashMap的segment的数量，不可扩容。
  • initialCapacity：初始容量，这个值指的是整个 ConcurrentHashMap 的初始容量，实际操作的时候需要平均分给每个 Segment。
  • loadFactor：负载因子，因为Segment 数组不可以扩容，所以这个负载因子是给每个Segment 内部使用的。

HashEntry、value都是由volatile修饰的。

put过程

  1. 尝试获取自旋获取锁
  2. 如果重试次数达到了MAX_SCAN_RETRIES则改为阻塞锁获取，保证能获取成功
  3. 根据key得到hashcode定位到segments中HashEntry的下标
  4. 遍历HashEntry（链表）不为空则判断传入的key是否相等，相等则覆盖value
  5. 为空则新建HashEntry并加入到segments中，同时会先判断是否需要进行扩容
  6. 最后解除获取的锁

get过程

  1. 根据key得到hashcode并且计算得到segments中的下标，获取到HashEntry
  2. 遍历HashEntry中key，相等则获取value
    由于HashEntry的value是用volatile修饰的，保证了其可见性，所以每次获取都是最新的值

jdk1.8

CocurrentHashMap抛弃了原有的Segment分段锁，采用了CAS + synchronized关键字来保证并发安全性。与HashMap1.7的问题一样，链表过长后查询效率低的问题。

HashEntry修改为Node，其中的val,next都用了volatile修饰，保证了可见性

对sizeCtl的控制都是用 CAS 来实现的:

1
2
3
4
5
6
7
8
9
/**
 * Table initialization and resizing control.  When negative, the
 * table is being initialized or resized: -1 for initialization,
 * else -(1 + the number of active resizing threads).  Otherwise,
 * when table is null, holds the initial table size to use upon
 * creation, or 0 for default. After initialization, holds the
 * next element count value upon which to resize the table.
 */
private transient volatile int sizeCtl;

下面是翻译：

-1代表table正在初始化，N表示有 -N-1 个线程正在进行扩容操作。

如果table未初始化，表示table需要初始化的大小。

如果table初始化完成，表示table的容量，默认是table大小的0.75倍，用这个公式算 0.75（n – (n >>> 2)）。

CAS 会出现的问题：ABA

解决：对变量增加一个版本号，每次修改，版本号加1，比较的时候比较版本号。

put过程：

  1. 根据key的hashcode计算得处table的下标
  2. 判断是否需要进行初始化
  3. 获取table对应下标的Node，如果为空表示当前位置可以写入数据，利用CAS 尝试写入，失败则自旋保证成功
  4. 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容
  5. 如果都不满足，则利用synchronized锁写入数据（此处锁的对象是Node）
  6. 如果数量大于TREEIFY_THRESHOLD则要转换为红黑树

get过程：

  1. 根据key的hashcode计算得到table的下标，得到Node
  2. 如果是红黑树则按照树的方式获取值
  3. 如果不是则按照链表的方式遍历获取值

ArrayList

默认容量10

int newCapacity = oldCapacity + (oldCapacity >> 1)

其中oldCapacity是原来的容量大小，oldCapacity >> 1为位运算的右移操作，右移一位相当于除以2，所以这句代码就等于

int newCapacity = oldCapacity + oldCapacity / 2；

即容量扩大为原来的1.5倍，获取newCapacity后再对newCapacity的大小进行判断，如果仍然小于minCapacity，则直接让newCapacity 等于minCapacity，而不再计算1.5倍的扩容。然后还要再进行一步判断，即判断当前新容量是否超过最大的容量

if (newCapacity - MAX_ARRAY_SIZE > 0)

如果超过，则调用hugeCapacity方法，传进去的是minCapacity，即新增元素后需要的最小容量：
如果minCapacity大于MAX_ARRAY_SIZE，则返回Integer的最大值。否则返回MAX_ARRAY_SIZE。

调用Arrays.copyof方法，即复制原数组内容到一个新容量的大数组里。这里Arrays.copyof方法实际是调用System.arraycopy方法。

相关问题

追问1：ArrayList和LinkedList有什么区别？

追问2：ArrayList底层使用一个数组，它是怎么进行扩容的？

追问3: HashMap和Hashtable有什么区别?

追问4: HashMap的put和get方法是怎么实现的?

jdk1.7-.jdk1.8 HashMap的变化？

HashTable是通过synchronized实现线程安全，那么具体同步了哪些资源？

对修改Hashtable内部共享数据的方法添加了synchronized，保证线程安全。
包括put、get、remove、clear、size等方法都有同步。
总的来说就是所有对Hashtable的所有数据操作的行为都进行了同步。

追问5: 线程安全的集合类包括哪些，它们是怎么实现线程安全的?

追问6: Hashtable和ConcurrentHashMap的区别？

涉及其他知识点

红黑树，平衡二叉树

hash算法，下标计算如何计算

直接看下HashMap中的hash方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

  • key==null直接返回0;
  • hash为(h = key.hashCode()) ^ (h >>> 16);

以下为put方法的片段代码：

1
2
3
4
5
6
7
8
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 {
...
}

  • n为table扩容后的长度
  • p为当前节点
  • 得到table下标位置(n - 1) & hash ;

扩容细节

默认容量：DEFAULT_INITIAL_CAPACITY 1<<4 = 16;

CAS

借助Unsafe来实现native code。CAS有3个操作数，内存值V、旧的预期值A、要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。Unsafe借助CPU指令cmpxchg来实现。

投食入口