List

List的重要实现有：ArrayList、LinkedList、Vector。
List内容比较简单，需要搞清楚下面这几个问题就可以。

ArrayList和LinkedList对比

ArrayList初始容量和扩容

ArrayList初始容量默认10，扩容1.5倍。

Vector线程安全的实现原理

方法上synchronized加锁实现。

ArrayList构造方法

我们知道ArrayList默认容量是10，那我们对比下ArrayList()、ArrayList(10)、ArrayList(0)三者的区别。

Map

Map是面试中问到最多的Java集合，我们需要关注下HashMap、LinkedHashMap、TreeMap、HashTable、ConcurrentHashMap这些Map的子类。

HashMap

HashMap1.8和1.7的区别

1. 数据结构。1.7用数组+链表的方式；1.8中用数组+链表+红黑树的方式。使用红黑树主要是针对当链表过长时效率差的问题，当链表长度达到8时（包含头节点），会转为树结构；当链表长度减少到6时，树会退化为链表。
2. 链表插入方式。1.7中链表插入是用头插法，也就是说新插入的元素在链表头部（有种说法是因为新插入的元素被访问的概率更大，所以用的头插法）；1.8中改为了用尾插法。

   HashMap1.7中死循环的问题

   HashMap1.7中，扩容的时候也是头插的方式的，然后在多线程操作的时候，可能出现链表元素形成环的情况，例如a->b，b->a。这样当后面调用get()方法的时候，就会在环里打转，形成死循环。
   在1.8中将头插法改成了尾插法了，能避免这种情况的发生。

   HashMap容量和负载因子

   HashMap会强制容量为2，这么做的目的有两个：1 在计算元素数组下标位置的时候，用与运算替代了取模运行；2 在扩容的时候，只需要看特殊位就可以确定扩容后的位置。

• 原来计算元素位置，是通过 hash%cap，而如果cap是2的话，那么有hash%cap=hash&(cap-1)，而与运算性能好于取模运算。
• 扩容的话，原来的方式是需要对元素重新计算扩容后的位置hash%(newCap-1)，但其实不用这么麻烦，我们假设原来的容量是8，扩容后是16（HashMap扩容是原来的两倍），那么原来的位置是：hash%0111，那扩容后的位置hash%1111，可以发现只需要看第4位是1还是0，如果是0位置不变，如果是1，移动到 当前位置+原来的容量 的位置。

讲完了容量为什么是2，再聊下负载因子，负载因子HashMap默认0.75，这是一个空间和时间的折中选择。

HashMap的put()方法过程

1. 进行位扰动计算，位扰动计算是将key.hashCode()的前16位和后16位进行异或运算，这样只要有一位不同结果就不同，尽可能减少hash冲突；
2. 如果数组未初始化，对数组进行初始化；初始化了之后计算元素在数组中的位置hash&(cap-1)；
3. 如果该位置没有元素，直接插入；如果该位置有元素，调用equals()方法比较，如果相等，更新value；
4. 看数组该位置元素后面是链表还是红黑树，如果是树，在树中进行更新value或插入元素的操作；如果是链表，遍历链表调用equals()方法，相等就更新value，如果直到链表尾部都不相等，就尾插元素，如果此时链表长度达到8，转为树结构；

5. 上述步骤就完成了插入元素或更新value，如果是插入元素还会让size++、modcount++，size达到阈值还需要进行扩容，最后put()方法中还有两个钩子方法让子类实现，LinkedHashMap中就实现了这两个钩子方法来实现访问顺序访问和LRU算法。

   哈希冲突有哪些解决方式

   链地址法、开放寻址法（冲突了就在数组上遍历过去找到空的地方插入）、多次hash法（有一组hash函数，冲突了就调用下一个函数）。

   LinkedHashMap

   LinkedHashMap是HashMap的子类，其数据结构在数组+链表+红黑树的基础上，还有一个双向链表，保存了顺序，有两种：插入顺序访问和访问顺序访问。
   插入顺序访问实现原理就是，在put()的时候，如果插入了一个新的元素，那么就把它放到双向链表的尾部，其重写的newNode()方法中，会把新创建的Node放在双向链表的尾部。
   访问顺序访问实现原理就是，在插入、更新、查询的时候，把元素放到双向链表的尾部。
   在访问顺序访问的基础上，我们可以实现LRU算法，就重写removeEldestEntry()，在达到一定数量的时候，移除最老的元素。

   TreeMap

   TreeMap是按照元素大小进行排序的，一致性hash算法就通过TreeMap来实现的。

   HashTable

   HashTable可以简单的认为是个线程安全的HashMap，其线程安全的实现就是在方法上加synchronized锁。

   ConcurrentHashMap

   ConcurrentHashMap1.7和1.8实现的区别

   ConcurrentHashMap最大的特点就是实现了分段锁，每段管理一部分数据，这样并发下读写性能更好。而其在1.7和1.8中的实现有很大的区别。
   1.7中数组中存储的是Segment，Segment是ReentrantLock的子类，我们可以简单的认为他就是一个锁，而在Segment中有数组+链表的数据结构，数据存在这个Segment里面。所以1.7中分段锁的实现是：数组中存储了多个锁，然后每个锁管理一部分数据。
   1.8中抛弃了Segment，其数据结构和1.8的HashMap差不多，唯一不同的是，用synchronized锁锁住数组中的元素，这样元素后面的链表/红黑树就只能一个线程访问了。总结来说，1.8中分段锁的实现是：一个HashMap的数据结构，在写数据的时候，通过锁住数组中元素，实现分段。

   ConcurrentHashMap的get()方法为什么不需要加锁

   node和value都用volatile修饰，保证了可见性。

   ConcurrentHashMap的size()方法实现

   1.7中求size()是通过计算两次，如果相同就返回，如果不同，那锁住整个ConcurrentHashMap来遍历实现的。
   1.8中ConcurrentHashMap中有一个volatile修饰的变量和数组，在每次变更map中元素的时候都会记录，通过计算变量和数组就可以实现。

   如何提高ConcurrentHashMap的插入效率

6. 减少扩容。合理设置（设置的大点）数组容量和负载因子。

7. 尽量避免synchronized锁升级。我们可以把多线程put()的操作，放到一个队列中，然后让一个单独的线程去处理，完成put()，这样能避免多线程竞争锁资源，造成锁膨胀的情况。
8. 如果我们能够把插入的数据进行分类，把同一个锁下面的插入数据交给同一个线程去插入，这样就能避免锁竞争了。这里同一个锁下面的数据可以简单的认为是在数组中索引位置相同的元素，我们可以通过hash&(cap-1)这种来计算。

   Set

   Set最大的特点就是元素不重复，其重要的实现类有HashSet、LinkedHashSet、TreeSet，底层都是通过对应的Map实现的。
   而Set是怎么保证元素不重复的呢？主要就是用的Map，key是插入的元素，value是Object对象，当插入重复的元素时，key其实是不变的。