一文看透集合容器
- 一、Map
- a. HashMap
- b.ConcurrentHashMap
- c.HashTable
- d. TreeMap
- 二、Collection
- a. List
- ArrayList
- LinkedList
- Vector
- CopyOnWriteArrayList
- 对比和自身思考
- 思考：为什么都拒绝使用Vector啊？它线程安全诶
- b. Set
- HashSet
- TreeSet
- CopyOnWriteArraySet
- c. BlockingQueue
- ArrayBlockingQueue
- LinkedBlockingQueue
- 对比和自身思考
- 思考：为什么 LinkedBlockingQueue 中记录元素个数要使用 AtomicInteger 类型，为啥要CAS操作？
- 三、Collections#shuffle
本篇博客会对我画的如下图的集合进行源码分析，去发现新大陆：
一、Map
a. HashMap
经典集合，以1.8展开说，内部通过链表/红黑树的方式解决hash冲突问题，通过扰动计算计算hash值去降低hash冲突的概率，通过&运算代替%取模，加快计算速度…
put 方法解析如下：
// hash值的计算
// 将高位的hash码和低位hash码混合计算，降低hash冲突概率
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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)
// resize 初次扩容
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// hash映射到hash表对应位置是空，直接new
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 判断是否key相同，相同进行覆盖
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;
}
b.ConcurrentHashMap
这里不给你分析jdk1.7用Segment然后继承ReentrantLock去实现分段锁保证线程安全的，咱直接步入主题，看1.8是咋使用分段思想+Synchronized和CAS去保证线程安全的，这里的分段思想是说它锁的时候只是锁头节点，而不是说给整个Map上锁，也不是说向1.7那样分段，只能说锁的粒度小了。
直接步入主题，分析源码，put、get
public V put(K key, V value) {
return putVal(key, value, false);
}
public V putVal(K key, V value) {
if (value == null) // 可以看见，为空的话直接抛出空指针异常，所以说 ConcurrentHashMap是不能存空的
throw new NullPointerException();
// 对 key 的 hashCode 进行扰动
int hash = spread(key.hashCode());
int binCount = 0;
// 循环操作
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 如果 table 为 null 或长度为 0，则进行初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// 如果哈希槽为空，则通过 CAS 操作尝试插入新节点
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break;
}
// 如果哈希槽处已经有节点，且 hash 值为 MOVED，则说明正在进行扩容，需要帮助迁移数据
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// 如果哈希槽处已经有节点，且 hash 值不为 MOVED，则进行链表/红黑树的节点遍历或插入操作
else {
V oldVal = null;
// 加锁，确保只有一个线程操作该节点的链表/红黑树
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
// 遍历链表，找到相同 key 的节点，更新值或插入新节点
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 覆盖判断
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
// 将新节点插入到链表末尾
if (casNext(pred, new Node<K,V>(hash, key,
value, null))) {
break;
}
}
}
}
// 遍历红黑树，找到相同 key 的节点，更新值或插入新节点
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
// 如果插入或更新成功，则进行可能的红黑树化操作
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
// 如果替换旧值成功，则返回旧值
if (oldVal != null)
return oldVal;
break;
}
}
}
//
addCount(1L, binCount);
return null;
}
当table是空的时候，初始化table的时候也是通过CAS去控制首次扩容的：
get 方法解析，就是直接取：
并发控制阶段：
- 初始化桶阶段，CAS自旋去让某线程去初始化，防止多线程初始化导致的资源浪费；
- put元素阶段，若是直接头部插入那就CAS，若是插入链表和红黑树就用Synchronized锁住头部；
- 扩容阶段。
c.HashTable
该集合及其的简单，内部是通过单链表去解决hash冲突的，没有引入红黑树，而且它计算hash很直接，就是使用hashCode方法，比较特殊点就是它是线程安全的，在操作的方法前都加了synchronized关键字保障线程安全。
下面是put源码分析:
public synchronized V put(K key, V value) {
// Make sure the value is not null
// HashTable也不允许存储Null值
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
// 去尝试是否替换值
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
// 向链表尾部添加元素，判断是否需要扩容
addEntry(hash, key, value, index);
return null;
}
get 方法就更简单了，直接就是遍历找对应节点就好了：
d. TreeMap
咱先看一下它节点Entry的定义：
妥妥红黑树节点，明着说它底层就是一个红黑树，添加、查找元素都是对红黑树进行操作，想看红黑树咋实现的，这个TreeMap就是很好的参考。
这需要讲讲它的不同点，它的话当我们去遍历它的时候（不管是用keySet、entrySet…），它最后的结果都是有序的，它内部是通过迭代器去操作的，首先是得到红黑树最左的结点，也就是最小值的节点，然后再通过迭代器不断迭代…总结的说就是这个集合是有序的，排序规则的话默认是由存入的数据key的比较器为准，当然也可在构造TreeMap的时候自己指定。
二、Collection
a. List
主要是对 add、get、remove 方法进行分析
ArrayList
它不考虑线程安全问题，底层基于数组实现起来真的很简单，谁懂啊？内部封装了个elementData 数组，起初是一个空数组，第一次添加元素会扩容十，谁后满了再添加会扩容1.5倍，扩容起来很简单就是Arrays.copyOf，内部就是创建数组然后调用System.arraycopy去操作。那get、remove方法实现就是基于数组的基本实现。
add 方法实现，检查容量，容量不够调用 grow 进行扩容，然后填充元素：
remove
get
LinkedList
大伙应该都知道这玩意底层是个双向链表，但是这里想说的是它除了实现了List接口，还实现了Deque接口，就是说它具有双端队列的功能，提供了offerFirst、offerLast方法，默认操作都是个队列操作，即add是向尾添加，remove是向表头删除，getFirst是拿表头元素。
简单看看add、remove、get方法吧，不难，就是链表节点之间的连接、删除操作。
add 分析：
remove分析：
getFirst分析：
Vector
Vector底层实现和ArrayList没啥区别，都是基于数组，只不过Vector在grow扩容的时候是按俩倍扩容，而且它初始化容量是10，而ArrayList是没给初始化容量的，只不过第一次扩容是10.还有最大的区别就是它 add、remove、get 方法都加了 synchronized 关键字保障线程安全。
CopyOnWriteArrayList
底层实现还是基于数组的，但是它可以说不是动态数组，紧紧滴。内部有个 ReentrantLock 锁，在对数组进行写操作的时候会进行上锁。但是添加操作是先扩容原长度+1/-1，然后再进行添加/删除元素的。就只要写操作就会涉及Arrays.copyOf扩容/缩容现象。
add 方法实现，上锁，扩容，添加元素，OK。
remove 方法也简单，上锁，System.arraycopy 移除元素。
get 的话直接获取对应值就好了：
对比和自身思考
LinkedList可以作为双端队列使用，它底层是双向链表；
ArrayList、Vector、CopyOnWriteArrayList底层都是数组，ArrayList是非线程安全的，后俩是线程安全的。
思考：为什么都拒绝使用Vector啊？它线程安全诶
个人觉得哈，Vector作为一个动态数组容器，虽然保障了线程安全，但是对于这种数组容器，是经常会有读取操作的，那在高并发的情况下，读操作会因写操作而阻塞？那这往往是不能接受的，这也是为什么而后引出了
CopyOnWriteArrayList集合的原因吧
b. Set
HashSet
底层直接根据HashMap进行操作，Easy。
添加操作就是往 HashMap 中添加元素，value 就是内部封装的一个Object 对象，final的。
遍历起来也是根据HashMap 的keySet进行遍历的：
TreeSet
内部基于 TreeMap，emmmm…
添加元素就是往这个 TreeMap 中添加元素：
这里要阐述的是一个 tailSet 方法，会重构一个AscendingSubMap，重构一个Set出来
然后我们掉这个 tailSet 得到的集合的 first 方法的时候，就可以拿到拿到大于等于刚刚传进去的 fromElement 的第一个key：
CopyOnWriteArraySet
内部是由 CopyOnWriteArrayList 实现的，鼠鼠震惊~
它的add方法：
这添加就得 O(n) 时间复杂度了，它去遍历数组去判断这个元素是否存在的…虽保障了线程安全，但是比起 HashSet 性能要降不少。
c. BlockingQueue
主要分析三个方法实现：peek(读取队头元素）、poll(删除队头元素，并返回)、offer(入队）
ArrayBlockingQueue
底层是基于数组进行实现，由ReentrantLock保障线程安全（默认使用非公平锁），由takeIndex、putIndex表示出队头和队尾，用于插入元素，count记录队元素个数。
offer 方法实现，很简单，加锁，向队尾添加元素，putIndex、count加1，putIndex如果等于总容量了就置为0：
poll方法实现，一样简单，加锁，随后根据takeIndex让队头元素删除，一样takeIndex、count都加1，takeIndex到容量了置为0：
peek实现更简单，加锁取队头元素：
可以发现 poll、peek、offer 这三操作都是使用同一把锁，都是构造时候创建的ReentrantLock锁，就是说线程在执行这三方法时都存在竞争行为。
LinkedBlockingQueue
底层基于单链表进行实现的，由head节点属性指向队头，由last节点属性指向队尾，还于ArrayBlockingQueue不同的是LikedBlokingQueue内部维护了俩把ReentrantLock锁，一个putLock锁用来在控制队尾写操作的安全，一个takeLock锁用来控制队头读写操作的安全。这个时候在记录总元素的时候就可能存在线程安全问题，所以使用了原子性AtomicInteger，用CAS操作去保障队列元素总数变量的线程安全问题。
offer 方法实现，取队尾读写锁 putLock，进行加锁，队尾添加元素，count.getAndIncrement() CAS 进行队内元素个数+1.
poll 方法实现，拿到队头锁 takeLock，进行加锁，队头删除元素，count.getAndDecrement() CAS 进行队内元素个数-1.
peek 方法实现，取对应的队头锁takeLock，加锁，然后取头部元素就是了：
对比和自身思考
ArrayBlockingQueue 中三个操作都是使用同一把锁，且记录元素个数是long类型，反观 LinkedBlockingQueue 中有俩把锁，一把用于队尾操作，一把用于队头读写操作，而记录元素个数的是 AtomicInteger 类型，从这可以看见的后者的锁的粒度是更小的，那并发下性能也会更好。
思考：为什么 LinkedBlockingQueue 中记录元素个数要使用 AtomicInteger 类型，为啥要CAS操作？
这问题是开始我看LinkedBlockingQueue源码的时候，以为它和ArrayBlockingQueue一样使用的是同一个ReentrantLock对象，就是说操作前后都是上锁的，那么记录元素个数为什么要用AtomicInteger这种原子类型呢？后来仔细看发现是队头和队尾的操作是使用的不同的锁，那么这之间对元素个数变量就存在线程安全问题，而这里处理该线程安全就是使用原子类型的CAS操作进行的。完美~
三、Collections#shuffle
Collections 工具类里面有个 shuffle 方法，用来随机排序内部的元素的，咱来看看它咋实现的：
遍历一遍元素，从末尾开始，随机找前面序列的一个数进行交换，从而达到随机排序的效果。你别说，还挺有意思~😮😮😮
