我非常热衷于源码研究，也非常愿意分享我对源码的研究经验。如果读者也想研究源码，可以关注我的分享文章。在分析源码的过程中，我们会选择paw ding解牛的分析，将每一行核心代码都分析清楚，让读者真正理解透彻，以便在以后的访谈中或者独立开发中间件，会有很大的帮助。很大的好处。
前言
本节以上帝视角剖析整个Java容器类，让读者从宏观上把握，一目了然。对于本节涉及的位操作，如果觉得基础不够，可以查看作者专门分析容器类的位操作文章。，从数据结构入手，从假溢出——缺乏顺序队列存储结构过渡到有选择的数据结构，循环队列。通过以图文形式对核心代码进行详尽解析，同时开启容器源码阅读技巧之门，让源码阅读从晦涩到赏心悦目。研究Java容器类的源代码将获得很多好处。1. Java容器类经常出现在面试中，会让你在面试中脱颖而出，把面试官打胖。2. 为你学习数据结构和算法打下坚实的基础。3、让你写出高效性能、更好的代码容错性的高质量代码，考虑问题更全面。
一、Java集合类概述
2.研究经历
整体来说说Java集合源码的研究心得吧。读者要想能够顺利的阅读源码，必须具备两个技能。
1). 位运算能力（位运算性能非常好，有些功能用位运算很容易实现，比如用哈希表容量求2的整数次方）
2). 数据结构能力
Java集合类的每个实现类都基于特定的数据结构。这也是作者在前面3节介绍位操作和树结构的初衷。希望读者能够非常清楚的掌握相应的数据结构。如果这两个能力还不够扎实。关注作者，了解之前的内容。只要具备这两个能力，阅读源码就非常轻松。
对于任何一个容器类，你只需要关注构造函数、添加操作、删除操作、修改操作，以及如何调整这些容器。
我会详细分析，，，这4个核心容器类，把每一行核心代码都用图文的形式解释清楚，因为在我看来，这4个类是整个Java集合类中最有技术含量的，所以有必要解释清楚，读者只要能看懂这4个类的源码，再研究其他容器的源码就很容易了。
3.涉及数据结构和算法
在容器类中，我们看到应用了如下数据结构：
动态数组：内部是动态数组，内部链表数组也是动态扩展的，内部也是动态扩展的数组。链表：它是用双向链表实现的。映射到同一个链表数组的键值对通过单向链表链接起来，其中的每个元素也加入到一个双向链表中，以维护插入或访问顺序。哈希表：是用哈希表实现的，基于它，当然内部也是哈希表。排序二叉树：用红黑树实现（基于排序二叉树）。它在内部使用。当然，它也是一棵红黑树。红黑树可以保持元素的有序性，综合性能高。堆：它是用堆实现的。堆在逻辑上是一棵树，在物理上是一个动态数组。堆可以高效地解决一些其他数据结构难以解决的问题。循环数组：由循环数组实现，通过维护头尾变量实现高效的队列操作。位向量：由位向量来实现。对于只有两种状态，需要集合运算的数据，用位向量表示，用位运算处理，精简高效。
每个数据结构往往包含一定的算法策略，这往往是一种妥协，如：
动态扩容算法：动态数组的扩容策略一般是指数扩容，在两个方面进行平衡。一方面希望减少内存消耗，另一方面希望减少内存分配、移动和复制的开销。哈希算法：将哈希表中的键映射到链表数组的索引的算法。算法要快，同时要尽可能随机均匀。二叉树排序的平衡算法：二叉树排序的平衡很重要。红黑树是一种平衡算法，AVL树是另一种。一方面，平衡算法必须保证尽可能多的平衡，另一方面，它必须最小化整体开销。
4.数据结构分析
1、假溢出——顺序队列存储结构不足
队列是一种特殊的线性表，它的特殊之处在于它只允许在表的前端（front）进行删除操作，在表的后端（rear）进行插入操作。队列是一个有限操作的线性表。插入操作结束的称为队尾，删除操作结束的称为队头。
假设是一个长度为5的数组，初始状态，空队列如图，前后指针都指向下标为0的位置。
然后入队a1,a2,a3,a4，前指针仍然指向下标0的位置，后指针指向下标4的位置
当a1和a2出队时，front指针指向下标2的位置，rear保持不变，如下图，然后进入a5。此时前指针不变，后指针移出数组。
假设这个队列的总数不超过5，但是如果当前继续加入队列，因为数组尾部的元素已经被占用，如果后面再加入，数组越界会发生错误，但实际上，我们的队列是下标的，因为 0 和 1 仍然是空闲的。假溢出
2.优化-循环队列
有一个问题：连续出队时，队头左边的空间没有被充分利用，导致队列容量越来越小。
解题：通过数组实现循环队列，充分利用空间（取模：%）。当记录队列尾部的变量达到数组长度时，检查记录队列头部的变量是否在数组的开头。如果不是，则队列尾部从数组起始位置开始存值，并向后移动。
循环队列的实现方式：
添加一个属性size，记录当前元素个数。目的是在head=rear时通过size=0或者size=array 来区分队列是空的还是队列满的。数组中只存入数组大小-1个元素，保证绕一圈后rear不会等于head，即队列满时rear+1=head，且只有一个空元素在中间。
使用方法：
第二种方式是牺牲一个元素空间来区分空码和满码。
1.对front变量的含义做一个调整：front直接指向数组queue的第一个元素front = 0
2、对rear变量的含义做一个调整：rear指向队列最后一个元素之后的位置，因为希望空出一个空间，约定rear = 0
3.当队列满时，条件为rear+1 % == front [full]
4.当队列为空时，rear == front [empty]
5、我们这样分析的时候，队列中有效数据的个数（rear+-front）%
注意：这5个属性一定要牢牢记住源码，深刻理解。源码就是在这些结论的基础上实现的。从源码分析中，你会切实感受到位操作和数据结构的重要性。
特别是在明源代码中，front = tail = 0 开头。如果将一个元素front添加到队列的头部并逆时针旋转，则将元素tail添加到队列的末尾并顺时针旋转。当front == tail时，表示队列已满，需要扩容。
5.具体代码分析
5.1 实例变量
/**
* The array in which the elements of the deque are stored.
* The capacity of the deque is the length of this array, which is
* always a power of two. The array is never allowed to become
* full, except transiently within an addX method where it is
* resized (see doubleCapacity) immediately upon becoming full,
* thus avoiding head and tail wrapping around to equal each
* other. We also guarantee that all array cells not holding
* deque elements are always null.
*/
transient Object[] elements; // non-private to simplify nested class access
/**
* The index of the element at the head of the deque (which is the
* element that would be removed by remove() or pop()); or an
* arbitrary number equal to tail if the deque is empty.
*/
transient int head;
/**
* The index at which the next element would be added to the tail
* of the deque (via addLast(E), add(E), or push(E)).
*/
transient int tail;5.2 岩心钻头运行分析
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
// Tests "= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity >>= 1;// Good luck allocating 2 ^ 30 elements
}
elements = new Object[initialCapacity];
}1、结论：求出大于上述函数左右的2的第一个整数次方的个数
如果 = 6；最后8。
= 10; 终于16了
注 = 8; 最终也是16岁。
我们这样定义位索引顺序，0-15位
如果n = 0 微信：0011 从左到右，第一个出现1的索引位是11，对应0-10上面位上0和1的排列，经过下面的操作，
一直把n改成0 微信：1111
n |= (n >>> 1);
n |= (n >>> 2);
n |= (n >>> 4);
n |= (n >>> 8);
n |= (n >>> 16);重点分析n |= (n >>> 1); n |= (n >>> 1) ==>> n = (n >>> 1) | 名词；
n >>> 1是将n原来的第11个索引位置设置为0，第10个索引位置为1，|的结果 与n的运算赋值给n，使得n的第11-10个索引位置都为1，即n=0 微信：0011
同样，n |= (n >>> 2); 使得索引位11-8全为1，即n = 0 微信：0011
同样，n |= (n >>> 4); 使得索引位11-4全为1，即n = 0 微信：1011
同样，n |= (n >>> 8); 使得索引位11-0全为1，即n = 0 微信：1111
同样，n |= (n >>> 16); 使得索引位11-0全为1，即n = 0 微信：1111
n+1的结果是0 微信：0000变成2的整数次方
2. 什么时候。是 2 的整数次幂：
(tail-head)&(.-1) 等于 (tail – head)%(.-1)
如果不是2的整数次方，则结论不成立。
如果 m = 8；n = 7, n % m = 7; n = 15, n % m = 7; n = 23, n % m = 7;
根据%值的定义，我们只需要关注从最高位1到最后的m
对于8 ==>> 0微信：1000，即只需要关注1000的4位上位值。
这里有一个严格的证明：
如果n=0微信：1101；mask = 0 微信：1111
证明 n % mask = n & mask
根据%的定义，我们只需要关注右端12的值即可。由于mask的右端有12个1，根据&的定义，1与任意数（0或1）的运算都可以保持原值不变。所以经过n&mask操作后，右边12位对应的值仍然可以正确保持，所以
n % 掩码 = n & 掩码
下面证明如果掩码不是0微信：1111的形式，比如0微信：1111，右端第5个索引的值为0，对该索引位进行&操作。即使那个位的值为1，最后运算后也为0，改变了原来的值，所以只有mask不是2的幂-1的整数源码，n % mask = n & mask才会成立，否则不会成立的，为什么，数组的大小应该做成2的整数次方，正好利用这个特性，要知道，位运算效率很高。
以上两个属性在 中也用到了，请读者牢记。
5.3 构造器
/**
* Constructs an empty array deque with an initial capacity
* sufficient to hold 16 elements.
*/
public ArrayDeque() {
elements = new Object[16];
}
/**
* Constructs an empty array deque with an initial capacity
* sufficient to hold the specified number of elements.
*
* @param numElements lower bound on initial capacity of the deque
*/
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
/**
* Constructs a deque containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator. (The first element returned by the collection's
* iterator becomes the first element, or front of the
* deque.)
*
* @param c the collection whose elements are to be placed into the deque
* @throws NullPointerException if the specified collection is null
*/
public ArrayDeque(Collection c) {
allocateElements(c.size());
addAll(c);
}上面已经详细分析了这个函数的作用，所以整个构造函数应该很容易理解。
5.4 加尾
/**
* Inserts the specified element at the end of this deque.
*
* This method is equivalent to {@link #addLast}.
*
* @param e the element to add
* @return {@code true} (as specified by {@link Collection#add})
* @throws NullPointerException if the specified element is null
*/
public boolean add(E e) {
addLast(e);
return true;
}
/**
* Inserts the specified element at the end of this deque.
*
*
This method is equivalent to {@link #add}.
*
* @param e the element to add
* @throws NullPointerException if the specified element is null
*/
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
/**
* Doubles the capacity of this deque. Call only when full, i.e.,
* when head and tail have wrapped around to become equal.
*/
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;
}[尾巴] = e;
就是把当前元素添加到队列的尾部位置，当然需要让尾部指向下一个位置
分析这段(tail = (tail + 1) & (. – 1)) == head
tail = (tail + 1) & (. – 1) 是让tail指向循环队列的下一个位置
(tail + 1) & (. – 1) == head 表示队列已满，需要扩容。
下面重点分析一下扩展的过程。下图形象地表达了这4行代码的意图。
int r = n - p; // number of elements to the right of p
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);让我们看一个例子。假设原来的长度是8，头尾都是4，现在开始扩充数组，扩充后的长度是16，具体结构如下图所示：
5.5 头部添加
/**
* Inserts the specified element at the front of this deque.
*
* @param e the element to add
* @throws NullPointerException if the specified element is null
*/
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}在head处添加，让head指向之前的位置，给head的位置赋值。head 的前一个位置是 (head – 1) & (. – 1)。开始时，head 为 0，如果 . 是 8，那么 (head – 1) & (. – 1) 将得到 7。
例如执行以下代码
Deque queue = new ArrayDeque(7);
queue.addFirst("a");
queue.addFirst("b");执行后的结果如下图所示
5.6 头部删除
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E removeFirst() {
E x = pollFirst();
if (x == null)
throw new NoSuchElementException();
return x;
}
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;
}比较简单，就是让原来的head置为null，让head指向下一个位置，下一个位置就是
(h + 1) & (. – 1);
就是让头部顺时针旋转。为避免读者混淆，特贴出此图
5.7 视长
/**
* Returns the number of elements in this deque.
*
* @return the number of elements in this deque
*/
public int size() {
return (tail - head) & (elements.length - 1);
}经过前面的分析，很明显
5.8 检查给定元素是否存在
/**
* Returns {@code true} if this deque contains the specified element.
* More formally, returns {@code true} if and only if this deque contains
* at least one element {@code e} such that {@code o.equals(e)}.
*
* @param o object to be checked for containment in this deque
* @return {@code true} if this deque contains the specified element
*/
public boolean contains(Object o) {
if (o == null)
return false;
int mask = elements.length - 1;
int i = head;
Object x;
while ( (x = elements[i]) != null) {
if (o.equals(x))
return true;
i = (i + 1) & mask;
}
return false;
} int mask = elements.length - 1;
int i = head;
i = (i + 1) & mask;上面3行代码是从头到尾遍历比较，当元素为null时，遍历结束，因为中间的元素不能为null。我 = (i + 1) & 面具; 就是让我指向下一个位置。
暂无评论内容