1、Java集合类图
观察此图，总结如下结论：
- 集合类分为了Map和Collection两个大的类别。
- Dictionary、HashTable、Vector、Stack是JDK遗留类且为线程安全的
- Collection有三个继承接口：List、Queue和Set。
依照实现分类
- 实现Map接口的有：EnumMap、IdentityHashMap、HashMap、LinkedHashMap、WeakHashMap、TreeMap
- 实现List接口的有：ArrayList、LinkedList
- 实现Set接口的有：HashSet、LinkedHashSet、TreeSet
- 实现Queue接口的有：PriorityQueue、LinkedList、ArrayQueue
依照内部结构分类
- 底层以数组的形式实现：EnumMap、ArrayList、ArrayQueue
- 底层以链表的形式实现：LinkedHashSet、LinkedList、LinkedHashMap
- 底层以hash table的形式实现：HashMap、HashSet、LinkedHashMap、LinkedHashSet、WeakHashMap、IdentityHashMap
- 底层以红黑树的形式实现：TreeMap、TreeSet
- 底层以二叉堆的形式实现：PriorityQueue
依照并发分类
- 最下方的一个整块都是java.util.concurrent包里面的类，依照包名我们就能够知道这个包里面的类都是用来处理Java编程中各种并发场景的。
2、Java常用集合特性
注：1.6之前linkedList JDK使用双向循环链表，之后则使用双向链表。
1.1、数组与链表的区别
数组是将元素在内存中连续存放，每个元素占用内存相同，通过下标移动来访问数组中的任意元素，这样删除和增加都需要对数组空间重新整理，或增或减。
链表中的元素在内存中并非顺序存储，而是通过存储元素中的指针联系到一起。所以访问元素，需要从头开始，但是删除元素就比较简单，只需要修改元素的指针就可以，元素本身存储的位置不需要改动。
内存角度理解，数组是从栈分配空间，便捷但自由度小；链表是从堆中分配空间，自由度大但是内存管理麻烦。
1.2、ArrayList
基于索引的数据结构，它地底层是数组。他可以以O（1）的时间复杂度对元素访问。使用ArrayList需要注意它是线程异步的，所以如果不考虑线程安全，ArrayList 的效率是比较高的。另外，ArrayList的大小的动态变化的，增长率是50%，所以如果数据量过大它就没有太大的优势。
1.3、LinkedList
以元素列表的形式存储它的数据，每一个元素和它的前一个和后一个元素链接在一起，因此查找某个元素的时间复杂度是O(n)。相对于ArrayList，它的插入添加删除会更快，但是随机的get也就是查询不如ArrayList。
1.4、Vector
底层基于数组实现的，如果集合中的元素数目大于目前集合数组的长度时，Vector增长率为目前长度的100%。Vector 是线程同步的。正是由于Vector使用了synchronized方法，所以性能上比ArrayList要差。
1.5、LinkedHashSet
底层基于链表实现，集成自HashSet，所以同样也是使用HashCode来决定元素的位置，但是它使用链表维护元素的次序。它是非线程安全的。
1.6、TreeSet
底层是以二叉树实现的，主要功能是排序，可以指定一个顺序，对象的存储会按照指定的顺序排列。它是非线程安全的。
1.7、ArrayDeque
双端队列的实现类，继承自AbastractCollection，其内部是通过数组实现的，它是非线程安全的。
1.8、HashMap
通过hashcode对其内容进行查找，底层是通过hash表实现的。在Map中插入删除和定位元素，HashMap都是最佳选择。
1.9、LinkedHashMap
基于链表和哈希表实现的。虽然增加了时间和空间的开销，但是通过维护一个运行于所有条目的双向链表，保证了其对元素迭代的顺序。它是非线程安全的。
1.10、 WeakHashMap
基于链表和哈希实现的，所以也是HashMap的一种实现，他使用弱引用作为内部数据的存储方案，它是简单缓存表的解决方案，非线程安全。
1.11、 TreeMap
实现了SortedMap接口，能够把它保存的记录根据键排序，默认是键值的升序排序，当然也可以指定比较器。
1.12、 IdentityHashMap
最明显的特征是，在检索元素时，条件更为苛刻。HashMap 按照 key1.equals(key2)，而IdentityHashMap是按照key==k来进行检索。
1.13、 ConcurrentHashMap
和 HashMap思路差不多的，但是因为它支持并发操作。简单理解就是，ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承 ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全。同时相比较HashTable锁整个集合的方式而言，ConcurrentHashMap 的并发性更高，在多线程开发中是个不错的选择。1.8之后数据结构发生变化
note：其中hashMap 和ConcurrentHashMap 在1.8之后做过优化，具体参考：
1.7及1.8 Hashmap与ConcurrentHashMap详解_Al1en的博客-CSDN博客_1.7 concurrenthashmap
3、常见面试题
3.1、ArrayList和LinkedList的异同？
ArrayList和LinkedList 底层实现不同，前者数组后者双向循环链表。数组插入和删除元素的时间复杂度受到元素位置的影响，插入末尾还好，如果是中间，则时间复杂度接近于O(n)，链表使用指针所以插入和删除不需要挪动元素位置，只需要改变指针位置，时间复杂度接近O(1)，对于访问，数组却优于链表。所以两者刚好相反，数组访问快，增删慢。链表增删快，但访问慢。另外，ArrayList的空间浪费体现在List的结尾预留容量，LinkedList体现在每一个元素都要消耗额外空间维护链表关系（直接后继和直接前驱以及数据）。
3.2、HashMap 和 HashTable的区别？
- 线程安全，HashMap是非线程安全的，HashTable是线程安全的；这是因为HashTable内部的方法基本都被Synchronized修饰过。
- 效率，因为线程安全的问题，HashTable会比HashMap效率低一下，而且HashTable也基本被淘汰
- 对null key 和value的支持，HashMap对于null的键值都支持，HashTable不支持null 的key，否则会NPE
- 初始容量和扩容，Table默认11，扩容为2n+1,Map默认16,扩容为二倍。另外HashMap 会为指定容量扩容二倍。
- 底层结构，JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制
3.3、HashMap和HashSet区别？
两者都是基于HashMap实现的，前者是Map接口，后者是Set接口，存储分别是键值对与对象，前者使用key计算Hash 值，后者使用对象，所以需要使用equals方法来判断对象的相等性。
这里引出额外问题：
- 如果两个对象相等，则hashCode也一定相等，equals方法也返回true
- 两个对象的hashcode值相等，则对象不一定相等
所以需要注意：
- equals方法被覆盖，则hashcode一定需要被覆盖，这是因为hashcode的默认行为是对堆上的对象产生独特值，如果没有重写hashcode，则两个class对象无论如何都不会相等（即使他们指向了相同的数据）。
- "==" 是判断两个变量或者实例是不是指向同一个内存空间equals是判断两个对象或实例所指向的内存空间的值是不是相同。所以==是指堆内存地址进行比较，equals则是对内容进行比较，或者说前者是引用是否相等，而后者则是值是否相等。
3.4、HashMap的底层实现。
JDK1.8以前，HashMap底层是数组和链表组合在一起使用也就是链表散列。HashMap通过Key的hashcode经过扰动函数处理后得到的hash值，然后通过(n-1)&hash判断当前元素存放的位置（这里的n指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素hash值以及key是否相等，如果相等，直接覆盖，如果不相同就通过拉链法解决冲突。 所谓扰动函数就是HashMap 的hash方法。使用扰动函数是为了减少hash碰撞。较之1.7的hash方法，1.8减少了扰动次数。所以性能有些许提升。
所谓拉链法，就是将链表和数组相结合，也就是说创建一个链表数组，数组中每一格都是一个链表，若是遇到hash冲突，则将冲突的值加入到链表即可。
较之1.7在解决hash冲突方面，1.8有较大的变化。当链表长度大于阈值（default 8），则将链表转换为红黑树后判断，如果当前数组的长度小于64，则先进行扩容，而不是转换红黑树。以便减少搜索时间。 TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。红黑树是为了解决二叉树在某些条件下退化为一个线性结构的缺陷。
3.5、HashMap的长度为什么总是2的幂次方？
HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法；这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算，源码中做了优化hash&(length-1)，如下是截取自resize方法。
newTab[e.hash & (newCap - 1)] = e;
hash%length==hash&(length-1)的前提是length是2的n次方；
为什么这样能均匀分布减少碰撞呢？2的n次方实际就是1后面n个0，2的n次方-1 实际就是n个1；
例如长度为9时候，3&(9-1)=0 2&(9-1)=0 ，都在0上，碰撞了；
例如长度为8时候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞；其实就是按位“与”的时候，每一位都能 &1 ，也就是和1111……1111111进行与运算
3.6、HashMap多线程导致死循环问题
HashMap本身就不是线程安全的，在并发的情况，发生扩容时，多个线程同时对table进行扩容，扩容后rehash的链表可能会产生循环链表，在执行get的时候，会触发死循环，引起CPU的100%问题，所以一定要避免在并发环境下使用HashMap。
具体参考：HashMap多线程下发生死循环的原因_zhangjunli的博客-CSDN博客
解决方案：
- 使用ConcurrentHashMap
- 使用Collections.synchronizedMap(Mao<K,V> m)方法把HashMap变成一个线程安全的Map
3.7、ConcurrentHashMap和HashTable 的区别？
两者主要区别体现在实现线程安全的方式不同。
底层数据结构，JDK1.7的ConcurrentHashMap底层采用分段的数组+链表实现，1.8采用的数据结构和HashMap一样，数组+链表、红黑树。HashTable和JDK1.8之前的HashMap类似采用数数组+链表，数组是主体，链表是为了解决hash冲突而存在的。
实现线程安全的方式，1.7的时候，ConcurrentHashMap使用分段锁对整个桶数组进行分割分段，没一把锁只锁住容器内的数据，多线程的访问容器里不同数据段的数据，就不会存在锁竞争，提高并发效率。而到1.8则摒弃了Segment 的概念，直接使用Node数组+链表+红黑树来实现，并发控制使synchronized和CAS来个控制。1.6之后对synchronized做了很多优化，虽然仍然可以看到segment的代码 但是是为了兼容旧版本。HashTable使用Synchronized 一把锁确保数据安全，效率低下。
3.8、comparable和comparator的区别？
Comparable & Comparator 都是用来实现集合中元素的比较、排序的，只是 Comparable 是在集合内部定义的方法实现的排序， Comparator 是在集合外部实现的排序，所以，如想实现排序，就需要在集合外定义 Comparator 接口的方法或在集合内实现 Comparable 接口的方法， Comparator 位于包java.util下，而 Comparable 位于包java.lang下。
public int compareTo(T o);
int compare(T o1, T o2);
具体表现，
- Comparable是排序接口。若一个类实现了Comparable接口，就意味着该类支持排序。实现了Comparable接口的类的对象的列表或数组可以通过Collections.sort或Arrays.sort进行自动排序。实现此接口的对象可以用作有序映射中的键或有序集合中的集合，无需指定比较器。
- Comparator是比较接口，我们如果需要控制某个类的次序，而该类本身不支持排序(即没有实现Comparable接口)，那么我们就可以建立一个“该类的比较器”来进行排序，这个“比较器”只需要实现Comparator接口即可。
总结
两种方法各有优劣， 用Comparable 简单， 只要实现Comparable 接口的对象直接就成为一个可以比较的对象，但是需要修改源代码。 用Comparator 的好处是不需要修改源代码， 而是另外实现一个比较器， 当某个自定义的对象需要作比较的时候，把比较器和对象一起传递过去就可以比大小了， 并且在Comparator 里面用户可以自己实现复杂的可以通用的逻辑，使其可以匹配一些比较简单的对象，那样就可以节省很多重复劳动了。
4、特殊问题
4.1、Java中集合的线程安全问题
事实上我们可以注意到，除了遗留的Vector和HashTable，java.util包中的集合都不是线程安全的。这是因为线程安全的代价是性能降低。甚至在相当大的数据操作下，ArrayList速度差不多是Vector的2倍。
为了确保在单线程环境下的性能最大化，所以基础的集合实现类都没有保证线程安全。那么如果我们在多线程环境下如何使用集合呢？其实我们可以手动自己添加synchronized代码块来确保安全，但是使用自动线程安全的线程比我们手动更为明智。
示例：
List<String> safeList = Collections.synchronizedList(new ArrayList<>());
//已存在的集合
Map<Integer, String> unsafeMap = new HashMap<>();
Map<Integer, String> safeMap = Collections.synchronizedMap(unsafeMap);
迭代器本身也是不安全的Iterator，我们可以使用同步代码块来控制，
synchronized (safeList) {
while (iterator.hasNext()) {
String next = iterator.next();
System.out.println(next);
}
}
更明智的做法是，使用java提供的并发包下的并发集合。
一个关于同步集合的缺点是，用集合的本身作为锁的对象。这意味着，在你遍历对象的时候，这个对象的其他方法已经被锁住，导致其他的线程必须等待。其他的线程无法操作当前这个被锁的集合，只有当执行的线程释放了锁。这会导致开销和性能较低。
这就是为什么jdk1.5+以后提供了并发集合的原因，因为这样的集合性能更高。并发集合类并放在java.util.concurrent包下，根据三种安全机制被放在三个组中。
写时复制集合：这种集合将数据放在一成不变的数组中；任何数据的改变，都会重新创建一个新的数组来记录值。这种集合被设计用在，读的操作远远大于写操作的情景下。有两个如下的实现类：CopyOnWriteArrayList 和 CopyOnWriteArraySet.
比对交换集合也称之为CAS（Compare-And-Swap）集合：这组线程安全的集合是通过CAS算法实现的。CAS的算法可以这样理解：
为了执行计算和更新变量，在本地拷贝一份变量，然后不通过获取访问来执行计算。当准备好去更新变量的时候，他会跟他之前的开始的值进行比较，如果一样，则更新值。
如果不一样，则说明应该有其他的线程已经修改了数据。在这种情况下，CAS线程可以重新执行下计算的值，更新或者放弃。使用CAS算法的集合有：ConcurrentLinkedQueue and ConcurrentSkipListMap.采用了特殊的对象锁（java.util.concurrent.lock.Lock）：这种机制相对于传统的来说更为灵活，可以如下理解：
这种锁和经典锁一样具有基本的功能，但还可以再特殊的情况下获取：如果当前没有被锁、超时、线程没有被打断。
不同于synchronization的代码,当方法在执行，Lock锁一直会被持有，直到调用unlock方法。有些实现通过这种机制把集合分为好几个部分来提供并发性能。比如：LinkedBlockingQueue，在队列的开后和结尾，所以在添加和删除的时候可以同时进行。
其他使用了这种机制的集合有：ConcurrentHashMap 和绝多数实现了BlockingQueue的实现类
4.2、更加安全的删除元素
java集合中，list列表应该是我们最常使用的，它有两种常见的实现类：ArrayList和LinkedList。ArrayList底层是数组，查找比较方便；LinkedList底层是链表，更适合做新增和删除。但实际开发中，我们也会遇到使用ArrayList需要删除列表元素的时候。虽然ArrayList类已经提供了remove方法，不过其中有潜在的坑，下面将介绍remove方法的三种错误用法以及六种正确用法。
1、错误：for循环中使用remove(int index)，列表从前往后遍历
首先看一下ArrayList.remove(int index)的源码，读代码前先看方法注释：移除列表指定位置的一个元素，将该元素后面的元素们往左移动一位。返回被移除的元素。
源代码也比较好理解，ArrayList底层是数组，size是数组长度大小，index是数组索引坐标，modCount是被修改次数的计数器，oldValue就是被移除索引的元素对象，numMoved是需要移动的元素数量，如果numMoved大于0，则执行一个数组拷贝（实质是被移除元素后面的元素都向前移动一位）。然后数组长度size减少1，列表最后一位元素置为空。最后将被移除的元素对象返回。
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
如果在for循环中调用了多次ArrayList.remove()，那代码执行结果是不准确的，因为每次每次调用remove函数，ArrayList列表都会改变数组长度，被移除元素后面的元素位置都会发生变化。比如下面这个例子，本来是想把列表中奇数位置的元素都移除，但最终得到的结果是[2,3,5]。
List<Long> list = new ArrayList<>(Arrays.asList(1L, 2L, 3L, 4L, 5L));
for (int i = 0; i < list.size(); i++) {
if (i % 2 == 0) {
list.remove(i);
}
}
//最终得到[2,3,5]
2、错误：直接使用list.remove(Object o)
ArrayList.remove(Object o)源码的逻辑和ArrayList.remove(int index)大致相同：列表索引坐标从小到大循环遍历，若列表中存在与入参对象相等的元素，则把该元素移除，后面的元素都往左移动一位，返回true，若不存在与入参相等的元素，返回false。
3、错误：Arrays.asList()之后使用remove()
Arrays.asList()返回的是一个指定数组长度的列表，所以不能做Add、Remove等操作。至于为啥是返回的是固定长度的，看下面源码，asList()函数中调用的new ArrayList<>()并不是我们常用的ArrayList类，而是一个Arrays的内部类，也叫ArrayList，而且这个内部类也是基于数组实现的，但它有一个明显的关键字修饰，那就是final。都用final修饰了，那是肯定不能再对它进行add/remove操作的。
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
private static class ArrayList<E> extends AbstractList<E>
implements RandomAccess, java.io.Serializable
{
private static final long serialVersionUID = -2764017481108945198L;
private final E[] a;
ArrayList(E[] array) {
a = Objects.requireNonNull(array);
}
}
Arrays.asList()之后需要进行add/remove操作，可以使用下面这种方式：
String[] arr = new String[3];
List list = new ArrayList(Arrays.asList(arr));
4、正确：直接使用removeIf()
removeIf()的入参是一个过滤条件，用来判断需要移除的元素是否满足条件。方法中设置了一个removeSet，把满足条件的元素索引坐标都放入removeSet，然后统一对removeSet中的索引进行移除。
5、正确：在for循环之后使用removeAll(Collection<?> c)
这种方法思路是for循环内使用一个集合存放所有满足移除条件的元素，for循环结束后直接使用removeAll方法进行移除。
6、正确：list转为迭代器Iterator的方式
迭代器就是一个链表，直接使用remove操作不会出现问题。
7、正确：for循环中使用remove(int index), 列表从后往前遍历
因为每次调用remove(int index)，index后面的元素会往前移动，如果是从后往前遍历，index后面的元素发生移动，跟index前面的元素无关，我们循环只去和前面的元素做判断，因此就没有影响。
8、正确：使用while循环
使用while循环，删除了元素，索引便不+1，在没删除元素时索引+1