Java提供的容器类如List、Set、Map是语言的基础，熟练掌握是必备技能，本文就Java中容器相关的坑与知识做一个总结整理。本文涉及的代码摘自OpenJDK jdk9-b94，部分逻辑在不同版本的实现有所差异。

List

• ArrayList：非线程安全，由数组实现，擅长随机访问
• Vector：同ArrayList，但是添加了线程安全支持
• LinkedList：非线程安全，由双向链表实现（JDK1.6之前为循环链表），擅长插入、删除操作，不擅长随机访问
• CopyOnWriteArrayList：通过Immutable方式实现了线程安全，由数组实现，性质类似于ArrayList，但是由于CopyOnWrite的逻辑所以不适合大数据量使用

在内存使用方面，ArrayList会在结尾留有一定空闲余量，而LinkedList则是每个节点的内存使用量都比ArrayList大。LinkedList不是线程安全的，如果需要链表实现的线程安全的数据结构建议使用ConcurrentLinkedQueue、ConcurrentLinkedDeque。

Set

• HashSet：无序、唯一、允许Null、非线程安全。底层使用HashMap保存数据
• LinkedHashSet：有序（按插入顺序）、唯一、允许Null、非线程安全。继承自HashSet，内部由LinkedHashMap实现
• TreeSet：有序（可自定义compare顺序）、唯一、不允许Null，非线程安全。由红黑树实现
• CopyOnWriteArraySet：内部由CopyOnWriteArrayList实现，性质类似CopyOnWriteArrayList，但是做了Key的判断

Java没有提供Concurrent开头支持线程安全的Set类型，如果需要使用线程安全的Set我们可以通过线程安全的Map实现相关逻辑，如ConcurrentHashMap，通过put值相同的key来实现key的set属性。

当把对象加入HashSet时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象，这时会调用equals()方法来检查hashcode相等的对象是否真的相同。如果两者相同，HashSet就不会让加入操作成功。

Map

• HashMap：无序、唯一、允许Null、非线程安全。JDK1.8之前由数组+链表组成，1.8之后引入了当链表长度大于阈值（默认8）的时候将链表转为红黑的操作来优化哈希冲突时的搜索效率
• LinkedHashMap：有序（按插入顺序）、唯一、允许Null、非线程安全。继承自HashMap，在HashMap之外按插入顺序维护了一个双向链表以保证遍历对象的有序性
• TreeMap：有序（可自定义compare顺序）、唯一、不允许Null，非线程安全。由红黑树实现
• Hashtable：不允许Null，线程安全。数组+链表实现，为线程安全加了会锁住这个对象的全局锁，性能有较大牺牲，一般不使用
• ConcurrentHashMap：更高效线程安全的Map实现。底层数据结构于HashMap一致。线程安全方面在JDK1.8之前使用Segment对象将数据根据hash值分段，只锁部分数据性能更好。JDK1.8之后摒弃了Segment锁，使用synchronized和CAS来操作，性能进一步提升