二、Java集合类
本文最后更新于 2025-03-06，文章超过7天没更新，应该是已完结了~
一、List.*
1. ArrayList列表
ArrayList数组列表，有序可重复。
底层通过数组实现的。初始化对象时，如果没有传大小，则列表的大小为DEFAULT_CAPACITY的默认值10。
/**
* Default initial capacity. 默认的初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;当列表容量不够时，如果继续往列表追加元素，则通过数据拷贝并对原数组进行扩容。扩容方式为"int newCapacity = oldCapacity + (oldCapacity >> 1)"，即newCapacity为10+10/2=15。但如果一次性追加多个元素，比如6个，那么列表的最小容量minCapacity为16，newCapacity小于minCapacity，则将新数组容量取最小容量值newCapacity=minCapacity。
注意：当使用默认构造器时，并不会马上初始化为10的数组，当进行第一次add的时候，elementData将会变成默认的长度：10。
对数组列表进行插入、删除操作时都需要对数组进行移动并重排序。所以如果能知道大概存储多少数据时，尽量初始化初始容量，提升性能。
主要方法：
总结：
1）arrayList可以存放null。
2）arrayList本质上就是一个elementData数组。
3）arrayList区别于数组的地方在于能够自动扩展大小，其中关键的方法就是grow()方法。
4）arrayList中removeAll(collection c)和clear()的区别就是removeAll可以删除批量指定的元素，而clear是全是删除集合中的元素。
5）arrayList由于本质是数组，所以它在数据的查询方面会很快，而在插入删除这些方面，性能下降很多，有移动很多数据才能达到应有的效果。
6）arrayList实现了RandomAccess，所以在遍历它的时候推荐使用for循环。
public boolean add(E e) {
//判断是否可以容纳e，若能，则直接添加在末尾；若不能，则进行扩容，然后再把e添加在末尾
ensureCapacityInternal(size + 1); // Increments modCount!!
//将e添加到数组末尾
elementData[size++] = e;
return true;
}
// 每次在add()一个元素时，arraylist都需要对这个list的容量进行一个判断。通过ensureCapacityInternal()方法确保当前ArrayList维护的数组具有存储新元素的能力，经过处理之后将元素存储在数组elementData的尾部
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 若ArrayList已有的存储能力满足最低存储要求，则返回add直接添加元素；如果最低要求的存储能力>ArrayList已有的存储能力，这就表示ArrayList的存储能力不足，因此需要调用 grow();方法进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// 获取elementData数组的内存空间长度
int oldCapacity = elementData.length;
// 扩容至原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//校验容量是否够
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//若预设值大于默认的最大值，检查是否溢出
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 调用Arrays.copyOf方法将elementData数组指向新的内存空间
//并将elementData的数据复制到新的内存空间
elementData = Arrays.copyOf(elementData, newCapacity);
}
ArrayList遍历删除元素的几种姿势
普通for循环正序删除（结果：会漏掉元素判断）
普通for循环倒序删除（结果：正确删除）
for-each循环删除（结果：抛出异常）
Iterator遍历，使用ArrayList.remove()删除元素（结果：抛出异常）
Iterator遍历，使用Iterator的remove删除元素（结果：正确删除）
让我们来探究一下原因把：
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
arrayList.add(3);
arrayList.add(4);
arrayList.add(5);
removeWayOne(arrayList);
}for (int i = 0; i < arrayList.size(); i++) {
if (arrayList.get(i) == 3) {//3是要删除的元素
arrayList.remove(i);
//解决方案: 加一行代码i = i - 1; 删除元素后，下标减1
}
System.out.println("当前arrayList是"+arrayList.toString());
}
//原ArrayList是[1, 2, 3, 3, 4, 5]
//删除后是[1, 2, 3, 4, 5]可以看到少删除了一个3，因为调用remove删除元素时，调用的是System.arraycopy()方法，将后面的元素移动到前面被删除的位置，也就是第二个3会移动到数下标为2的位置，下一次循环时i+1，检查的是下标为3的位置，所以会忽略到下标为2的位置。连续重复元素，会导致少删除。
解决方案：可以在删除元素后，执行i=i+1；使得下次循环时再对该数组下标进行判断。
private static void removeWayOne(ArrayList<Integer> arrayList) { //普通for循环倒序删除
for (int i = arrayList.size()-1; i >=0 ; i--) {
if (arrayList.get(i)==3){
arrayList.remove(i);
}
System.out.println("当前："+arrayList.toString());
}
} private static void removeWayOne(ArrayList<Integer> arrayList) { //for-each循环删除
for (Integer value :
arrayList) {
if (value.equals(3)) {
arrayList.remove(value);
}
System.out.println("当前"+arrayList.toString());
}
}
我们查看remove()方法的源码
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
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
}remove()方法会调用fastRemove()方法，其中会对modCount+1，代表对数组进行了修改，将修改次数+1。
对removeWayOne()方法进行反编译
0 aload_0
1 invokevirtual #7 <java/util/ArrayList.iterator>
4 astore_1
5 aload_1
6 invokeinterface #8 <java/util/Iterator.hasNext> count 1
11 ifeq 72 (+61)
14 aload_1
15 invokeinterface #9 <java/util/Iterator.next> count 1
20 checkcast #10 <java/lang/Integer>
23 astore_2
24 aload_2
25 iconst_3
26 invokestatic #4 <java/lang/Integer.valueOf>
29 invokevirtual #11 <java/lang/Integer.equals>
32 ifeq 41 (+9)
35 aload_0
36 aload_2
37 invokevirtual #12 <java/util/ArrayList.remove>
40 pop
41 getstatic #13 <java/lang/System.out>
44 new #14 <java/lang/StringBuilder>
47 dup
48 invokespecial #15 <java/lang/StringBuilder.<init>>
51 ldc #16 <当前>
53 invokevirtual #17 <java/lang/StringBuilder.append>
56 aload_0
57 invokevirtual #18 <java/util/ArrayList.toString>
60 invokevirtual #17 <java/lang/StringBuilder.append>
63 invokevirtual #19 <java/lang/StringBuilder.toString>
66 invokevirtual #20 <java/io/PrintStream.println>
69 goto 5 (-64)
72 return可以看到foreach的底层其实是用Array.iterator的hasNext()方法和next()方法 实现的，Iterator.hasNext()来判断是否还有下一个元素，和Iterator.next()方法来获取下一个元素。
我们查看Iter源码
private class Itr implements Iterator<E> {
int cursor; // 游标
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;//期待的modCount值
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();//判断expectedModCount与当前的modCount是否一致
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;//更新expectedModCount
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}在这里，迭代ArrayList的Iterator中有一个变量expectedModCount，该变量会初始化和modCount相等，但如果接下来如果集合进行修改modCount改变，就会造成expectedModCount!=modCount，此时就会抛出java.util.ConcurrentModificationException异常。
结论：当删除完元素，进行下一次循环时，会调用Itr.next()方法获取下一个元素，并调用checkForComodification()方法对ArrayList进行校验，判断在遍历ArrayList时是否被修改，由于使用ArrayList.remove()时modCount+1，跟expectedModCount不一致，所以会抛出异常。
解决办法：使用Itr.remove()方法删除元素后会对expectedModCount更新。
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;//更新expectedModCount
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}注意： iterator.next()方法会将游标往后移动，所以注意单次循环记得只能使用一次该方法
private static void removeWayOne(ArrayList<Integer> arrayList) {
Iterator<Integer> iterator = arrayList.iterator();
while (iterator.hasNext()){
if (iterator.next().equals(3)){
iterator.remove();
}
}
System.out.println(arrayList.toString());
}2. LinkedList双向链表
双向链表，也即每个元素都有指向前后元素的指针。而且链表的顺序读取效率非常高，而随机读取的效率非常低。当随机获取一个index位元素时，链表先比较index和链表长度1/2大小，小于则从链表头部查找元素，大于则从链表尾部查找元素。
public E get(int index) {
// 元素下表的合理性检查
checkElementIndex(index);
// node(index)真正查询匹配元素并返回
return node(index).item;
}
// 作用：查询指定位置元素并返回
Node<E> node(int index) {
// assert isElementIndex(index);
// 如果索引位置靠链表前半部分，从头开始遍历
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;
}对比 ArrayList 如果随机读取数据较多时使用 ArrayList 性能高，插入删除较多时使用 LinkedList 性能高。
由于LinkList实现了Deque<E>接口，所以介绍一下队列的方法
// 作用：在链表头插入指定元素
public void addFirst(E e) {
linkFirst(e);
}// 作用：在链表尾部添加元素e
public void addLast(E e) {
// 上面已讲解过，参考上面。add()方法
linkLast(e);
}// 作用:往链表头部添加元素e
public void push(E e) {
addFirst(e);
}// 作用：得到头元素
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
} // 作用：返回头元素，并且不删除。如果不存在也不报错，返回null
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
} // 作用：返回头节点元素，并删除头节点。并将下一个节点设为头节点。
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
} // 作用：删除头节点，如果头结点为null.则抛出异常
public E pop() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}一般我们这样认为：ArrarList查询和获取快，修改和删除慢；LinkedList修改和删除快，查询和获取慢。
更细节来说：
LinkedList做插入、删除的时候，慢在寻址（遍历指针），快在只需要改变前后Entry的引用地址；
ArrayList做插入、删除的时候，慢在数组元素的批量copy（移动元素），快在寻址。
所以，如果待插入、删除的元素是在数据结构的前半段尤其是非常靠前的位置的时候，LinkedList的效率将大大快过ArrayList，因为ArrayList将批量copy大量的元素；越往后，对于LinkedList来说，因为它是双向链表，所以在第2个元素后面插入一个数据和在倒数第2个元素后面插入一个元素在效率上基本没有差别，但是ArrayList由于要批量copy的元素越来越少，操作速度必然追上乃至超过LinkedList。
总的来说，如果在无法完全确定元素插入、删除的位置，那就选择LinkList。
LinkedList整体插入、删除的执行效率比较稳定，没有ArrayList这种越往后越快的情况；
插入元素的时候，弄得不好ArrayList就要进行一次扩容，而ArrayList底层数组扩容是一个既消耗时间又消耗空间的操作
3. Vector向量
与 ArrayList 一样也是通过数组实现的，不同的是 Vector 是线程安全的，也即同一时间下只能有一个线程访问 Vector，线程安全的同时带来了性能的耗损，所以一般都使用 ArrayList。Vector 的扩容也与 ArrayList 不同，可以设置扩容值，默认每次扩容原来的2倍。
4. Stack栈 LIFO后进先出
Stack 继承自 Vector 所以也是数组实现的，线程安全的栈。他的方法很简单，只有empty()、peek()、pop()、push(Object element)、search(object element)这几个。
二、Map.*(重点)
1.HashMap
底层结构是：数组+链表(JDK1.8增加了红黑树部分，当链表长度大于8时，会将链表转换为红黑树，红黑树结点个数小于6时才转换成链表)，HashMap允许空值和空键
1.确定哈希桶数组索引位置：
HashMap，当插入一个数据时，先对key值做hash，用得到的值与 数组的大小n减1 做& 运算得到桶的位置，i就是桶的位置。在桶中查找有无元素，没有直接插入，有则比较元素key值是否相同，相同用新值替换。桶的位置计算为什么是 (n - 1) & hash？
先看hash值的计算源码:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}HashMap中hash(Object key)的原理，为什么这样做?
首先解释一下h>>>16是什么。
h是hashcode。h>>>16使用来取出h的高16位。
为什么hashCode要和hashCode>>>16异或？
首先看一下源码中hashmap返回索引的源码
private static int indexFor(int h, int length) {
return h & (length-1);
}
我们平时用map大多数情况下map里面的数据不是很多，绝大多数情况下数组length的长度都会小于2^16，所以始终是h的低16位与（length-1）进行&运算。
为什么要用hash值和自己的低16位异或？
自己的高半区和低半区做异或，就是为了保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销
希值更随机则返回的索引更随机，目的是为了减少hash冲突--->减少对象在同一个索引的概率---->降低链表长度的增加--->遍历链表取值的效率就不会过低
总结：
由于和（length-1）运算，length 绝大多数情况小于2的16次方。所以始终是hashcode 的低16位（甚至更低）参与运算。要是高16位也参与运算，会让得到的下标更加散列。
所以才有hash(Object key)方法。让他的hashCode()和自己的高16位^运算。
扩展：
数组下标的计算方法 (n - 1) & hash。为什么要-1？
取余(%)操作 中如果除数是2的幂次 则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。 并且 采用二进制位操作 &，相对于%能够提高大约10倍的运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。
那么 a % b 操作为什么等于 a & ( b - 1 )呢? (前提是b等于2的n次幂)
举例说明:
若 a = 10 , b = 8 , 10与8取余应得2.
8的二进制为: 1000 ; 7的二进制为: 0111；10的二进制1010
也就是说，2n-1这样的数的二进制都是如000111111这样前半部分是0后半部分是1的形式.。
所以, 用2n-1这样的数 & 另一个数 就相当于 这两个数取余。
2.HashMap的扩容机制
初始化参数
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;前者是初始化容量 16，即新建一个 HashMap 的时候，如果不指定长度，则容量为 16（自定义初始容量会自动转化为比当前数大的2的幂次方的数）。
后者是加载因子，即当实际长度除以容量高于该因子的时候，进行扩容操作。默认为 0.75，所以 HashMap 空间占用大于 3/4 的时候就开始扩容了。扩容后的容量是原来的两倍。
插入方式
jdk1.8采用尾插法将原数组元素拷贝到新数组，这样链表元素的相对位置没有变化，但是jdk1.7采用头插法，这样链表的元素会倒置，在多线程情况下，会导致两个线程中出现元素相互指向形成循环列表，而1.8采用尾插法不会出现这种情况。
重新确定索引
jdk1.7中遍历链表元素并重新计算hash值确定新数组的下标，jdk1.8则进行了优化：
由于扩容机制设置为原来数组长度的两倍，即2次幂的扩展，那么length-1和元素的hash值进行&运算后，和扩容前的区别就是高一位可能是0或者1
因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点
通过哈希算法从寻止上能够高效的找到对应的下标，但是随着数据的增长，哈希冲突碰撞过多。在寻找数据时，先找到链表，然后通过遍历在寻找对应数据，如此将会使得 get 数据效率越来越低。在 JDK1.8 中，链表元素数量大于等于 8 可能会重组该链表结构形成为“红黑树结构”(不一定，看下面源码)，这种结构使得在 hash 冲突碰撞过多情况下，get效率比链表的效率高很多。
5.关于树化
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
如果table为null,或者大小还没有到64，暂时不进行树化，而是进行扩容
树化后若结点被删除了很多，则可能会剪枝，变成链表
resize();
}关于HashMap的重点源码
1.执行构造器，初始化加载因子 0.75，HashMap$Node[] table=null
// 2.执行put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 3.计算得到key的hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 4.执行putVal()
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)
n = (tab = resize()).length;
//Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 说明table为Node结点,第一次扩容到16
if ((p = tab[i = (n - 1) & hash]) == null) //通过hash得到索引位置，判断是否为null
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //hash值相同或key是同一个对象或Key的内容相同，则替换
e = p;
else if (p instanceof TreeNode) //如果当前的table的已有的Node 是红黑树，就按照红黑树的方式处理
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);
if (binCount >= TREEIFY_THRESHOLD - 1) // 加入后，判断当前链表的个数是否已经到8个，到8个后就调用treefyBin 方法进行束化
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; //每增加一个Node ,就size++
if (++size > threshold)//若size>临界值，就扩容
resize();
afterNodeInsertion(evict);
return null;
}性能：在没有哈希冲突的情况下，HashMap 存取元素的时间复杂度是 O(1)，但是这只是理想情况。当冲突不多的时候，重复元素以链表形式存储，时间复杂度是 O(n)，当数据量大的时候，链表转换为红黑树，时间复杂度变成 O(logn)
3.put方法流程:
1、判断存放entry的数组table是否为空数组，为空则先初始化;
2、key如果为空，则统一放在数组中索引为0的位置，因为null的hash值总是0，在putForNullKey(value)方法中可以看到;
3、key不为空，对key进行hash得到"尽可能唯一"的hash值;
4、根据hash值和数组length-1通过&运算得到该entry在数组中的索引值 i;（放在数组的位置取决于hash值）
5、判断key是否和数组中索引为i的位置已有相同的key，相同则用新值覆盖旧值;
6、不相同则调用addEntry()方法，有两种情况，一种是链表形式直接遍历到尾端插入，一种是红黑树按照红黑树结构插入。
7、链表数量大于阈值8，则转换成红黑树的结构
8、添加成功后检查是否需要扩容put方法里面解决了两个关键性问题：
其一是由hash值和数组长度经过&运算得到的索引值，通过这个索引能快速定位到该entry(key,value)。
其二是解决hash冲突的问题。当生成了两个hash值相同但是它们对应的key又不相同时，就发生了hash冲突，这时hashmap的实现里面的链表就发挥作用了，通过代码可知hashmap集合里的数组结构中存放的是Entry，里面有key、value、next、hash属性，这里的next指向的就是下一个entry，也就是说，发生hash冲突的多个Entry，先进的会放在链表头部，通过next属性"链式的"指向下一个entry对象，简图如下:
get方法相对简单，好理解。如果key=null，直接获取数组下标为0的entry，否则根据hash值找到数组中的Entry，如果Entry中的next指向不为空，说明是链表结构，则循环链表判断key是否相等，相等直接返回对应Entry的value值，否则返回null。
这里可以看到，当链表长度非常大的时候（说明hash冲突较多），遍历链表取值操作是比较耗性能的，因为链表索引定位数据慢，修改或新增操作快，尤其是当元素位于链表的最末端时，复杂度是O(n)。
这里要注意的是，作为hashmap对象的key一定要同时重写hashcode和equals方法。
原因：
public int hashCode():HashCode是根类Obeject中的方法。默认情况下，Object中的hashCode() 返回对象的32位jvm内存地址与hash函数的运算结果。也就是说如果对象不重写该方法，则返回相应对象的32为JVM内存地址。
public bollean equals()：Object类中的equals方法内部使用的就是==比较运算符，也即还是比较内存地址。
hash,hashcode和hash表的关系？
一丶首先了解一下hashcode是什么？
1、hash和hash表是什么？
hash是一个函数，该函数中的实现就是通过一种算法来得到一个hash值（hashcode）。通过hash算法得到的hash值就在这张hash表中。
2、hashcode
hashcode就是通过hash函数得来的，hashcode在hash表中有对应的位置。
每个对象都有hashcode，那么该对象的hashcode怎么得来的？
通过对象的物理地址转换成一个整数，然后该整数通过hash函数的算法得到了hashcode。
二丶hashcode有什么作用呢？
1.hashcode的存在主要是为了查找的快捷性，HashCode是用来在散列存储结构中确定对象的存储地址的。
为什么hashcode就查找的更快，比如：我们有一个能存放1000个数这样大的内存中，在其中要存放1000个不一样的数字，用最笨的方法，就是存一个数字，就遍历一遍，看有没有相同得数，当存了900个数字，开始存901个数字的时候，就需要跟900个数字进行对比，这样就很麻烦，很是消耗时间，用hashcode来记录对象的位置，来看一下。
hash表中有1、2、3、4、5、6、7、8个位置，存第一个数，hashcode为1，该数就放在hash表中1的位置，存到100个数字，hash表中8个位置会有很多数字了，1中可能有20个数字，存101个数字时，他先查hashcode值对应的位置，假设为1，那么就有20个数字和他的hashcode相同，他只需要跟这20个数字相比较(equals)，如果每一个都相同，那么就放在1这个位置，这样比较的次数就少了很多，实际上hash表中有很多位置，这里只是举例只有8个，所以比较的次数会让你觉得也挺多的，实际上，如果hash表很大，那么比较的次数就很少很少了。
三、equals方法和hashcode的关系？
1、如果两个对象equals相等，那么这两个对象的HashCode一定也相同
2、如果两个对象的HashCode相同，不代表两个对象就相同，只能说明这两个对象在散列存储结构中，存放于同一个位置。因为HashCode是通过对象的内存地址进行hash运算得来的，假设 散列算法是 除10 取余，那么 对象A内存地址假设为 101，则对象A的hashcode为1， 对象B内存地址假设为201 ，则对象B的hashcode为1。AB两个对象地址不同 是不同的对象，但是他们的hashcode还是相同的。
四、为什么equals方法重写的话，建议也一起重写hashcode方法？
比如：有个A类重写了equals方法，但是没有重写hashCode方法，看输出结果，对象a1和对象a2使用equals方法相等，按照上面的hashcode的用法，那么他们两个的hashcode肯定相等，但是这里由于没重写hashcode方法，他们两个hashcode并不一样，所以，我们在重写了equals方法后，尽量也重写了hashcode方法，通过一定的算法，使他们在equals相等时，也会有相同的hashcode值。
扩展：
如果 HashMap 的 key 是自定义类，需要重写hashCode()方法，并且由于 HashMap 的效率高度依赖hashCode()，需要保证散列分布尽量均匀。
为什么hashmap里的key经常使用string，并且不需要重写hashcode和equals方法？
在《Java 编程思想》中有这么一句话：设计 hashCode() 时最重要的因素就是对同一个对象调用 hashCode() 都应该产生相同的值。String 类型的对象对这个条件有着很好的支持，因为 String 对象的 hashCode() 值是根据 String 对象的内容计算的，并不是根据对象的地址计算。
下面是 String 类源码中的 hashCode() 方法：String 对象底层是一个 final 修饰的 char 类型的数组，hashCode() 的计算是根据字符数组的每个元素进行计算的，所以内容相同的 String 对象会产生相同的散列码。
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i]; //31 是一个质数，与质数相乘得到的结果比其他方式更容易产生唯一性， 产生 hash 值重复的概率比较小，冲突概率小
}
hash = h;
}
return h;
}
2. LinkedHashMap
LinkedHashMap继承自HashMap，它的多种操作都是建立在HashMap操作的基础上的。同HashMap不同的是，LinkedHashMap维护了一个Entry的双向链表，且保证了插入的Entry中的顺序。这也是Linked的含义。结构图如下：
/**
* LinkedHashMap中的node直接继承自HashMap中的Node。并且增加了双向的指针
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
LinkedHashMap主要元素：
* 头指针，指向第一个node
transient LinkedHashMap.Entry<K,V> head;
* 尾指针，指向最后一个node
transient LinkedHashMap.Entry<K,V> tail;
* 一个条件变量，它控制了是否在get操作后需要将新的get的节点重新放到链表的尾部
final boolean accessOrder;LinkedHashMap
维护链表的操作：afterNodeRemoval，afterNodeInsertion，afterNodeAccess。这三个方法的主要作用是，在删除，插入，获取节点之后，对链表进行维护。（重点）
//学习一下如何优美得再双向链表中删除节点
void afterNodeRemoval(Node<K,V> e){
LinkedHashMap.Entry<K,V> p=(LinkedHashMap.Entry<K,V>)e ,b=p.before,a=p.after;
//将p节点的前驱和后继节点置空
p.before=p.after=null;
//b为null,说明p时头节点
if(b==null)
head=a;
else
b.after=a;
//a为null，表明p是尾节点
if(a==null)
tail=b;
else
a.before=b;
} public class AfterNodeAccess {
/**
* 1.只有 accessOrder 是 true 才会调用该方法
* 2.使用 get 方法会访问到节点，从而触发调用这个方法
* 3.使用 put 方法插入节点，如果key 存在，也会调用该方法
* 4.这个方法会把访问到的节点重新插入双向链表结尾
*/
void afterNodeAccess(Node<K,V> e){
LinkedHashMap.Entry<K,V> last; //1.表示插入 e 前的尾结点 2.也可以表示插入e后，e的前一个节点
if(accessOrder && (last=tail) != e){ //如果访问的节点不是尾结点
/*
p：当前节点
b：前一个节点
a：后一个节点
结构：b<=>p<=>a
*/
LinkedHashMap.Entry<K,V> p=(LinkedHashMap.Entry<K,V>)e,
b=p.before,a=p.before;
p.after=null; //结构：b<=>p<-a
if(b==null) //如果p是头结点 那么头结点该为a
head=a;
else //如果p不是头尾节点,则将p的前后节点连接 结构：b->a
b.after=a;
if(a!=null) //结构 b<=>a
a.before=b; //在开始的if判断已经肯定p不是尾结点，所以a肯定不为空
-----------------------------------------------------------------------
//如果这是空链表，则之间将p改为头结点
if(last==null)
head=p;
else{ //否则将p插入链表尾部
p.before=last;
last.after=p;
}
tail=p;
++modCount; //访问总次数
}
}
}
在访问元素时，会根据accessOrder为true来执行afterNodeAcess方法，将被访问结点放到链表尾巴；如果插入元素时，不止会调用该方法将结点放到链表尾巴，还会调用afterNodeInsertion方法，该方法有一个回调函数removeEldestEntry来判断是否删除链表尾巴元素。
// 那么这个方法是干嘛的呢，这个就是著名的 LRU 算法啦
// 在插入完成之后，需要回调函数判断是否需要移除某些元素！
/**
* 插入新节点才会触发该方法，因为只有插入新节点才需要内存
* 根据 HashMap 的 putVal 方法, evict 一直是 true
* removeEldestEntry 方法表示移除规则, 在 LinkedHashMap 里一直返回 false,我们可以重写该方法，使其变成经典的LRU算法
*/
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// 根据条件判断是否移除最近最少被访问的节点
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
// 移除最近最少被访问条件之一，通过覆盖此方法可实现不同策略的缓存
// LinkedHashMap是默认返回false的，我们可以继承LinkedHashMap然后复写该方法即可
// 例如 LeetCode 第 146 题就是采用该种方法，直接 return size() > capacity;
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}所以实现LRU算法的关键是实现removeEldestEntry算法，设置判断条件来进行删除最近最久未使用元素。
3. TreeMap丶HashTable
（1）TreeMap：基于红黑二叉树的NavigableMap的实现，线程非安全，不允许null，key不可以重复，value允许重复，存入TreeMap的元素应当实现Comparable接口或者实现Comparator接口，会按照排序后的顺序迭代元素，两个相比较的key不得抛出classCastException。主要用于存入元素的时候对元素进行自动排序，迭代输出的时候就按排序顺序输出。
（2）Hashtable 与 HashMap 的简单比较
HashTable 基于 Dictionary 类，而 HashMap 是基于 AbstractMap。Dictionary 是任何可将键映射到相应值的类的抽象父类，而 AbstractMap 是基于 Map 接口的实现，它以最大限度地减少实现此接口所需的工作。
HashMap 的 key 和 value 都允许为null，而 Hashtable 的 key 和 value 都不允许为null。HashMap 遇到 key 为null的时候，调用putForNullKey方法进行处理，而对 value 没有处理；Hashtable遇到null，直接返回NullPointerException。
Hashtable 方法是同步，而HashMap则不是。我们可以看一下源码，Hashtable 中的几乎所有的 public 的方法都是synchronized的，而有些方法也是在内部通过synchronized代码块来实现。
HashMap的初始容量为 16，Hashtable初始容量为 11，两者的填充因子默认都是0.75。
两者计算 hash 的方法不同
Hashtable 计算 hash 是直接使用 key 的 hashcode 对 table 数组的长度直接进行取模
java int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length;
四、Set.*
插入的数据具有唯一性，则使用Set集合。
HashSet底层使用的是HashMap。
TreeMap和TreeSet都能分别对键，数据进行排序，它们的相同点：
都不是线程安全的
时间复杂度为O(logN)，而HashMap/HashSet为O(1)
它们都是有序的集合，存储的键/数据都是排好序的
实际上TreeSet底层还是使用TreeMap来存储数据，跟HashSet和HashMap关系相似。TreeMap采用一种被称为“红黑树”的排序二叉树来保存Map中的每个Entry——每个Entry都被当做红黑树的一个节点来对待；
TreeSet初始化的时候会new 一个TreeMap进行初始化；
private transient NavigableMap<E,Object> m;
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet() {
this(new TreeMap<E,Object>());
}不同点：
TreeSet和TreeMap实现的接口规范不同，分别实现Set和Map接口。
TreeSet不能存放重复对象，而TreeMap可以
TreeMap的底层采用红黑树
最佳实践
什么是快速失败fail fast?
fast-fail是Java集合的一种错误机制。当多个线程对同一个集合进行操作时，就有可能会 产生fast-fail事件。例如：当线程a正通过iterator遍历集合时，另一个线程b修改了集合的 内容，此时modCount（记录集合操作过程的修改次数）会加1，不等于 expectedModCount，那么线程a访问集合的时候，就会抛出 ConcurrentModificationException，产生fast-fail事件。边遍历边修改集合也会产生fast-fail事件。
解决方法：
使用Colletions.synchronizedList方法或在修改集合内容的地方加上synchronized。这 样的话，增删集合内容的同步锁会阻塞遍历操作，影响性能。
使用CopyOnWriteArrayList来替换ArrayList。在对CopyOnWriteArrayList进行修改操作 的时候，会拷贝一个新的数组，对新的数组进行操作，操作完成后再把引用移到新的 数组。
什么是安全失败fail safe?
采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原 有集合内容，在拷贝的集合上进行遍历。java.util.concurrent包下的容器都是安全失败， 可以在多线程下并发使用，并发修改。
原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改 并不能被迭代器检测到，所以不会触发Concurrent Modification Exception。
缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭 代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。
讲一下ArrayDeque？
ArrayDeque实现了双端队列。内部使用循环数组实现，默认大小为16，它的特点有：
在两端添加，删除元素的效率较高
根据元素内容查找和删除的效率比较低
没有索引位置的概念，不能根据索引位置进行操作
ArrayDeque和LinkedList都实现了Deque接口，如果只需要从两端进行操作，ArrayDeque效率更高，如果需要根据索引位置进行操作，或者经常需要在中间进行插入和删除（LinkedList有相应的API），则应选择LinkedList。
ArrayDeque和LinkedList都是线程不安全。
迭代器Iterator是什么？
Iterator模式用同一种逻辑来遍历集合。它可以把访问逻辑从不同类型的集合类中抽象出来，不需要了解集合内部实现便可以遍历集合元素，统一使用Iterator提供的接口去遍历。它的特点是更加安全，因为它可以保证在，当前遍历的集合元素被更改的时候，就会抛出ConcurrentModificationException异常。
主要有三个方法: hasNext(),next()和remove()。
Iterator和ListIerator有什么区别？
ListIerator 是 Iterator的增强版。
ListIerator 遍历可以是逆向的，因为有previous()和hasPrevious()方法，而iterator不可以。
ListIerator 有 add()方法，可以向List添加对象，而iterator不可以
ListIerator 可以定位当前索引的位置，因为有nextIndex()和priviousInde()方法，而iterator不可以。
ListIterator可以实现对象的修改，使用set()方法。而iterator不行
ListIterator只适用于List及其子类，Iterator可以用于所有集合。
五、Concurrent.*
Java的CAS会使用现代处理器上提供的高效机器级别原子指令，这些原子指令以原子方式对内存执行读-改-写操作，这是在多处理器中实现同步的关键。同时，volatile变量的读/写和CAS可以实现线程之间的通信。把这些特性整合在一起，就形成了整个concurrent包得以实现的基石。如果我们仔细分析concurrent包的源代码实现，会发现一个通用化的实现模式：
首先，声明共享变量为volatile；
然后，使用CAS的原子条件更新来实现线程之间的同步；
同时，配合以volatile的读/写和CAS所具有的volatile读和写的内存语义来实现线程之间的通信（具体放在Java并发篇）
JDK提供的这些容器大部分在 java.uitl.concurrent 包中
ConcurrentHashMap：线程安全的HashMap
CopyOnWriteArrayList：线程安全的Llist，在读多写少的场合性能非常好，远远好于Vector
ConcurrentLinkedQueue：高效的并发队列，使用链表实现。可以看作是线程安全的LinkedList，这是一个非阻塞队列。
BlockingQueue：阻塞队列接口，JDK内部通过链表、数组等方式实现了这个接口。非常适用于作为数据共享的通道。
ConcurrentSkipListMap：跳表的实现。使用跳表的数据结构进行快速查找。
ConcurrentHashMap
插入数据的时候，假如A线程和B线程同时添加元素，然后计算出了相同的哈希值对应了相同的数组位置，因为此时该位置还没有数据，然后对同一个数组位置添加，B的写入操作就会覆盖A的写入操作造成A的写入数据丢失。那么该怎么解决？
第一反应当然是加锁，HashTable 就是这么做的，使用了synchronized关键字。虽然解决了并发访问的安全性问题，但是性能不怎么样。HashTable 中的增删改、甚至equals、toString方法等等都是方法级的锁，所以同时只能一个线程去操作，导致效率问题。
在JDK1.7及之前版本，ConcurrentHashMap 采用的是 Segment 分段锁，即将数据分为一段一段的存储，然后给每一段数据加一把锁。当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。
在JDK1.8以后，ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS 和synchronized来保证并发安全。 数据结构与 HashMap 1.8 的结构类似，数组+链表/红黑二叉树(链表长度>8 时，转换为红黑树)。synchronized只锁定当前链表或者红黑二树的首结点，相比1.7锁定HashEntry数组，锁粒度更小，支持更高的并发量。
ConcurrentHashMap 的整体性能要优于 HashTable，但是某些场景不能替代 HashTable，例如强一致性的场景，ConcurrentHashMap 的get、size等方法都没有加锁，ConcurrentHashMap 是弱一致性的。
put执行流程？
判断null值
判断key==null 或者 value==null，如果是，抛出空指针异常。
计算hash
根据key计算hash值（结果和hashMap一样，写法不同）
进入for循环，插入或更新元素
如果tab==null || tab.length==0 ，说明数组未初始化
调用initTable()方法初始化tab。（再initTable方法中，为了控制只有一个线程对table进行初始化，当前线程会通过CAS操作对SIZECTL变量赋值为-1，赋值成功才能初始化table，否则调用Thread.yield()方法让出时间片）
如果f==null，说明当前下标没有哈希冲突的键值对
根据key和value创建Node，使用CAS操作设置在当前数组下标下，并且break跳出循环
如果f!=null && f.hash=-1 ，说明存储的是标志结点，表示正在扩容
判断下标存储链表或者是红黑树
对f加sychronize同步锁，然后进行以下判断：
如果f.hash>0，说明当前数组下标存储的是一个链表，f是链表的头结点。
对链表进行遍历，如果有节点跟当前需要插入节点的hash值相同，那么对节点的value进行更新，否则根据key,value创建Node，添加到链表结尾
如果 f instanceof TreeBin，说明当前数组下标存储的是一个红黑树，f是红黑树根节点，调用putTreeVal方法，插入或更新节点。
插入完成后，判断binCount（链表长度），当binCount超过8时，并且数组长度大于64，则转为红黑树。
final V putVal(K key, V value, boolean onlyIfAbsent) {
//ConcurrentHashMap不允许key和value为null，否则抛出异常
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());//计算hash值
int binCount = 0;
for (Node<K,V>[] tab = table;;) {//进入循环
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)//数组如果为空
tab = initTable();//初始化数组
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))//如果发现此数组下标下没有哈希冲突的元素，就直接使用CAS操作将Node设置到此下标下
break;
}
else if ((fh = f.hash) == MOVED)//代表当前下标的头结点是标识节点，代表数组在扩容
tab = helpTransfer(tab, f);//协助扩容
else {//这种是普遍情况，存的是链表或者红黑树，进行插入
V oldVal = null;
synchronized (f) {//加同步锁，避免多线程进行插入
if (tabAt(tab, i) == f) {
if (fh >= 0) {//头结点hash值大于0，此数组下标下代表存的是一个链表
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) {//键值对是新添加的，在链表尾部插入新节点
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
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)//链表长度>=8，转换为红黑树
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}为什么ConcurrentHashMap，HashTable不支持key，value为null？
因为HashMap是非线程安全的，默认单线程环境中使用，如果get(key)为null，可以通过containsKey(key) 方法来判断这个key的value为null，还是不存在这个key，而ConcurrentHashMap，HashTable是线程安全的， 在多线程操作时，因为get(key)和containsKey(key)两个操作和在一起不是一个原子性操作，可能在containsKey(key)时发现存在这个键值对，但是get(key)时，有其他线程删除了键值对，导致get(key)返回的Node是null，然后执行方法时抛出异常。所以无法区分value为null还是不存在key。 至于ConcurrentHashMap，HashTable的key不能为null，主要是设计者的设计意图。
CopyOnWriteArrayList
先讲一下什么是Copy-On-Write，通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行 Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。对 CopyOnWrite 容器进行并发的读的时候，不需要加锁，因为当前容器不会添加任何元素。所以 CopyOnWrite 容器也是一种读写分离的思想，延时更新的策略是通过在写的时候针对的是不同的数据容器来实现的，放弃数据实时性达到数据的最终一致性。
CopyOnWriteArrayList 的实现也不复杂，对有并发风险的操作加了锁。注意这里的内部数组是volatile修饰的，写线程对数组引用的修改对读线程是可见的。由于在写数据的时候，是在新的数组中插入数据的，从而保证读写实在两个不同的数据容器中进行操作。
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock(); //add方法需要加锁
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1); //复制新数组
newElements[len] = e;
setArray(newElements); //原容器的引用指向新容器
return true;
} finally {
lock.unlock();
}
}从JDK1.5开始Java并发包里提供了两个使用CopyOnWrite机制实现的并发容器,它们是CopyOnWriteArrayList和CopyOnWriteArraySet。
ConcurrentLinkedQueue（非阻塞队列）
阻塞队列和非阻塞队列的区别在于，当队列是空时，获取元素不会阻塞等待，而是直接返回失败，其它操作同理。
非阻塞队列。高效的并发队列，使用链表实现。可以看作线程安全的LinkedList，通过CAS操作实现。
非阻塞队列中的几种主要方法:
add(E e)：将元素e插入到队列末尾，如果插入成功，则返回true;如果插入失败(即队列已满)，则会抛出异常
remove() ：移除队首元素，若移除成功，则返回true；如果移除失败(队列为空),则会抛出异常
offer(Ee)：将元素e插入到队列末尾，如果插入成功，则返回true；如果插入失败(即队列已满)则返回false;
poll() ：移除并获取队首元素，若成功，则返回队首元素；否则返回null
peek() ：获取队首元素，若成功，则返回队首元素；否则返回null
对于非阻塞队列，一般情况下建议使用offer，poll和peek三个方法，不建议使用add和remove方法。因为使用offer，poll和peek三个方法可以通过返回值判断操作成功与否，而使用add和remove方法却不能达到这样的效果。
阻塞队列
阻塞队列是 java.util.concurrent 包下重要的数据结构， BlockingQueue 提供了线程安全的队列访问方式：当阻塞队列进行插入数据时，如果队列已满，线程将会阻塞等待直 到队列非满；从阻塞队列取数据时，如果队列已空，线程将会阻塞等待直到队列非空。 并发包下很多高级同步类的实现都是基于 BlockingQueue 实现的。 BlockingQueue 适合 用于作为数据共享的通道。
Java提供的阻塞队列
ArrayBlockingQueue：ArrayBlockingQueue 是一个有界的阻塞队列，其内部实现是将对象放到一个数组里。有界也就意味着，它不能够存储无限多数量的元素。它有一个同一时间能够存储元素数量的上限。你可以在对其初始化的时候设定这个上限，但之后就无法对这个上限进行修改了(译者注：因为它是基于数组实现的，也就具有数组的特性：一旦初始化，大小就无法修改)。
DelayQueue：DelayQueue 对元素进行持有直到一个特定的延迟到期。注入其中的元素必须实现 java.util.concurrent.Delayed 接口。
LinkedBlockingQueue：LinkedBlockingQueue 内部以一个链式结构(链接节点)对其元素进行存储。如果需要的话，这一链式结构可以选择一个上限。如果没有定义上限，将使用 Integer.MAX_VALUE 作为上限。
PriorityBlockingQueue：PriorityBlockingQueue 是一个无界的并发队列。它使用了和类 java.util.PriorityQueue 一样的排序规则。你无法向这个队列中插入 null 值。所有插入到 PriorityBlockingQueue 的元素必须实现 java.lang.Comparable 接口。因此该队列中元素的排序就取决于你自己的 Comparable 实现。
SynchronousQueue：SynchronousQueue 是一个特殊的队列，它的内部同时只能够容纳单个元素。如果该队列已有一元素的话，试图向队列中插入一个新元素的线程将会阻塞，直到另一个线程将该元素从队列中抽走。同样，如果该队列为空，试图向队列中抽取一个元素的线程将会阻塞，直到另一个线程向队列中插入了一条新的元素。据此，把这个类称作一个队列显然是夸大其词了。它更多像是一个汇合点。
