（3）集合类

**1 Java中常用的集合类有哪些？
Java面试题（3）-集合

2 ArrayList和LinkedList的部实现是怎样的，他们之间的区别和优缺点？

ArrayList:内部是数组实现的,是利用数组的下标进行元素的访问,所以访问速度特别快.因为是数组,所以ArrayList初始化大小是10.插入新元素的时候,会判断是否需要扩容,扩容的大小是原始大小的0.5倍,扩容的方式是数组的复制,所以有一定的消耗。

LinkedList:内部是双向链表实现的,LinkedList有一个内部类作为存放元素的单元,里面有三个属性,用来存放元素本身和前后两个单元的引用.LinkedList还有一个Header属性,第一个元素和最后一个元素都指向Header。

ArrayList和LinkedList的缺点如下:
对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。
在ArrayList集合中添加或者删除一个元素时，当前的列表移动元素后面所有的元素都会被移动。而LinkedList集合中添加或者删除一个元素的开销是固定的。
LinkedList集合不支持高效的随机随机访问（RandomAccess），因为可能产生二次项的行为。
ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。

ArrayList和LinkedList的场景如下:
ArrayList使用在查询比较多，但是插入和删除比较少的情况，而LinkedList用在查询比较少而插入删除比较多的情况

3 说说HashMap实现原理？

HashMap 的底层数据结构实际上是一个 entry 数组，当往 map 里面 put 一个数据的时候，会根据 key 的 hash 值计算下标，如果没有发生碰撞，就会直接放进数组里。如果碰撞了，就以链表的方式链接到链表上，在 jdk1.7 是使用的头插法在多线程的情况会导致 map 扩容的时候让链表成环，如果这个时候刚好有 get 操作到了此链表上,就会发生死循环，1.8 的时候就改用尾插法了。

当链表的长度超过阈值 6 的时候，就会把链表转换成红黑树，以此提高查找数据的性能。如果链表里面存着相同的 key，则会替换旧值。当 map 里面的数据超过容量的百分之七十五，就会调用 resize 、rehash 方法,将 map 扩容两倍之后重排。这里的 resize 方法会对整个 map 的元素进行遍历，极其耗费性能。因此我们在实际开发过程中，当我们明确知道 map 要用的容量的时候，尽量使用指定初始化容量的构造函数，避免频率的扩容重排带来的性能损耗。

当我们在 map 里面 get 一个数据的时候，会根据 key 的 hash 值计算下标，在这里 jdk 对 hashmap 的寻址算法做了一个优化，就是规定数组的长度必须是 2 的幂次方。当数组的长度是 2 的幂次方的时候， (n-1)&hash 数组的长度减一跟 hash 值作与运算，就跟直接用数组长度跟 hash 值取模是一样的，这里就用了与运算代替取模，提升性能。但是这里也会带来一个问题， HashMap 的容量可以达到 2 的三十二次方，但是在业务系统实际开发过程中，我们可能并不会在内存中存放大量的数据，那么这时候我们用数组的长度减一跟 hash 值作与运算的时候，因为高位都是 0 ，这样就相当于高位的差异都丢失了。所以这里 jdk 又对 hash 算法作了一个优化，将 key 原始的 hash 值的高十六位与第十六位作一个异或运算。因为异或运算里，相等的等于1，不相等的等于0，做异或运算就相当于将高位跟低位的特征都集中在了低位，这样当我们往 HashMap 里面put数据的时候就能降低 hash 碰撞的几率，以此提高 HashMap 的性能

总结一下，HashMap 是线程不安全，如果需要同步请使用guava的类库或者是 ConcurrentHashMap ，并且 resize 方法极其耗费性能。因此我们在实际开发过程中，当我们明确知道 map 要用的容量的时候，尽量使用指定初始化容量的构造函数，避免频率的扩容重排带来的性能损耗。

4 说说HashMap、Hashtable、TreeMap的区别

1、实现

HashMap是继承自AbstractMap类，而HashTable是继承自Dictionary类。它们都同时实现了map、Cloneable（可复制）、Serializable（可序列化）这三个接口。存储的内容是基于key-value的键值对映射，不能有重复的key，而且一个key只能映射一个value。HashSet底层就是基于HashMap实现的。

2、为空

Hashtable的key、value都不能为null；HashMap的key、value可以为null，不过只能有一个key为null，但可以有多个null的value；TreeMap键、值都不能为null。

3、排序

Hashtable、HashMap具有无序特性。TreeMap是利用红黑树实现的（树中的每个节点的值都会大于或等于它的左子树中的所有节点的值，并且小于或等于它的右子树中的所有节点的值），实现了SortMap接口，能够对保存的记录根据键进行排序。所以一般需求排序的情况下首选TreeMap，默认按键的升序排序（深度优先搜索），也可以自定义实现Comparator接口实现排序方式。

5 说说Vertor、ArrayList、LinkedList的区别

Vector
是Java早期提供的线程安全的动态数组。内部使用对象数组来保存数据，可以自动增加容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。
ArrayList
由动态数组实现，其本身不是线程安全的，所以性能较高。也可自动扩容。与Vector的区别是 Vector 是增加 1 倍，而ArrayList是增加50%。扩容是调用底层 System.arraycopy()方法进行大量的数组复制操作；在删除元素时并不会减少数组的容量（如果需要缩小数组容量，可以调用trimToSize()方法）；在查找元素时要遍历数组，对于非null的元素采取equals的方式寻找。
LinkedList
由双向链表实现，非线程安全的。LinkedList在插入元素时，须创建一个新的Entry对象，并更新相应元素的前后元素的引用；在查找元素时，需遍历链表；在删除元素时，要遍历链表，找到要删除的元素，然后从链表上将此元素删除即可。

Vector和ArrayList作为动态数组，其内部元素有数组形式顺序存储，非常适合需要随机访问的场合。除了尾部的插入或删除操作，其性能会相对较差，如在中间任意插入元素都需移动后续所有元素。LikedList 进行节点的插入或删除操作效率更高，但随即访问性能较低。

6 HashSet和HashMap区别

HashSet实现了Set接口，它不允许集合中出现重复元素。当我们提到HashSet时，第一件事就是在将对象存储在HashSet之前，要确保重写hashCode（）方法和equals（）方法，这样才能比较对象的值是否相等，确保集合中没有储存相同的对象。如果不重写上述两个方法，那么将使用下面方法默认实现：

public boolean add(Object obj)
方法用在Set添加元素时，如果元素值重复时返回 "false"，如果添加成功则返回"true"

HashMap实现了Map接口，Map接口对键值对进行映射。Map中不允许出现重复的键（Key）。Map接口有两个基本的实现TreeMap和HashMap。TreeMap保存了对象的排列次序，而HashMap不能。HashMap可以有空的键值对（Key（null）-Value（null））。HashMap是非线程安全的（非Synchronize），要想实现线程安全，那么需要调用collections类的静态方法synchronizeMap（）实现。

public Object put(Object Key,Object value)方法用来将元素添加到map中。

**7 ConcurrentHashMap如何保证线程安全？

HashMap是用于存储存在映射关系的键值对的集合，但是HashMap是线程不安全的，在并发环境下会出现脏读脏写的问题。HashTable这个集合解决了HashMap的线程安全问题，但是它的解决方法是简单粗暴的，直接在每个get/put方法上用synchronized进行修饰，这样操作的效率是低下的，每当有一个线程正在使用HashTable时，就会把整个散列表都锁住，其它线程若想操作HashTable则都会被阻塞。因此现在基本上都不推荐使用HashTable来解决HashMap的线程安全问题。

JDK1.7下ConcurrentHashMap的解决思想将散列表分别多个段，进而使用分段锁，来降低锁的粒度（锁粒度越小事务的并行度越高）。可以参考下图：

ConcurrentHashMap内部维护一个Segment(段)数组，该Segment数组中的每一个元素是一个HashEntry数组，而HashEntry的结构与HashMap基本一致。

Segment继承了Reentrantlock（关于Reentrantlock，在我的Java并发专栏中的文章已提到了，有兴趣可以看看），意味着每个Segment对象就是一把锁，而每个Segment对象内部都存储着一个HashEntry数组，也就是说该HashEntry数组中的数据同步依赖于该Segment对象这一把锁，这就形成了分段锁。

设ConcurrentHashMap中的Segment数组的长度为n，相较于HashTable，也就是说ConcurrentHashMap将散列表分成了n段，那么性能就提升了n倍。但实际上，ConcurrentHashMap本身还对锁进行了优化，使得性能达到了n倍以上。是怎么优化的呢？

设现在线程A正在修改一个HashEntry数组中的数据，此时线程B也想尝试在HashEntry数组中进行put操作，但是这时候线程A已经独占了这个锁，所以线程B只能等待或者重试，但与其让线程B干等或不断重试，ConcurrentHashMap改为让线程B在重试的过程当中提前依据put操作中的key和value去完成HashEntry键值对节点的创建。

其实这里存在一个问题，如果线程B在获取到锁时发现锁被占用，它在等待过程中先进行了HashEntry键值对节点的初始化之后，获取到了锁，此时发现了在原本的散列表中已经存在了当前key的键值对节点，那我们这个新创建的HashEntry键值节点对不就浪费了吗？其实这是一种 “预创建” 的思想，与其让线程在原地干等，还不如让它先去把可能需要用到的工作（在这里指创建一个HashEntry键值对节点）做了，以防在后面发现了不存在当前key的键值对时可以直接使用该新建的HashEntry键值对节点。

在JDK1.7中ConcurrentHashMap的扩容方面，Segment数组一旦初始化后就不会再进行扩容，而HashEntry是可以进行扩容的，扩容原理与HashMap一致，且该扩容操作是在put方法中发生的，而put操作已经被使用锁保证了线程安全，所以也保证了扩容的线程安全。

对JDK1.7中ConcurrentHashMap的总结：

使用分段锁，Segment继承于Reentrantlock，将每个Segment对象作为锁，每个Segment对象中有一个HashEntry数组
Segment数组经初始化后不再扩容，HashEntry数组可扩容
使用预创建的思想，当线程要进行put操作而获取锁时发现锁被占用，会先进行对节点的创建，以避免线程处于空闲状态
扩容是在HashEntry中的put方法中进行，而当前HashEntry已经使用了Segment对象作为锁来确保线程安全，进而确保了扩容的线程安全。

HashMap在JDK1.8版本中引入了红黑树的结构，在JDK1.8版本的ConcurrentHashMap中也引入了红黑树的结构。

当冲突链表个数增大到 8 个时，就会将链表转化为红黑树结构，以提高查询效率。当红黑树节点个数小于 6 个时，就会将红黑树转化回链表的结构。

在结构上，JDK1.8中的ConcurrentHashMap由JDK1.7中的Segment数组 + HashEntry数组 + 链表进化为 Node数组 + 链表 / 红黑树的结构。其中Node数组中的每一个Node对象也即存储了键值对的信息。

在解决线程安全方面，简单来说，相较于JDK1.7，JDK1.8不再使用分段加锁的操作，而是直接在散列表的每一个头节点上进行加锁，进一步缩小了锁的粒度。同时在JDK1.7中是使用继承了Reentrantlock的Segment对象作为锁来进行加锁操作，而JDK1.8中是直接在节点上使用CAS或者Synchronized关键字修饰来进行并发控制。

ConcurrentHashMap中有一个比较关键的属性sizeCtl，这个属性的不同值代表ConcurrentHashMap目前处于不同的状态：

-1 说明正在初始化
-N 说明有N-1个线程正在进行扩容
表示 table 初始化大小，如果 table 没有初始化
表示 table 容量，如果 table 已经初始化。
在ConcurrentHashMap初始化操作中，使用CAS进行初始化，以防同时与其它线程对当前ConcurrentHashMap进行了初始化。

ConcurrentHashMap中键值对的key和value不能为null，因为如果key和value可以为null，会出现二义性问题。当通过一个key获取到的value为null时，我们没法知道是不存在这个键值对还是存在value为null的键值对，这就产生了二义性问题。在HashMap中，当获取到的value为null，我们可以通过containsKey方法来判断是否存在这个键值对。但是在ConcurrentHashMap中，当获取到的value为null，我们再去调用containsKey方法，但这个过程没法确保是否刚好有别的线程把查询的对象加入到集合中或者把它删除掉，所以为了避免二义性问题，ConcurrentHashMap不允许key和value为null。

在put操作中的流程：

判断key和value是否为null，如果是则报错。
判断当前ConcurrentHashMap是否需要进行初始化，如果当前ConcurrentHashMap为空，则使用CAS进行初始化
依据当前key定位出Node的位置，如果当前位置为空，则使用CAS在当前位置尝试加入Node，失败则进行自旋保证成功
如果当前位置不为空，判断当前位置是否有其它线程正在进行扩容，如果有则当前线程进入协助扩容阶段
如果当前位置不为空且无其它线程在进行扩容，则使用synchronized关键字对当前位置的头节点加锁后，进行数据修改
如果当前位置的节点是链表结构，则遍历链表找是否有key相同的元素，有则修改value，无则在最后插入新链表节点，然后判断当前链表中的节点个数是否超过了树化阈值（这个阈值是TREEIFY_THRESHOLD，是相对链表节点个数而言，值为8），如果超过，则考虑将链表转化为红黑树
如果当前链表中的节点个数超过了树化阈值，会调动treeifyBin方法，然后看当前散列表数组的大小是否小于最小树化阈值（这个阈值是MIN_TREEIFY_CAPACITY，是相对散列表个数而言，值为64），如果小于它，则不进行改造为红黑树，而是将散列表数组容量扩大为两倍，然后重新调节节点位置
如果当前位置的节点是红黑树结构，则按照红黑树的插入规则进行新节点的插入
新节点插入之后节点数量 + 1，判断ConcurrentHashMap是否需要进行扩容
在get操作中的流程：

根据 hash 值计算位置。
查找到指定位置，如果头节点就是要找的，直接返回它的 value.
如果头节点 hash 值小于 0 ，说明此处正在扩容或者此处是红黑树，查找之。
如果是链表，遍历查找之。
什么时候会发生扩容？

新增节点后链表节点数达到了8个但是散列表数组长度小于64，这时不会选择将链表转化为红黑树而是将散列表数组大小变为2倍，调用tryPresize方法。
新增节点后当前数组中的总元素个数达到了扩容阈值，则进行扩容，调用transfer方法。
当调用了putAll方法时，发现当前容量不足以存放所有的元素，则进行扩容。
JDK1.8中ConcurrentHashMap扩容机制比较复杂，内容较多，大家可以参考这篇文章《ConcurrentHashMap1.8 - 扩容详解》，里面有图解扩容。

对JDK1.8中ConcurrentHashMap的总结：
引入了红黑树的数据结构，且不再使用分段锁，改用Node数组
直接在散列表的每个头节点上使用CAS进行创建头节点或者使用synchronized关键字加锁
扩容时可能会有多个线程参与扩容
key和value不能为null，目的是在于避免二义性问题

8 Collection和Collections的区别

Collection，提供了对集合对象进行基本操作的通用接口方法，所有集合都是它的子类，比如List、Set等。Collections，是一个工具类，它包含了很多静态方法，不能被实例化，比如排序方法：Collections.sort(list)等。

参考
https://blog.csdn.net/QQ1149646297/article/details/123613822open in new window
https://zhuanlan.zhihu.com/p/313708329open in new window
https://zhuanlan.zhihu.com/p/267545042open in new window
https://blog.csdn.net/gejiangbo222/article/details/81540616open in new window
https://juejin.cn/post/7130059718248103967open in new window