集合问题

转自小端有话说，侵改；

1.问：List 和 Set 都有什么区别？

分析：这种问题面试官一般想考察的都是你对这两种数据结构的了解，以及使用时候的选择依据，可以从数据结构和一些使用案例入手分别做个介绍，可深可浅，就看自己了解的程度了。
答：List，列表，元素可重复。常用的实现ArrayList和LinkedList，前者是数组方式来实现，后者是通过链表来实现，在使用选择的时候，一般考虑的是基本数据结构的特性，比如，数组读取效率较高，链表插入时效率较高。
Set，集合，特点就是存储的元素不可重复。常用是实现，是HashSet和TreeSet，分开来谈：

• HashSet，底层实现是HashMap，存储时，把值存在key，而value统一存储一个object对象。排重的时候，是先通过对象的hashcode来判断，如果不相等，直接存储。如果相等，会再对key做equals判断，如果依然相等，不存储，如果不相等，则存入，我们知道，HashMap是数组+链表的基本结构，同样的，在HashSet中，也是通过同样的策略，存储在相同的数组位置下的链表中。

• TreeSet，存入自定义对象时，对象需要实现Comparable接口，重写排序规则。使用场景一般是需要保证存储数据的有序和唯一性。底层数据结构是自平衡的二叉排序树（红黑树）

延伸：

• a.在说到HashMap时，可能会直接引到HashMap相关话题，我发现这个问题面试官非常喜欢问，可能是因为HashMap可聊的较多，也能很好的考验下应聘者对底层实现细节、源码阅读、刨根问底的态度。

• b.涉及到二叉树了，小端就遇到过一次问红黑树特性的，因为之前准备过，胸有成竹的啪啪啪正要一一道来呢，结果刚说到第二个特性，面试官就问：红黑树和普通的平衡二叉树有什么区别？当时一脸懵逼样...回来后赶紧补足，核心区别就是：红黑树也是二叉查找树的一种，二叉树需要通过自旋、或其他方式（比如红黑树还能通过变色）来保证平衡（否则就成了链表结构了，没有时间复杂度上的优势了），红黑树限定的条件相对来说比较宽松，也就是说在平衡的过程中，消耗相对较小。

• c.由于HashSet无序，为了实现有序的目的，又不想用其他数据结构，可以用LinkedHashSet。简要说明，同HashSet和HashMap关系一样，也是使用了一个LinkedHashMap，LinkedHashMap和普通的HashMap的区别就是，在原有数据结构之上，采用双向链表的形式将所有entry（注意，是前面讲过的数组+链表中的各个链表里的元素，做了连接）连起来，顺序就是entry的插入顺序，这样可以保证元素的迭代顺序和插入顺序相同（有序性），如下图：

image

（请注意框住部分，绿色和橙色的箭头的走向，就是这个双向链表）

2.HashMap 是线程安全的吗，为什么不是线程安全的?

分析：这种问题，既然面试官问起，肯定是在这方面有的聊的。这个问题，在多数情况下，能清晰、全面的描述出问题来龙去脉即可，很少有面试官真的拿一段源码来考。当然，作为应聘者，如果能理解的很透彻，再用简单的图边写边讲，作为补充，还是非常出彩的。

答：嗯，不是线程安全的。主要从两个方面来说：

• a.在插入新数据的时候，多线程hash后的结果相同，插入位置也就会定位到数组的相同下标下的同一个链表中。在插入时，假如第二个线程在第一个线程插入的瞬间也插入，就可能会导致，覆盖前面插入的值。
• b.第二个非线程安全的影响是在扩容的时候，扩容会把所有值重新hash，插入到新的扩容后的“数组+链表”结构中。可能会导致环状链表情况出现，这样在读取节点的next节点时，永不为空，也就是著名的扩容时CPU使用率100%情况。

延伸：
要做到心中有底，还是需要知其然知其所以然才行，所以，撸下源码好好想想，才能做到临阵不乱。

• a.建议好好看看源码，源码量不大，结构也比较清晰。
• b.针对环状链表的情况，我是看了别人写的图文并茂版的文章弄明白的，这里放上链接，供参考：HashMap高并发问题

3.问：那你是用什么数据结构来作为替代，满足线程安全的场景要求呢？

分析：这里一般面试官想考察的是对ConcurrentHashMap的了解，但是也有个别情况，会涉及到HashTable，小端就吃过这方面的亏，明明可以一笔带过的小知识点，却由于准备不充分，而没能答完整。
答：在Java里，提供了以下数据结构，可以解决线程安全问题：

• a.HashTable，实现原理是通过Synchronize同步锁来把读写方法都加锁的方式。虽然线程安全了，但是效率低下，只要有读写，就不能做其他操作。
• b.SynchronizedMap（涉及较少，了解即可），有条件的同步，是Collections类提供的一个方法返回的HashMap的多线程版本。实现是把基本的方法都加了同步锁。
• c.ConcurrentHashMap（重头戏）：根据jdk版本不同，实现也有差别。
  java8以前，是用segment（锁住map一段实现，默认是16段也就是可以并发数支持到16，也可自定义。读不受影响），数据结构为数组(segment)+数组(entry)+链表，适用于读多写少的场景。提供原子操作putIfAbsent()（没有则添加）。segment继承自ReentrantLock，来作为锁。
  java8，元素结构为Node（实现Entry接口），数据结构为数组+链表；直接对Node进行加锁，粒度更小。当链表长度大于8，转换为红黑树,当然在转换前，先看下数组长度，如果小于64，那先通过扩容来实现；插入元素时，如果该位置为null，用CAS插入；如果不为null，则加Synchronize锁插入到链表；

扩展：

• a.我们看到，数组的默认长度都是16，那么这个数字有什么深意吗？有！做运算时效率高！属于取巧的设计。一个是扩容的时候，直接向左位操作，移一位，扩张为二倍；二是hash取模的时候，hash值是32位，右移28位，剩高四位，然后与这个length-1也就是15（1111）按位与操作，使数据均匀分布。
• b.ConcurrentHashMap在获取size时候是怎么计算的呢？
  1.7size(),先获取segment的大小，然后判断是否修改过，如果是，在加锁重新获取segment大小，然后把所有segment大小加在一起；
  1.8size()的实现是用一个volatile 变量来做CAS修改，如果高并发，还会把部分值存到一个volatile数组。取值时，把这两部分的值加在一起。mappingcount()方法和size()方法实现方式一样
• c.hashmap可以使用null作为key和value，存储于table数组第一个节点；hashtable不允许key和value为null.（这个在一个小公司被面试官问倒了，汗颜）
• d.了解一些其他的数据结构：
  ConcurrentSkipListMap 数据有序
  ConcurrentSkipListSet 能去重
• e.hashset是用hashmap实现，内部存的是key，所有的value都是同一个object