JAVA集合和映射表源码详细解读
2019-05-06 本文已影响68人
Aiibai
下面这些类图是通过IDEA生成的，将一些无用的线删掉了（比如：LinkedList继承了AbstractList，并且实现List，其实不用声明实现List接口，因为这里AbstractList就是List的实现。这种做法不明白其意思，网上搜索的答案是因为手误，但是也不影响程序，所以就一直保留了。。）
绿色实线：接口继承
蓝色实现：类继承
绿色虚线：接口实现
下面是集合的类图，这里只画出了比较常用的类，并不是java中的全部集合类，大致可以分为三种类型：List、Set和 Queue，后面会对每种类型的集合进行详细解读，这里只简单提一下这三种类型的区别。
List：作为
有序可重复集合的容器，实现方式有数组（ArrayList）和链表（LinkedList）等。
Set：不能包含重复元素，并且元素是无序的，当然这里的无序指的是天然无序，并不是没有办法让它有顺序，如果不考虑元素的顺序，只是判断元素是否存在于集合中，使用这种数据结构更高效。
Queue：队列是一种FIFO的数据结构，也有双端队列，常用的场景是阻塞队列实现生产者和消费者。
Collection.png
List
List.png
- ArrayList
底层是用Object类型的数组（考虑一下为什么不是泛型数组，为什么没有泛型数组）存储，适用于索引查找元素，但是对于添加和删除元素效率较低，这是底层数组结构决定的，删除和添加元素需要移动受影响的元素。既然ArrayList是动态数组，那么它是如何实现扩容的，请看下面的源代码
public void add(int index, E element) {
rangeCheckForAdd(index);
//检查容量
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
private void ensureCapacityInternal(int minCapacity) {
//DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空数组
//初始化数组大小最小是DEFAULT_CAPACITY
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//修改计数器，用于迭代器的快速失败检查
modCount++;
// overflow-conscious code
//如果容量不够，进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新容量是原来容量加1/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果新容量比需要的最小容量小，就是用需要的容量作为新容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新容量大于最大容量（MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8）
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
//这个方法除了检查minCapacity是不是负数之外，后面返回值不知道意义何在，
//如果真是newCapacity - MAX_ARRAY_SIZE>0，但是MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8，
//也就是说数组最大是Integer.MAX_VALUE，为什么不直接将MAX_ARRAY_SIZE 设置为Integer.MAX_VALUE
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError()；
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//将要添加元素位置以后的所有元素向后移动一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//将要删除的元素的后面的元素向前移动一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
总结：
- newCapacity = oldCapacity + oldCapacity / 2 ，具体还要根据minCapacity以及数组当前状态确定。
- ArrayList 的最大容量是Integer.MAX_VALUE
- 插入和删除时需要移动元素
- LinkedList
链表存储，并且实现了双端队列接口，适用于插入和删除，但是不适用于通过索引获取元素，即便是支持的，效率很低。我们看一下插入和删除操作的源码
public void add(int index, E element) {
//插入位置检查： 0<=index<=size
checkPositionIndex(index);
//插入链表末尾
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkLast(E e) {
//插入之前末尾节点
final Node<E> l = last;
//设置插入节点的前驱节点是之前的末尾节点，后驱节点为空
final Node<E> newNode = new Node<>(l, e, null);
//插入节点作为新的末尾节点
last = newNode;
//如果之前的末尾节点为空，也就是链表为空，新节点应该作为首节点，
//否则设置新节点是之前末尾节点的后驱节点
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//根据元素的索引查找元素
Node<E> node(int index) {
// assert isElementIndex(index);
//如果索引大于1/2 size，从首节点遍历，否则从末节点遍历
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
总结：
1.获取元素是通过遍历元素，所以效率不高，O(n)
2.向指定的位置添加和删除元素，也会涉及到通过索引定位元素，然后修改节点关系，也就是LinkedList的插入和删除效率不一定比ArrayList高，当数据量比较大，索引靠近中间位置（遍历查找元素耗时最多）的时候，ArrayList要比LinkedList的效率高。（可以用20w个元素，index设置为10w测试）。但是如果只是在末尾插入元素呢，这个要根据数据量来说，具体可以看一下这篇文章：https://blog.csdn.net/qq_34144916/article/details/81154528
- List总结
- 在插入或者删除场景推荐使用 LinkedList
- 在索引查找场景推荐使用 ArrayList
上面的两点不是绝对的，要具体根据元素数量来说，在元素数量比较小时适用。
Vector和ArrayList的相同点和不同点
- 相同点：
- 继承自
AbstractList - 底层使用Object数组实现
- 实现了RandomAccess，支持随机访问
- 能容纳的最大元素数量相同
- 不同点
- Vector的所有公开方法都是
synchronized的 - 扩容大小不同
//Vector
//capacityIncrement 可以通过构造函数传入，默认是0
newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity)
//ArrayList
newCapacity = oldCapacity + (oldCapacity >> 1);
双端队列以及使用场景
在上面的类图中我们看到 ArrayDeque 和 LinkedList 都实现 Deque 接口，ArrayDeque 是循环队列，可以使用在队列和栈场景，双端队列主要适用于工作秘场景，比如爬虫任务。在队列模块会进行详细解读。可以参考这篇文章：
https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/4-Stack%20and%20Queue.md
到此List相关类详细完毕，下一节我们学习Set。
Set
Set.png
这里我们着重介绍
HashSet 、LinkedHashSet和TreeSet
- HashSet
HashSet底层是使用HashMap存储，HashMap我们会在后面的章节介绍到，那么将HashSet中的元素如何存储到HashMap中的，HashMap中的键是什么？值是什么？请看下面的代码
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public boolean add(E e) {
//键是元素，值是一个固定的Object，而且是静态的，
//也就是所有 `HashSet` 在 `HashMap`中的值是一样的
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public Iterator<E> iterator() {
return map.keySet().iterator();
}
这里需要注意一点，既然 HashSet 中的元素是作为 HashMap 的键，那么为了保证 HashSet 中元素不能重复，就要重写元素的 equals 和 hashCode 方法。至于这两个方法的关系我们在 Map 章节介绍
实现很简单吧，下面我们再说一下 HashSet 的子类 LinkedHashSet
-
LinkedHashSet
LinkedHashSet使用LinkedHashMap实现的，LinkedHashMap是一个比较有意思的Map，Map章节介绍，这里知道LinkedHashSet保证元素的遍历顺序和插入顺序是相同的就行，其他和HashSet没有什么区别，这也是为什么前面我们说Set只是天然无序的，并不是不能做到有序。 -
TreeSet
TreeSet是使用TreeMap实现
所有要想深入了解Set，必须学习对应的Map。 -
Set总结
- Set 使用 Map 实现
- HashSet 是无序的
- LinkedHashSet 是有序的，顺序是元素插入的顺序
- TreeSet 可以对元素排序
- 它们都是线程不安全的
Set学习至此完毕，下一节学习Queue。
Queue
Queue.png
- 队列分类
| 阻塞单端队列 | 非阻塞单端队列 | 阻塞双端队列 | 非阻塞双端队列 |
|---|---|---|---|
| BlockingQueue | Queue | BlockingDeque | Deque |
| ArrayBlockingQueue LinkedBlockingQueue SynchronousQueue PriorityBlockingQueue |
PriorityQueue | LinkedBlockingDeque | ArrayDeque/LinkedList |
- 使用场景
在生产者-消费者设计中，所有消费者有一个共享的工作队列，而在工作密取设计中，每个消费者都有各自的双端队列。如果一个消费者完成了自己双端队列中的全部工作，那么它可以从其它消费者双端队列末尾秘密地获取工作。
密取工作模式比传统的生产者-消费者模式具有更高的可伸缩性，这是因为工作者线程不会在单个共享的任务队列上发生竞争。在大多数时候，它们都只是访问自己的双端队列，从而极大地减少了竞争。当工作者线程需要访问另一个队列时，它会从队列的尾部而不是头部获取工作，因此进一步降低了队列上的竞争程度。
工作密取非常适用于即是消费者也是生产真问题--当执行某个工作时可能导致出现更多的工作。例如，在网页爬虫程序中处理一个页面时，通常会发现有更多的页面需要处理。类似的还有许多搜索图的算法，例如在垃圾回收阶段对堆进行标记，都可以通过工作密取机制来实现高效并行。当一个工作线程找到新的任务单元时，它会将其放到自己队列的末尾（或者在工作共享模式中，放入其它工作者线程的队列中）。当双端队列为空时，它会在另一个线程的队列末尾查找新的任务，从而确保每个线程都保持忙碌状态。
首先我们简单陈述一下，各种类型队列的定义：
image.png
关注一下对于相同操作，不同方法的操作结果
| Throws exception | Special value | Blocks | Times out | |
|---|---|---|---|---|
| Insert | add(e) | offer(e) | put(e) | offer(e, time, unit) |
| Remove | remove() | poll() | take() | poll(time, unit) |
| Examine | element() | peek() | not applicable | not applicable |
- ArrayDeque
无界循环双端队列
在阅读代码之前，首先应该明白一个公式：
a % b == a & (b - 1)，前提是b是2^n，并且a>0，具体证明可以参考这里：
https://www.codercto.com/a/30894.html
// 第一个元素的索引
private transient int head;
// 下个要添加元素的位置，为末尾元素的索引 + 1
private transient int tail;
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
/*当head-1 = -1 时，取余得到的是(elements.length - 1)，从而实现了循环，
这也说明了tail为什么不是最后一个元素的位置，而是最后一个需要插入元素的位置，如果是最后一个
元素的位置的话，当：head=0，tail=elements.length-1 时，就没有位置从首部插入新的元素*/
elements[head = (head - 1) & (elements.length - 1)] = e;
/*如果head==tail 时进行扩容，请注意这里的tail是下一个可插入元素的位置，也就是这时候数组中其实
还有一个空位的*/
if (head == tail)
doubleCapacity();
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
//这里直接在尾部插入了元素，就是因为tail是下一个可插入元素的位置
elements[tail] = e;
/*更新tail，如果需要扩容
取模，保证数据不越界*/
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
if (result == null)
return null;
elements[h] = null; // Must null out slot
head = (h + 1) & (elements.length - 1);
return result;
}
public E pollLast() {
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
E result = (E) elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;
return result;
}
/**
* Allocates empty array to hold the given number of elements.
*获取大于numElements的最小2^n
* @param numElements the number of elements to hold
*/
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
//如果numElements本来就是2^n，则结果翻倍，如果想返回原始值，则在计算之前-1
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);//使 n 的前2位为1
initialCapacity |= (initialCapacity >>> 2);//使 n 的前4位为1
initialCapacity |= (initialCapacity >>> 4);//使 n 的前8位为1
initialCapacity |= (initialCapacity >>> 8);//使 n 的前16位为1
initialCapacity |= (initialCapacity >>> 16);//使 n 的前32位为1
initialCapacity++;
//如果大于了最大整数，上面的++会导致溢出，结果变为负数
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
elements = new Object[initialCapacity];
}
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
那么可以回答下面的问题了
- 如何做到循环队列？
通过控制数组元素个数为2^n，通过 & 实现循环 - 怎么判断需要扩容
当 head==tail 时，说明数组中只剩tail位置可以插入，这是进行两倍的扩容 - 如何做到无界队列
数组拷贝扩容
通过上面源码的学习，我们应该收获到
- 实现有界循环：a & (b-1)
- 计算一个数的最小2的次幂
- LinkedList
在List章节已经详细介绍过
关于上面这两个双端队列性能的比较可以看一下这篇文章：
https://www.zhihu.com/question/33030727
- PriorityQueue
优先级队列，因为需要排序，有两种方式实现排序，要么元素实现Comparable接口，要么在给队列的构造函数提供比较器：Comparator
在学习之前我们复习一下我们曾经学习的堆
堆：
- 近似完全二叉树结构
- 如果用数组实现堆，每个节点的索引满足下面的公式：
节点索引是k,那么左右子节点的索引分别是:2i+1和2i+2 - 有序堆：大顶堆（升序）、小顶堆（降序），
满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆，满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆
下面代码是用小顶堆排序
public static void sort(int[] array) {
//构建小顶堆，从最后一个非叶子节点调整，直到堆顶
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, array.length, i);
}
//排序
for (int i = array.length - 1; i >= 0; i--) {
//将顶部元素和最后一个在数组中（这里请注意，是数组中）未排序的元素交换
swap(array, 0, i);
//交换以后，调整由交换引起的可能不满足小顶堆性质的节点
adjustHeap(array, i, 0);
}
}
private static void adjustHeap(int[] array, int length, int i) {
int temp = array[i];
//从i节点的左子节点开始
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
//如果右子节点比左子节点的值还小，就用右子节点与父节点比较
if (k + 1 < length && array[k] > array[k + 1]) {
//右子节点
k = k + 1;
}
//如果子节点的值比父节点小，交换
if (temp > array[k]) {
swap(array, i, k);
//交换以后，确保父节点沉下去以后还是满足小顶堆性质
i=k;
} else {
break;
}
}
}
private static void swap(int[] array, int a, int b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
好了，如果明白了小顶堆排序，那么学习 PriorityQueue 源代码就简单多了，它的实现就是：数组+小顶堆
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
//自动扩容，grow方法和ArrayList中的grow类似，这里不做过多解释
if (i >= queue.length)
grow(i + 1);
//更新元素总数
size = i + 1;
//如果是第一个插入到队列中的元素，直接放到数组的0位
if (i == 0)
queue[0] = e;
else
//将i作为子节点，调整它以及它的祖先节点
siftUp(i, e);
return true;
}
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
//如果要移除的是最后一个元素，直接移除，不用调整堆
if (s == i) // removed last element
queue[i] = null;
else {
//堆中最后一个元素，也是最大的元素
E moved = (E) queue[s];
queue[s] = null;
//将最大的元素移动到要移除的元素的位置，并向下调整堆
//这里写的不太好，既然已经是小顶堆了，最有可能出现在要删除位置的元素应该是它的子节点
//这里的moved应该用要删除元素的子节点感觉更合适一点，也有另外一个原因是，不管移动那个
//节点，要删除的元素的所有子节点都要移动一下
siftDown(i, moved);
//如果没有向下调整，也就是说它比它的子节点都小，那就要判断一下是否有向上调整的必要
//如果queue[i] ！= moved 说明向下调整了，也就是说有子节点还比它小，所以没有必要再向上调整
//了，因为本来就是有序堆。
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
//向下调整堆，也就是将k作为父节点
private void siftDown(int k, E x) {
//下面的两个方法的算法是一样的，只不过比较方式不一样
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
//还记得父节点的子节点的索引关系吗？2K+1/2K+2，也就是最大的非叶子节点的索引应该是
//(size-2)/2=size/2-1，所以这里的half可以理解为第一个叶子节点的索引
int half = size >>> 1; // loop while a non-leaf
//如果是非叶子节点
while (k < half) {
//左节点：child=2k+1
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
//右节点
int right = child + 1;
//如果右节点比左节点小，就用右节点的父节点比较
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
//继续调整交换以后的子节点
k = child;
}
queue[k] = key;
}
//类似于：siftDownComparable
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
//向上调整，k作为子节点
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
private void siftUpUsingComparator(int k, E x) {
//直到对顶元素
while (k > 0) {
//parent = (k-1)/2
int parent = (k - 1) >>> 1;
Object e = queue[parent];
//如果比它的父节点大，就结束
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
//初始化堆，从第一个非叶子节点开始（length/2-1）
private void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}
学习完源代码是不是觉得没有想象中的那么难？呵呵
使用场景：
那么这个队列的使用场景是什么，既然它是优先级队列，那直接想到的就是处理优先级高的数据，比如一个电商网站搞特卖或抢购，用户登录下单提交后，考虑这个时间段用户访问下单提交量很大，通常表单提交到服务器后端后，后端程序一般不直接进行扣库存处理，将请求放到队列，异步消费处理，用普通队列是FIFO的，这里有个需求是，用户会员级别高的，可以优先抢购到商品，可能这个时间段的级别较高的会员用户下单时间在普通用户之后，这个时候使用优先队列代替普通队列，基本能满足我们的需求。
后面我们学习一下阻塞队列，一般使用阻塞队列使用的比较多，因为大多数涉及到队列的场景都有高并发。
突然发现除了LinkedList其他队列都不允许元素为空，我想这可能是因为像poll这样的方法如果没有获取到元素会返回null，但是如果允许元素有null，那么就有歧义了。
- 阻塞队列是通过
ReentrantLock来保证线程安全的，有两个Condition，分别是：notEmpty，notFull - 阻塞队列新增了几个中重要的方法：阻塞方法
take/put和超时等待的off /poll
- ArrayBlockingQueue
有界队列
如果读懂之前介绍的队列源代码，这里的源代码就很简单了
int count;
final Object[] items;
//阻塞获取元素索引
int takeIndex;
//阻塞添加元素索引
int putIndex;
final ReentrantLock lock;
//有数据条件
private final Condition notEmpty;
//有空间条件
private final Condition notFull;
//入队列
private void enqueue(E x) {
// assert lock.getHoldCount() == 1;
// assert items[putIndex] == null;
final Object[] items = this.items;
items[putIndex] = x;
//从头开始添加，可以想象成putIndex和takeIndex刚开始都为0，然后takeIndex跟在putIndex后面
//在数据中循环移动
if (++putIndex == items.length)
putIndex = 0;
count++;
notEmpty.signal();
}
//出队列
private E dequeue() {
// assert lock.getHoldCount() == 1;
// assert items[takeIndex] != null;
final Object[] items = this.items;
E x = (E) items[takeIndex];
items[takeIndex] = null;
if (++takeIndex == items.length)
takeIndex = 0;
count--;
if (itrs != null)
itrs.elementDequeued();
notFull.signal();
return x;
}
- LinkedBlockingQueue
可以是有界，也可以是无界
类似于ArrayBlockingQueue，不同的是底层使用链表，并且lock的粒度不同，新增了takeLock和putLock，计数使用AtomicInteger
private final AtomicInteger count = new AtomicInteger();
transient Node<E> head;
private transient Node<E> last;
private final ReentrantLock takeLock = new ReentrantLock();
private final Condition notEmpty = takeLock.newCondition();
private final ReentrantLock putLock = new ReentrantLock();
private final Condition notFull = putLock.newCondition();
private void enqueue(Node<E> node) {
// assert putLock.isHeldByCurrentThread();
// assert last.next == null;
last = last.next = node;
}
private E dequeue() {
//这里要明白的是head节点是个空节点，移除的是空节点的next
Node<E> h = head;
Node<E> first = h.next;
h.next = h; // help GC
head = first;
E x = first.item;
first.item = null;
return x;
}
public void put(E e) throws InterruptedException {
if (e == null) throw new NullPointerException();
// Note: convention in all put/take/etc is to preset local var
// holding count negative to indicate failure unless set.
int c = -1;
Node<E> node = new Node<E>(e);
final ReentrantLock putLock = this.putLock;
final AtomicInteger count = this.count;
putLock.lockInterruptibly();
try {
while (count.get() == capacity) {
notFull.await();
}
enqueue(node);
c = count.getAndIncrement();
if (c + 1 < capacity)
notFull.signal();
} finally {
putLock.unlock();
}
if (c == 0)
signalNotEmpty();
}
public E take() throws InterruptedException {
E x;
int c = -1;
final AtomicInteger count = this.count;
final ReentrantLock takeLock = this.takeLock;
takeLock.lockInterruptibly();
try {
while (count.get() == 0) {
notEmpty.await();
}
x = dequeue();
c = count.getAndDecrement();
if (c > 1)
notEmpty.signal();
} finally {
takeLock.unlock();
}
//c是上一次元素数量，如果上一次容量满了，现在移除了一个元素，那么应该通知当前
//容量非满，刚开始看着说有可能发生多线程挂死，后面才看到signalNotFull方法中又用了
//putLock，所以不用担心
if (c == capacity)
signalNotFull();
return x;
}
private void signalNotFull() {
final ReentrantLock putLock = this.putLock;
putLock.lock();
try {
notFull.signal();
} finally {
putLock.unlock();
}
}
private void signalNotEmpty() {
final ReentrantLock takeLock = this.takeLock;
takeLock.lock();
try {
notEmpty.signal();
} finally {
takeLock.unlock();
}
}
通过上面的代码可以看到，LinkedBlockingQueue 使用了两个锁，在容量满了或者为空时，用对方的锁去signal。
所以LinkedBlockingQueue在多线程上实现生产者和消费者应该要比ArrayBlockingQueue效率高。
- LinkedBlockingDeque
LinkedBlockingDeque实现上和ArrayBlockingQueue类似，只不过底层使用的是链表，并且是双端队列。详细代码就不用贴了。
通过上面的队列学习，我们应该知道：
- 循环双端队列 ArrayDeque 是如何实现的？
- 阻塞队列是如何实现的以及
ArrayBlockingQueue和LinkedBlockingQueue有什么区别？ - 优先级队列的数据结构
至此，Collection的实现类学习完毕，如果这时候你对Collection类图了然于胸，并且每个实现类的使用场景以及优缺点都整明白了，那么恭喜你，对于集合部分的大部分知识你能应对了。
下面我们会学习常用的映射表， 它的实现中有很多巧妙的算法，很有意思。
参考文档：
https://blog.csdn.net/u013309870/article/details/71478120
https://blog.csdn.net/l540675759/article/details/62893335
Map
- equals 和 hashCode
- put 的操作过程
- 如何解决Hash冲突
- HashTable 和 ConcurrentHashMap 在实现高并发时有什么区别
Map.png
视图
迭代器
- fail-fast 和 fail-safe
- Iterator和ListIterator的区别
- Iterator 和 Enumeration的区别
并发集合
建议
-
LinkedList和ArrayList 的使用场景和区别？
-
Iterator 和 ListIterator 的区别？
-
访问元素的方式？
-
列表和集的使用场景？
列表是有序的，但是对于不关心元素顺序的场景，使用集更高效，因为查找相当于索引访问数组（当然这里也要考虑哈希冲突导致的列表查找） -
队列类似功能方法区别？
-
优先级队列的实现
-
更新一个映射值有那些方式
-
常见的映射表
-
视图
https://www.jianshu.com/p/939b8a672070
https://www.jianshu.com/p/a53b94b2bcca
https://mp.weixin.qq.com/s?__biz=MzI3NzE0NjcwMg==&mid=2650120877&idx=1&sn=401bb7094d41918f1a6e142b6c66aaac&chksm=f36bbf8cc41c369aa44c319942b06ca0f119758b22e410e8f705ba56b9ac6d4042fe686dbed4&mpshare=1&scene=1&srcid=1010L0NNyoRB5lVoryo00awY#rd
http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
