Java中常用数据结构-Collection

发表于 | 分类于 |

java内置的数据结构中主要有Collection和Map两个接口实现的集合结构类，Collection用于存储数组形式的单一对象集合，Map使用Key-Value的键值对结构存储对象的集合。其中Collection结构下又主要有List, Set, Queue三种接口，如常用的ArrayList, LinkedList是List的主要实现，HashSet, TreeSet是Set的实现，PriorityQueue, ConcurrentLinkedQueue是Queue的实现，除此之外，BlockingQueue和Deque也是Queue的常用接口。（基于jdk1.8）

Collection(interface)
java.util.Collection接口是集合类数据结构的根接口，改接口继承了java.lang.Iterator接口，即所有Collection的实现都是可枚举的。该接口具有的功能有：

1
2
3
4
5
6
7
8
9
10
11
12
13
add(E)                              // 向集合中添加一个E类型的元素
addAll(Collection<?>)               // 将一个集合中所有的元素添加到该集合中
clear()                             // 移除所有该集合中的元素
contains(Object)                    // 该集合中是否包含这个Object元素
containsAll(Collection<?>)          // 该集合中是否包含另一个集合中的所有元素
isEmpty()                           // 该集合元素数量是否为0
iterator()                          // 获取该集合的枚举对象
remove(Object)                      // 从该集合中移除Object元素,在字类型的实现中，常给出移除指定索引的元素和指定元素
removeAll(Collection<? extends E>)  // 从该集合中移除另一集合中的所有元素
retainAll(Collection<?>)            // 只保留该集合中包含在指定集合中的元素(可选操作)
size()                              // 获取该集合的元素个数
toArray()                           // 返回该集合的数组
toArray(T[])                        // 返回该集合的数组，如果T[]的长度大于或等于该集合的元素数量则将该集合复制到T[]这个数组中，T[]长度超出的部分置为null

在jdk1.8中，增加了对集合的stream操作，且对interface中增加default关键字，对java.util.Collection接口拓展了以下方法，并使用default实现：

1
2
3
4
parallelStream()                    // 返回一个并行流对象，并将此集合作为其源
removeIf(Predicate<? super E>)      // 从该集合中移除满足该Predicate描述的元素
spliterator()                       // 从该集合中创建一个可分割迭代器(splitable iterator可分割迭代器)
stream()                            // 将这个集合作为源返回一个可序列的流

Collection接口

List(interface)

一种有序的集合，使用这个接口可以精确地控制列表中每个元素被插入的位置。可以通过他们的整数索引(在列表中的位置)访问元素，并搜索列表中的元素。除Collection声明之外的主要功能有：

1
2
3
4
5
6
7
8
9
10
11
12
add(int, E)                             // 将元素E添加到指定位置上
addAll(int, Collection<? extends E>)    // 将另一集合插入到该集合的指定位置上
get(int)                                // 获取该集合上指定位置的元素
indexOf(Object)                         // 获取元素Object在该集合上的位置
lastIndexOf(Object)                     // 获取元素Object在该集合上最后的位置
listIterator()                          // 返回一个列表迭代器
listIterator(int)                       // 从指定位置开始返回一个列表迭代器
set(int, E)                             // 设置该集合指定位置上元素的值
subList(int, int)                       // 返回截取集合的子集合

replaceAll(UnaryOperator<E>)            // 使用运算符(函数变换)覆盖原值
sort(Comparator<? super E>)             // 使用外排序返回排序后的集合

ArrayList

ArrayList基于数组实现，可通过ArrayList()使用默认初始容量大小（10）, ArrayList(capacity)指定初始容量大小, ArrayList(Collection<?>)从另一个集合对象中赋值组装，三种方式构造一个实例。ArrayList可以指定初始容量大小，但是可以无限扩容（也有限制，毕竟记录容量大小的变量类型为int类型，即最大容量为Integer.MAX_VALUE），其扩容策略如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
private void ensureCapacityInternal(int minCapacity) {
    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;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    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);
}

即当向集合中增加一个元素时，先通过ensureCapacityInternal方法判断，并必要时增加数组的容量。在ensureCapacityInternal中，minCapacity值为添加元素后数组允许的最小容量即size+1，当集合中的数组为空数组时，minCapacity重新赋值为默认容量与minCapacity的较大值（其实就是默认容量大小10），并在ensureExplicitCapacity中判断容量是否需要增加。通过grow方法可以看出，当集合中容量不够用时，即将当前容量扩容至当前容量的3/2倍（取整），如果此次增加元素后数组长度达到最大数组长度(Integer.MAX_VALUE - 8)，则直接将新的容量设置为Integer.MAX_VALUE，并将旧数组拷贝到新的大容量的数组中。

注意

  • ArrayList在插入元素的时候需要考虑是否扩容，如果需要减小集合的容量，则可通过trimToSize()方法将当前集合的容量设置为size大小。
  • ArrayList是非线程安全的集合。
  • 使用遍历删除集合中的元素时，不应使用for, while的遍历方式进行元素的删除，应当使用迭代器iterator()去移除。
  • 在明确集合的大小时，应当通过new ArrayList<>(size)手动指定集合的初始容量，而非完全依赖ArrayList的自动扩容去依次递增容量，降低数组赋值带来的额外开销。
  • ArrayList中的elementData是通过transient修饰的，但它却实现了Serializable接口，注意看它的writeObject(ObjectOutputStream)和readObject(ObjectInputStream)，使用transient修饰存储对象是为了只序列化有效的容量，以达到不浪费资源的目的。这点同样适用以下序数据结构列化的实现原因。

Vector

Vector与ArrayList一样，是基于数组实现的集合类型，相对于ArrayList，Vector的所有公有方法都具有synchronized关键字，即Vecotr集合是线程安全的集合，可以通过new Vector()实例化一个默认容量大小的集合,new Vector(int)实例化一个指定容量大小的集合, new Vector(int, int)实例化一个指定容量大小，且指定其容量递增的大小, new Vector(Collection<? extends E>)从另一个集合中创建一个Vector集合。Vector除了是线程安全的集合外，与ArrayList相比，它的容量递增方案也不一样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 未指定容量的情况下，默认Vector的容量为10
 */
public Vector() {
    this(10);
}


private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

与ArrayList一样，minCapacity值为size+1，当插入下一个元素导致容量不够的情况下，Vector将通过grow方法扩容，可以看出，如果未指定capacityIncrement的值(其默认值为0），扩容后他的容量将是原容量的2倍，如果指定capacityIncrement则Vector每次容量递增为指定的大小，这点比ArrayList更为灵活。

注意

  • Vector是线程安全的集合
  • 鉴于在Vector元素超过容量的情况下，如果不指定capacityIncrement，则其扩容为原容量的两倍，故最好初始化Vector对象的时候应选择适当的扩容大小。
  • 与ArrayList一致，在需要移除Vector中的元素的时候，应选择通过迭代器访问的方式移除元素，避免空指针异常。

Stack

Stark（栈）是Vector的子类，即Stack也是线程安全的集合，扩容方案也跟随Vector，不同的是，在实例化Stack的时候，并不提供指定扩容大小的构造声明。栈的使用有以下常用方法：

1
2
3
4
5
push(E)         // 入栈
peek()          // 获取栈顶元素
pop()           // 出栈(通过 peek()获取数组中最后一个元素，再将其删除)
empty()         // 判断是否为空
search(Object)  // 栈中查找(从栈顶开始查找, 即使用 lastIndexOf(Object))

注意

  • Stack是线程安全的栈
  • Stack的声明不能指定其容量和扩容递增大小

LinkedList

LinkedList是基于双向链表的集合，不同于数组类型的集合，它是通过节点依次的链接以达到元素与元素关联成集合的目的。LinkedList中的节点为它的静态内部类Node<E>：

1
2
3
4
5
6
7
8
9
10
11
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

可以看出在LinkedList中的节点除了代表元素本身的item之外还有两个分别指向上一个元素(prev)和指向下一个元素(next)的引用。
LinkedList作为链表方式的实现具有在链表两端进行插入和删除操作，同时也能快速的在指定的位置插入和删除元素，LinkedList的常用操作有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
add(E)                                  // 将元素E包装为Node，追加到链表的最后一个
add(int, E)                             // 将元素E包装为Node，插入到指定位置，包装好Node的prev指针指向该位置前一个元素，next指针指向原来在该位置的元素
addAll(Collection<? extends E>)         // 将另一集合中的元素包装为Node，并依个追加到链表后面
addAll(int, Collection<? extends E>)    // 将另一集合中的元素包装为Node，并依个追加到指定位置后面
addFirst(E)                             // 将元素E包装为Node，追加到链表首部
addLast(E)                              // 同 add(E)
offer(E)                                // 同 add(E)
offerFirst(E)                           // 同 addFirst(E)
offerLast(E)                            // 同 addLast(E)

remove()                                // 移除链表首部第一个元素
remove(int)                             // 移除指定位置的元素
removeFirst()                           // 同 remove()
removeLast()                            // 移除链表尾部的最后一个元素
remove(Object)                          // 从链表首部开始查找，移除指定元素(只移除一个)
removeFirstOccurrence(Object)           // 同 remove(Object)
removeLastOccurrence(Object)            // 从链表尾部开始查找，移除指定元素(只移除一个)

getFirst()                              // 获取链表首部第一个元素，当链表为空时，抛出NoSuchElementException异常
getLast()                               // 获取链表尾部最后一个元素，当链表为空时，抛出NoSuchElementException异常
get(int)                                // 获取指定位置元素

set(int, E)                             // 将指定位置的元素替换

peek()                                  // 获取链表首部第一个元素，当链表为空时，返回 null
peekFirst()                             // 同 peek()
peekLast()                              // 获取链表尾部最后一个元素，当链表为空时，返回 null
element()                               // 同 getFirst()
poll()                                  // 移除链表首部第一个元素，并返回其值，当链表为空时，返回 null
pollFirst()                             // 同 poll()
pollLast()                              // 移除链表尾部最后一个元素，并返回其值，当链表为空时，返回 null

push(E)                                 // 同 addFirst(E), 可以通过 push,pop操作实现栈的功能
pop()                                   // 同 removeFirst()

descendingIterator()                    // 返回从尾部到首部的迭代器
listIterator(int)                       // 返回从首部到尾部的迭代器
spliterator()                           // 创建一个可分割迭代器(splitable iterator可分割迭代器)，当前元素指向首部元素

注意

  • LinkedList是非线程安全的线性表
  • LinkedList是基于节点，通过prev, next指针链接元素实现的双向链表
  • 获取LinkedList中的首部/尾部元素，如果不确定链表是否为空时，应使用peek(),peekFirst(),peekLast()获取，避免NoSuchElementException

CopyOnWriteArrayList

CopyOnWriteArrayList是java.util.concurrent包下的基于数组的List的实现，concurrent包是jdk在为多核CPU编程提供一套类库，关于concurrent包的介绍可以参考http://tutorials.jenkov.com/。故名思议，该集合是基于数组的方式通过复制实现的线程安全的集合，查看它的添加元素的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    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();
    }
}

可以看出，每有一个元素插入，里面的存储数组都会被拷贝一份，并在目标数组中容量+1。

注意

  • 每插入一个元素都会复制一遍旧数组,即写时复制，是个比较吃性能的动态数组。同时，插入元素时不往原存储容器中插入，而是copy一个新的容器，插入完成后再将容器的引用指向新容器，所以在读的时候，发现并没有给读操作加锁，是一种读写分离的实现。同样适用于CopyOnWriteArraySet。

Set(interface)

Set是一个不包含重复元素的集合的根接口

HashSet

HashSet用来存储不包含重复元素的单一对象组成的集合，可以通过new HashSet()实例化一个默认容量(16)的集合，new HashSet(int)实例化一个指定初始容量大小集合，new HashSet(int, float)实例化一个指定容量和负荷系数，new HashSet(Collection<? extends E>()使用另一集合为源实例化一个默认容量，负荷系数为该集合的大小的2.33倍与16取较大值。底层的实现却是通过HashMap作为元素的存储对象，使用HashMap<Key, Value>的Key来存储元素，Value是一个空对象(Object PRESENT = new Object())，因为HashMap是一个Key和Value都可以为null的map类型，故，当Set中插入null时，仅返回false，并不抛出异常:

1
2
3
4
5
6
/**
 * HashSet的add(E)实现
 */
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

HashSet在移除元素的时候，也是通过在map中移除掉对应的Entity，当移除的元素为null或者map中不存在该key值时，返回false：

1
2
3
4
5
6
/**
 * HashSet的remove(Object)实现
 */
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

同时，由于HashSet是通过HashMap的Key存储数据，即它存储的数据是一个无序的集合，故jdk中并不能提供get(index)、remove(index)的方式访问HashSet中的元素，只能通过迭代器的方式访问：

1
2
3
4
5
6
/**
 * HashSet的迭代器就是HashMap中键的迭代结果
 */
public Iterator<E> iterator() {
    return map.keySet().iterator();
}

注意

  • HashSet是非线程安全的(毕竟用来存储HashSet的数据结构HashMap也是非线性安全的)
  • HashSet中元素的访问需通过迭代器的方式访问，它的迭代器就是HashMap中的map.keySet().iterator()

LinkedHashSet

LinkedHashSet是HashSet的子类，除了初始容量及负荷系数的初始化上不一样之外，并没有其他的不同。

SortedSet(interface)、NavigableSet(interface)

故名思议，SortedSet是有序Set的接口，SortedSet提供以下方法：

1
2
3
4
5
6
7
8
comparator()            // 所有有序的Set都需要实现元素的比较器
subSet(E, E)            // 获取两元素之间的子集合
headSet(E)              // 获取该元素E之前的子集合(不包含E本身)
tailSet(E)              // 获取该元素E之后的子集合(包含E本身)
first()                 // 获取Set中的第一个元素
last()                  // 获取Set中的最后一个元素

spliterator()           // 在这个已排序的集合中创建一个可分割的迭代器

NavigableSet是Sorted的拓展接口，集合的有序化之外，还增加了有序集合的可操作方法：

1
2
3
4
5
6
7
8
ceiling(E)              // 返回该Set中大于或等于该元素E的最小元素(包含自身)
descendingIterator()    // 在这个Set中以降序返回一个迭代器
descendingSet()         // 返回该Set的倒序
floor(E)                // 返回该Set中小于或等于该元素E的最大元素(包含自身)
higher(E)               // 返回该Set中大于该元素E的最小元素(不包含自身)
lower(E)                // 返回该Set中小于该元素E的最大元素(不包含自身)
pollFirst()             // 检索并删除第一个元素(最小)，如果该Set为空，则返回null
pollLast()              // 检索并删除最后一个元素(最大)，如果该Set为空，则返回null

以上最小意为comparator排序规则中最小的那个

TreeSet

TreeMap是SortedMap的实现类，既然需要实现有序的不包含重复元素的集合，自然不能使用HashMap来存储元素，而是通过TreeMap作为元素的存储对象，与HashSet类似，TreeSet也是将元素存储在Map的Key中，Value为空对象。因为TreeMap中的Key不可为null值，故TreeSet中也不允许存储null值的元素。

注意

  • TreeSet是不允许插入null值的
  • TreeSet中元素的遍历只能通过iterator迭代

ConcurrentSkipListSet

ConcurrentSkipListSet是java.util.concurrent包下的有序不包含重复元素的集合的实现，基于有序的Map类型ConcurrentSkipListMap实现，除此之外与TreeSet并未有太多不同。

注意

  • 有序的集合中都不能插入null值，因为null并不能调用元素对象中的comparator()方法。

Queue(interface)

队列是用来保存待处理数据的集合，是一种先进先出(FIFO)的数据集合。接口提供的操作有：

1
2
3
4
5
6
add(E)      // 进队列(同offer())
poll()      // 出队列，获取并移除队列头元素，如果队列为空时返回 null
element()   // 获取队列头元素，当队列为空时抛出异常
offer(E)    // 如果可以在不违反容量限制的情况下立即将指定的元素插入到这个队列中。
peek()      // 获取队列头元素，当队列为空时返回 null
remove()    // 移除队列头元素，当队列为空时抛出异常

PriorityQueue

PriorityQueue是一个基于优先级的无界优先级队列，PriorityQueue是基于数组实现，其中有一个私有属性private final Comparator<? super E> comparator;，且通过add(E)方法的实现可以看出，该队列类型中的元素在每次有新元素插入的时候都会调用一次siftUp(int, E)，当有元素出队列时，调用shftDown(int, E)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
 * @param k 插入元素前队列的size
 * @param x 需要插入的元素
 */
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

@SuppressWarnings("unchecked")
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;
}

@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        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;
}
// 

/**
 * @param k 出队列元素的位置(poll()操作时k值为0)
 * @param x 出队列元素
 */
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
        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;
}

@SuppressWarnings("unchecked")
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;
}

通过以上siftUp(int, E),siftDown(int, E)的实现可以看出，元素的插入之后，siftUp操作并不是将队列中的元素进行排序，而只是在插入的元素放在队列的稍后端，siftDown操作也只是将数组中剩下的最小的元素放到队列头，这样点到即止的操作在非排序的情况下实现出队列的元素是队列已有元素的从小到大（即Priority）可以大大的节省排序带来的消耗。我们再看看它的扩容策略：

1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

可以看出，如果插入一个元素，容量不够用的情况下，当前容量小于64时，容量已步长为2的方式递增，如果当前容量大于或等于64，容量增长为当前容量的3/2倍。

注意

  • 队列中插入的元素不能为 null.
  • 每次有元素插入都会部分调整且非排序，故PriorityQueue中的元素是无序存储的。
  • PriorityQueue并非先进先出类型的队列。

ConcurrentLinkedQueue

通过类名就知道，ConcurrentLinkedQueue是基于链接节点，是concurrent包下的队列实现，线程安全的无界队列，该队列遵循先进先出(FIFO)原则。在ConcurrentLinekdQueue中，没有size或lenght记录队列的大小，每次在通过size()获取该队列的大小的时候，都会遍历一次整个队列，统计该队列中元素的个数。可以通过remove(Object)移除队列中的元素，peek()获取队列头部的元素（进入队列最长时间的元素），通过iterator()遍历队列中的元素。

注意

  • ConcurrentLinkedQueue是线程安全的队列
  • ConcurrentLinkedQueue是遵循FIFO原则的队列

BlockingQueue(interface)

BlockingQueue即阻塞队列，对队列的操作，会发生阻塞的情况有：

1、当队列满的时候进行入队操作
2、当队列为空的时候进行出队操作
即当一个线程对该队列操作，遇到阻塞的情况，需要另一线程对该队列操作至该队列达到非阻塞状态，譬如追加元素到已满的队列，发生阻塞，需要另一线程对该队列执行出队操作，入队操作的线程才能跳出阻塞状态继续执行。通过以上特性，阻塞队列是线程安全的。BlockingQueue有以下常用操作：

1
2
3
4
5
6
7
8
9
10
11
add(E)                              // 入队，当队列处于阻塞状态，则等待入队
offer(E)                            // 根据以上线性数据结构的了解，offer操作与add操作一致
put(E)                              // 入队，当队列处于阻塞状态，则等待入队，如果被打断，则抛出 InterruptedException
offer(E, long, TimeUnit)            // 入队，指定允许阻塞等待的时间，如果被打断，则抛出InterruptedException
take()                              // 出队，当队列处于阻塞状态，则等待出队，如果被打断，则抛出InterruptedException
poll(long, TimeUnit)                // 出队，指定允许阻塞等待的时间，如果被打断，则抛出InterruptedException
remainingCapacity()                 // 返回队列理想的大小（容量），即队列元素超过该大小则入队操作将blocking
remove(Object)                      // 移除指定元素Object
contains(Object)                    // 检查队列中是否包含该元素Object
drainTo(Collection<? super E>)      // 移出队列中的所有元素到集合E中，并返回移出元素的数量
drainTo(Collection<? super E>, int) // 移除指定数量队列中的元素到集合E中，并返回移出元素的数量

注意

  • BlockingQueue是线程安全的队列

ArrayBlockingQueue

ArrayBlockingQueue是基于数组实现的，遵循先进先出(FIFO)原则的阻塞队列。既然是阻塞队列，那就会有一个理想的容量，超过该容量之后，再要入队操作则进入阻塞状态。可以通过new ArrayBlockingQueue(int)创建一个指定容量的数组类型阻塞队列（默认在队列遇到阻塞情况时，不保证队列的先进先出原则），new ArrayBlockingQueue(int, boolean)创建一个指定容量，并指定当队列遇到阻塞情况是，是否保证队列的FIFO原则，new ArrayBlockingQueue(int, boolean, Collection<? extends E>)从已有集合中创建一个指定容量的，指定在阻塞情况下是否保证FIFO原则的数组阻塞队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/** The queued items */
final Object[] items;

/** items index for next take, poll, peek or remove */
int takeIndex;

/** items index for next put, offer, or add */
int putIndex;

/** Number of elements in the queue */
int count;
/** Condition for waiting takes */
private final Condition notEmpty;

/** Condition for waiting puts */
private final Condition notFull;

public boolean offer(E e) {
    checkNotNull(e);
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        if (count == items.length)
            return false;
        else {
            enqueue(e);
            return true;
        }
    } finally {
        lock.unlock();
    }
}

private void enqueue(E x) {
    // assert lock.getHoldCount() == 1;
    // assert items[putIndex] == null;
    final Object[] items = this.items;
    items[putIndex] = x;
    if (++putIndex == items.length)
        putIndex = 0;
    count++;
    notEmpty.signal();
}

通过元素的入队实现可以看出，每当有元素入队，入队操作就会使用ReentrantLock上锁。在指定容量的队列中，通过固定数组存储队列的元素，当数组满了（putIndex==items.length）之后，下一个需要入队的元素将追加到数组初始位置，从数组的声明也可看出，已经实例化的队列，其容量是不允许再变更的。元素入队成功之后，给一个signal给notEmptyConditionCondition的用法参考,通知正在Condition变量等待队列的线程从await方法返回，并且在返回前已经获得了锁。它的出队列操作则相反，当有元素出队列时，给dequeue()操作上锁，取出队列头的元素，将数组中该位置置为null, 给notFull()一个signal。

注意

  • ArrayBlockingQueue遵循FIFO
  • ArrayBlockingQueue是有界队列

BlockingQueue还有如 DelayQueue,DelayQueue是一个可以拥有无限容量的阻塞延时队列，该队列的存储通过PriorityQueue实现，拥有PriorityQueue元素优先级的特性，DelayQueue存储的对象都需要实现了Delayed接口。LinkedBlockingQueue, 故名思议是通过Node实现的单向链式阻塞队列，遵循FIFO,默认容量为Integer.MAX_VALUE,也可以指定容量，当队列中元素数量达到入量时，再插入元素将失败。PriorityBlockingQueue, PriorityBlockingQueue是PriorityQueue的阻塞实现，是一个无界优先阻塞队列。SynchronousQueue, 同步阻塞队列，当有元素进入队列时，必须要等这个元素出队列，才能再有元素入队，反之亦然，SynchronousQueue没有容量这一概念，甚至它的容量不是1. TransferQueue, 以及它的实现LinkedTransferQueue, 该类型队列是jdk1.7新增的，有点类似SynchronousQueue, 但功能上比SynchronousQueue丰富，对比可参考Java 7 TransferQueue - Pure Danger或它的译文ivfeve。

Deque(interface)

Deque(“double ended queue”的简写)，是双向队列的接口，是一种可以两端做同样操作的线性集合。商量双向队列的实现有ArrayQueue,ConcurrentLinkedDeque, LinkedList, 以及它的阻塞双向队列实现LinkedBlockingDeque. 很明显，ArrayDeque是基于数组的形式实现的大小可变化的双向队列，遵循FIFO原则，可配置初始容量，默认初始容量为16，当容量不够用时使用翻倍策略扩容。ConcurrentLinkedDeque是基于双向节点实现的无界链式线程安全的双向队列，遵循FIFO原则。LinkedList同时也是List的实现，同时具有双向队列的特性。LinkedBlockingDeque是并发包下的BlockingDeque的实现，基于节点，遵循FIFO的双向队列。

参考