Collection、Map接口汇总（下属实现类解析）

Collection、Map是非常常用的数据结构，也是面试的常客，接下来让我们一一讲述，首先看一个大致的关系图，这可是我亲手画的呀~

 Map接口和Collection接口的常用实现类基本已在图片中了，其中橙色为接口，蓝色为对应的实现类，接下来我们逐一介绍这几种类的用法和特点。

Map：以<Key，Value>存储元素，但Key不能重复，否则会发生覆盖，value可以重复。

1. HashMap：底层为数组（初始容量16）+链表（单向的）+红黑树，采用Entry数组来存储key-value对，并通过链表和红黑树解决哈希冲突，key与Value都可以为null（但Key只能有一个为null），线程不安全。
2. HashTable：底层为数组+链表，key与Value都不可以为null，线程安全（效率低，现已很少使用）。
3. TreeMap：底层是红黑二叉树，内部元素有序，线程不安全。
4. ConcurrentHashMap：实现了线程安全的Map，既可以做到线程安全又可以保证性能，采用：分段线程锁+读写锁。

Collection：extends自java.lang.Iterable接口。

• List：将以特定次序存储元素，取出来的顺序可能和放入顺序不同。

1. ArrayList：基于可变数组；内存地址连续；查询效率高，增删效率低；线程不安全。
2. LinkedList：基于双向链表，链表结构中的每一个元素就叫做Node对象；内存地址不连续；查询效率低，增删效率高；线程不安全。
3. Vector：与ArrayList类似，底层为可变数组；但线程安全。由于效率低已被ArrayList取代。

• Set ：元素无序排列，不能含有重复的元素。底层通过Map实现，相当于Map中k-v中的k部分。

1. HashSet：底层为数组（初始容量16）+链表（单向的）+红黑树；元素可以为空；添加对象时，先调用HashCode（）计算哈希值，确定元素位置(hash值相同则调用equals方法)；线程不安全；子类LinkedHashSet元素以存储顺序有序排列。
2. TreeSet：SortedSet接口的实现类；底层为红黑树，默认对元素进行自然排序；线程不安全。