导读：map竟然不属于java集合框架的子集？队列也和list一样属于集合的三大子集之一？更有队列的正确使用姿势，一起来看吧！

java中的集合通常指的是collection下的三个集合框架list、set、queue和map集合，map并不属于collection的子集，而是和它平行的*接口。collection下的子集的关系如文章开头图片所示。

本文的重点将会围绕： 集合的使用、性能、线程安全、差异性、源码解读等几个方面进行介绍。

本文涉及的知识点，分为两部分：

第一部分，collection所有子集：

• list => vector、arraylist、linkedlist
• set => hashset、treeset
• queue

第二部分，map => hashtable、hashmap、treemap、concurrenthashmap。

一、list

我们先来看list、vector、arraylist、linkedlist，它们之间的继承关系图，如下图：

可以看出vector、arraylist、linkedlist，这三者都是实现集合框架中的list，也就是所谓的有序集合，因此具体功能也比较近似，比如都提供按照位置进行定位、添加或者删除的操作，都提供迭代器以遍历其内容等。但因为具体的设计区别，在行为、性能、线程安全等方面，表现又有很大不同。

来看它们的主要方法，如下图：

常用方法：

• size 集合个数
• add()/add(int, e) 添加末尾/添加指定位置
• get(int) 获取
• remove 删除
• clear 清空
• ...

1.1 vector

vector是java早期提供的 线程安全的动态数组， 如果不需要线程安全，并不建议选择，毕竟同步是有额外开销的。vector 内部是使用对象数组来保存数据，可以根据需要自动的增加容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。

看源代码可以知道，我们vector是通过 synchronized 实现线程安全的：

public synchronized boolean add(e e) {
    modcount++;
    ensurecapacityhelper(elementcount + 1);
    elementdata[elementcount++] = e;
    return true;
}

vector动态增加容量，源码查看：

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);
}

capacityincrement变量是what？答案如下：

public vector(int initialcapacity, int capacityincrement) {
    super();
    if (initialcapacity < 0)
        throw new illegalargumentexception("illegal capacity: "+
                                           initialcapacity);
    this.elementdata = new object[initialcapacity];
    this.capacityincrement = capacityincrement;
}

vector动态增加容量总结： 由上面的源码可知，如果初始化vector的时候指定了动态容量扩展大小，就增加指定的动态大小，如果未指定，则扩展一倍的容量。

1.2 arraylist

arraylist 是应用更加广泛的动态数组，它本身不是线程安全的，所以性能要好很多。

arraylist的使用与vector类似，但有着不同的动态扩容机制，如下源码：

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);
}

其中“>> 1”是位运算相当于除2，所有arraylist扩容是动态扩展50%.

1.3 linkedlist

linkedlist 顾名思义是 java 提供的双向链表，所以它不需要像上面两种那样调整容量，它也不是线程安全的，它包含一个非常重要的内部类：entry。entry是双向链表节点所对应的数据结构，它包括的属性有：当前节点所包含的值，上一个节点，下一个节点。

1.4 vector、arraylist、linkedlist区别

vector、arraylist、linkedlist的区别，可以从以下几个维度进行对比：

1.4.1 底层实现的区别

vector、arraylist 内部使用数组进行实现，linkedlist 内部使用双向链表实现。

1.4.2 读写性能方面的区别

arraylist 对元素 非末位 的增加和删除都会引起内存分配空间的动态变化，因此非末位的操作速度较慢，但检索速度很快。

linkedlist 基于链表方式存放数据，增加和删除元素的速度较快，但是检索速度较慢。

1.4.3 线程安全方面的区别

vector 使用了synchronized 修饰了操作方法是线程安全的，而 arraylist、linkedlist 是非线程安全的。

如果需要使用线程安全的list可以使用copyonwritearraylist类。

二、map

hashtable、hashmap、treemap 都是最常见的一些 map 实现，是以键值对的形式存储和操作数据的容器类型。

它们之间的关系，如下图：

• hashtable 是早期 java 类库提供的一个哈希表实现，本身是同步的，不支持 null 键和值，由于同步导致的性能开销，所以已经很少被推荐使用。
• hashmap 是应用更加广泛的哈希表实现，行为上大致上与 hashtable 一致，主要区别在于 hashmap 不是同步的，支持 null 键和值等。通常情况下，hashmap 进行 put 或者 get 操作，可以达到常数时间的性能，所以它是绝大部分利用键值对存取场景的首选，比如，实现一个用户 id 和用户信息对应的运行时存储结构。
• treemap 则是基于红黑树的一种提供顺序访问的 map，和 hashmap 不同，它的 get、put、remove 之类操作都是 o（log(n)）的时间复杂度，具体顺序可以由指定的 comparator 来决定，或者根据键的自然顺序来判断。

hashmap 的性能表现非常依赖于哈希码的有效性，请务必掌握 hashcode 和 equals 的一些基本约定，比如：

• equals 相等，hashcode 一定要相等；
• 重写了 equals 也要重写 hashcode；
• hashcode 需要保持一致性，状态改变返回的哈希值仍然要一致；
• equals 的对称、反射、传递等特性；

线程安全： hashtable是线程安全的，hashmap和treemap是非线程安全的。hashmap可以使用concurrenthashmap来保证线程安全。

三、set

set有两个比较常用的子集：hashset、treeset.

hashset内部使用的是hashmap实现的，看源代码可知：

public hashset() {
    map = new hashmap<>();
}

hashset也并不是线程安全的，hashset用于存储无序(存入和取出的顺序不一定相同)元素，值也不能重复。

hashset可以去除重复的值，如下代码：

public static void main(string[] args) {
        set set = new hashset();
        set.add("orange");
        set.add("apple");
        set.add("banana");
        set.add("grape");
        set.add("banana");
        system.out.println(set);
}

编译器不会报错，执行的结果为：[orange, banana, apple, grape]，去掉了重复的“banana”选项。但排序是无序的，如果要实现有序的存储就要使用treeset了。

public static void main(string[] args) {
    set set = new treeset();
    set.add("orange");
    set.add("apple");
    set.add("banana");
    set.add("grape");
    set.add("banana");
    system.out.println(set);
}

输出的结果是：[apple, banana, grape, orange]

同样，我们查看源码发现，treeset的底层实现是treemap，源码如下：

public treeset() {
    this(new treemap<e,object>());
}

treeset也是非线程安全的。

四、queue

queue（队列）与栈是相对的一种数据结构。只允许在一端进行插入操作，而在另一端进行删除操作的线性表。栈的特点是后进先出，而队列的特点是先进先出。队列的用处很大，但大多都是在其他的数据结构中，比如，树的按层遍历，图的广度优先搜索等都需要使用队列做为辅助数据结构。

queue的直接子集，如下图：

其中最常用的就是线程安全类：blockingqueue.

4.1 queue方法

• 添加：add(e) / offer(e)
• 移除：remove() / poll()
• 查找：element() / peek()

注意：

1. 避免add()和remove()方法，而是要使用offer()和poll()添加和移除元素。后者操作失败不会报错，前者会抛出异常；
2. element() / peek() 都为查询第一个元素，不会删除集合，但element()查询失败会抛出异常，peek()不会。

4.2 queue使用

queue<string> queue =  new linkedlist<string>();
queue.offer("a");
queue.offer("b");
queue.offer("c");
queue.offer("d");
system.out.println(queue);
queue.poll();
system.out.println(queue);
queue.poll();
queue.poll();
queue.poll();
system.out.println(queue.peek());
// system.out.println(queue.element()); // element 查询失败会抛出异常
system.out.println(queue);

4.3 其他队列

arrayblockingqueue 底层是数组，有界队列，如果我们要使用生产者-消费者模式，这是非常好的选择。

linkedblockingqueue 底层是链表，可以当做*和有界队列来使用，所以大家不要以为它就是*队列。

synchronousqueue 本身不带有空间来存储任何元素，使用上可以选择公平模式和非公平模式。

priorityblockingqueue 是*队列，基于数组，数据结构为二叉堆，数组第一个也是树的根节点总是最小值。

arrayblockingqueue ：一个由数组结构组成的有界阻塞队列。

linkedblockingqueue ：一个由链表结构组成的有界阻塞队列。

priorityblockingqueue ：一个支持优先级排序的*阻塞队列。

delayqueue：一个使用优先级队列实现的*阻塞队列。

synchronousqueue：一个不存储元素的阻塞队列。

linkedtransferqueue：一个由链表结构组成的*阻塞队列。

linkedblockingdeque：一个由链表结构组成的双向阻塞队列

五、扩展：string的线程安全

关于string、stringbuffer、stringbuilder的线程安全

string是典型的immutable（不可变）类，被声明为final所有属性也都是final，所有它是不可变的，所有拼加、截取等动作等会产生新的string对象。

stringbuffer是为了解决上面的问题，而诞生的，提供了append方法实现了对字符串的拼加，append方法使用了synchronized实现了线程安全。

stringbuilder是jdk 1.5 新出的特性，作为stringbuffer的性能补充，stringbuffer的append方法使用了synchronized实现了线程的安全，但同时也带来了性能开销，在没有线程安全的情况下可以优先使用stringbuilder。

六、总结

list 也就是我们前面介绍最多的有序集合，它提供了方便的访问、插入、删除等操作。

set 是不允许重复元素的，这是和 list 最明显的区别，也就是不存在两个对象 equals 返回 true。我们在日常开发中有很多需要保证元素唯一性的场合。

queue/deque 则是 java 提供的标准队列结构的实现，除了集合的基本功能，它还支持类似先入先出（fifo， first-in-first-out）或者后入先出（lifo，last-in-first-out）等特定行为。这里不包括 blockingqueue，因为通常是并发编程场合，所以被放置在并发包里。

map 是广义 java 集合框架中的另外一部分，map 接口存储一组键值对象，提供key（键）到value（值）的映射。

七、参考资料

《码出高效：java开发手册》

java核心技术36讲：http://t.cn/ewujvwa

oracle docs：