在尽可能短的篇幅里，将所有集合与并发集合的特征，实现方式，性能捋一遍。适合所有”精通java”其实还不那么自信的人阅读。
list
arraylist
以数组实现。节约空间，但数组有容量限制。超出限制时会增加50%容量，用system.arraycopy()复制到新的数组，因此最好能给出数组大小的预估值。默认第一次插入元素时创建大小为10的数组。
按数组下标访问元素–get(i)/set(i,e) 的性能很高，这是数组的基本优势。
直接在数组末尾加入元素–add(e)的性能也高，但如果按下标插入、删除元素–add(i,e), remove(i), remove(e)，则要用system.arraycopy()来移动部分受影响的元素，性能就变差了，这是基本劣势。
linkedlist
以双向链表实现。链表无容量限制，但双向链表本身使用了更多空间，也需要额外的链表指针操作。
按下标访问元素–get(i)/set(i,e) 要悲剧的遍历链表将指针移动到位(如果i>数组大小的一半，会从末尾移起)。
插入、删除元素时修改前后节点的指针即可，但还是要遍历部分链表的指针才能移动到下标所指的位置，只有在链表两头的操作–add(), addfirst(),removelast()或用iterator()上的remove()能省掉指针的移动。
copyonwritearraylist
并发优化的arraylist。用copyonwrite策略，在修改时先复制一个快照来修改，改完再让内部指针指向新数组。
因为对快照的修改对读操作来说不可见，所以只有写锁没有读锁，加上复制的昂贵成本，典型的适合读多写少的场景。如果更新频率较高，或数组较大时，还是collections.synchronizedlist(list)，对所有操作用同一把锁来保证线程安全更好。
增加了addifabsent(e)方法，会遍历数组来检查元素是否已存在，性能可想像的不会太好。
补充
无论哪种实现，按值返回下标–contains(e), indexof(e), remove(e) 都需遍历所有元素进行比较，性能可想像的不会太好。
没有按元素值排序的sortedlist，在线程安全类中也没有无锁算法的concurrentlinkedlist，凑合着用set与queue中的等价类时，会缺少一些list特有的方法。
map
hashmap
以entry[]数组实现的哈希桶数组，用key的哈希值取模桶数组的大小可得到数组下标。
插入元素时，如果两条key落在同一个桶(比如哈希值1和17取模16后都属于第一个哈希桶)，entry用一个next属性实现多个entry以单向链表存放，后入桶的entry将next指向桶当前的entry。
查找哈希值为17的key时，先定位到第一个哈希桶，然后以链表遍历桶里所有元素，逐个比较其key值。
当entry数量达到桶数量的75%时(很多文章说使用的桶数量达到了75%，但看代码不是)，会成倍扩容桶数组，并重新分配所有原来的entry，所以这里也最好有个预估值。
取模用位运算(hash & (arraylength-1))会比较快，所以数组的大小永远是2的n次方， 你随便给一个初始值比如17会转为32。默认第一次放入元素时的初始值是16。
iterator()时顺着哈希桶数组来遍历，看起来是个乱序。
在jdk8里，新增默认为8的閥值，当一个桶里的entry超过閥值，就不以单向链表而以红黑树来存放以加快key的查找速度。
linkedhashmap
扩展hashmap增加双向链表的实现，号称是最占内存的数据结构。支持iterator()时按entry的插入顺序来排序(但是更新不算， 如果设置accessorder属性为true，则所有读写访问都算)。
实现上是在entry上再增加属性before/after指针，插入时把自己加到header entry的前面去。如果所有读写访问都要排序，还要把前后entry的before/after拼接起来以在链表中删除掉自己。
treemap
以红黑树实现，支持iterator()时按key值排序，可按实现了comparable接口的key的升序排序，或由传入的comparator控制。可想象的，在树上插入/删除元素的代价一定比hashmap的大。
支持sortedmap接口，如firstkey()，lastkey()取得最大最小的key，或sub(fromkey, tokey), tailmap(fromkey)剪取map的某一段。
concurrenthashmap
并发优化的hashmap，默认16把写锁(可以设置更多)，有效分散了阻塞的概率，而且没有读锁。 
数据结构为segment[]，segment里面才是哈希桶数组，每个segment一把锁。key先算出它在哪个segment里，再算出它在哪个哈希桶里。
支持concurrentmap接口，如putifabsent(key，value)与相反的replace(key，value)与以及实现cas的replace(key, oldvalue, newvalue)。
没有读锁是因为put/remove动作是个原子动作(比如put是一个对数组元素/entry 指针的赋值操作)，读操作不会看到一个更新动作的中间状态。
concurrentskiplistmap
jdk6新增的并发优化的sortedmap，以skiplist实现。skiplist是红黑树的一种简化替代方案，是个流行的有序集合算法，篇幅所限见入门教程。concurrent包选用它是因为它支持基于cas的无锁算法，而红黑树则没有好的无锁算法。
很特殊的，它的size()不能随便调，会遍历来统计。
补充
关于null，hashmap和linkedhashmap是随意的，treemap没有设置comparator时key不能为null；concurrenthashmap在jdk7里value不能为null(这是为什么呢？)，jdk8里key与value都不能为null；concurrentskiplistmap是所有jdk里key与value都不能为null。
set
set几乎都是内部用一个map来实现, 因为map里的keyset就是一个set，而value是假值，全部使用同一个object。set的特征也继承了那些内部map实现的特征。
hashset：内部是hashmap。 
linkedhashset：内部是linkedhashmap。 
treeset：内部是treemap的sortedset。 
concurrentskiplistset：内部是concurrentskiplistmap的并发优化的sortedset。 
copyonwritearrayset：内部是copyonwritearraylist的并发优化的set，利用其addifabsent()方法实现元素去重，如前所述该方法的性能很一般。 
补充：好像少了个concurrenthashset，本来也该有一个内部用concurrenthashmap的简单实现，但jdk偏偏没提供。jetty就自己封了一个，guava则直接用java.util.collections.newsetfrommap(new concurrenthashmap()) 实现。
queue
queue是在两端出入的list，所以也可以用数组或链表来实现。
–普通队列–
linkedlist
是的，以双向链表实现的linkedlist既是list，也是queue。它是唯一一个允许放入null的queue。
arraydeque
以循环数组实现的双向queue。大小是2的倍数，默认是16。
普通数组只能快速在末尾添加元素，为了支持fifo，从数组头快速取出元素，就需要使用循环数组：有队头队尾两个下标：弹出元素时，队头下标递增；加入元素时，如果已到数组空间的末尾，则将元素循环赋值到数组0，同时队尾下标指向0，再插入下一个元素则赋值到数组[1]，队尾下标指向1。如果队尾的下标追上队头，说明数组所有空间已用完，进行双倍的数组扩容。
priorityqueue
用二叉堆实现的优先级队列，不再是fifo而是按元素实现的comparable接口或传入comparator的比较结果来出队，数值越小，优先级越高，越先出队。但是注意其iterator()的返回不会排序。
–线程安全的队列–
concurrentlinkedqueue/concurrentlinkeddeque
无界的并发优化的queue，基于链表，实现了依赖于cas的无锁算法。
concurrentlinkedqueue的结构是单向链表和head/tail两个指针，因为入队时需要修改队尾元素的next指针，以及修改tail指向新入队的元素两个cas动作无法原子，所以需要的特殊的算法，篇幅所限见入门教程。
priorityblockingqueue
无界的并发优化的priorityqueue，也是基于二叉堆。使用一把公共的读写锁。虽然实现了blockingqueue接口，其实没有任何阻塞队列的特征，空间不够时会自动扩容。
delayqueue
内部包含一个priorityqueue，同样是无界的。元素需实现delayed接口，每次调用时需返回当前离触发时间还有多久，小于0表示该触发了。 
pull()时会用peek()查看队头的元素，检查是否到达触发时间。scheduledthreadpoolexecutor用了类似的结构。
–线程安全的阻塞队列–
blockingqueue的队列长度受限，用以保证生产者与消费者的速度不会相差太远，避免内存耗尽。队列长度设定后不可改变。当入队时队列已满，或出队时队列已空，不同函数的效果见下表：
arrayblockingqueue
定长的并发优化的blockingqueue，基于循环数组实现。有一把公共的读写锁与notfull、notempty两个condition管理队列满或空时的阻塞状态。
linkedblockingqueue/linkedblockingdeque
可选定长的并发优化的blockingqueue，基于链表实现，所以可以把长度设为integer.max_value。利用链表的特征，分离了takelock与putlock两把锁，继续用notempty、notfull管理队列满或空时的阻塞状态。
补充
jdk7有个linkedtransferqueue，transfer(e)方法保证producer放入的元素，被consumer取走了再返回，比synchronousqueue更好，有空要学习下。