【一些面经】Java集合

【一些面经】Java集合 1.ArrayList

存储的元素是有序的，可重复，线程不安全。

底层使用Object数组存储数据，适用于频繁的查找工作。

支持高效的随机元素访问（快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法))。

插入/删除时间受元素位置影响。

比如：

• add(e) 默认插入到数组末尾
• add(index, e) 需要将index及index后的元素往后移一位
• remove(e) 底层循环通过元素的equals方法判断元素是否相同，将移除元素后面的元素往前移一位
• remove(index) 移除索引位上的元素，并将后面的元素往前移一位

空间浪费体现在 list 列表的结尾会预留一定的容量空间。

2. ArrayList扩容

无参方法构建ArrayList时，实际上初始化的是一个空数组，当进行元素添加 *** 作时，才真正分配容量，扩容长度为10（JDK6 无参初始化时，直接创建了长度为10 的数组）。

扩容长度一般为当前长度的1.5倍。

3.linkedList

存储的元素是有序的，可重复，线程不安全。

底层使用双向链表（JDK1.6之前使用的双向循环链表， JDK1.7取消循环）。

不支持高效的随机元素访问。

插入/删除受元素位置影响（区别于ArrayList）：

• add(e)/addFirst(e)/addLast(e)/removeFirst(e)/removeLast(e) 时间复杂度类似于ArrayList的add(e)
• add(index, e) 需要将元素先移动至指定位置再进行插入，当数组长度很长的时候，index越靠近数据长度中部，插入速度越慢
• remove() -> removeFirst() 无参方法会直接删除链表的头结点
• remove(e) -> 遍历链表，如果传入null，当节点为null时删除节点，传入对象时 通过对象的equals方法判断判断是否相同，相同则删除节点
• remove(index) -> 通过checkElementIndex(index) 判断节点是否存在 如果存在则删除节点

空间浪费体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继(next)和直接前驱(prev)以及数据(data)）。

4.Vector

存储的元素是有序的，可重复，线程安全。

底层使用Object数组存储数据。

5.List各个集合的区别

底层实现

数据是否可重复

是否线程安全

数据是否有序

ArrayList

Object数组

可重复

否

有序

linkedList

双向链表（JDK1.6前为循环双向链表）

可重复

否

有序

Vector

Object数组

可重复

是

有序

6.HashSet

存储的元素是无序的，不可重复，不是线程安全的。

基于HashMap实现，底层数据结构是哈希表（基于 HashMap 实现）。

用于不需要保证元素插入和取出顺序的场景。

7.linkedHashSet

存储的元素是有序的，不可重复，不是线程安全的。

基于linkedHashMap实现，底层数据结构采用链表+哈希表（基于linkedHashMap实现）。

用于保证元素的插入和取出顺序。

8.TreeSet

存储的元素是有序的，不可重复，不是线程安全的。

底层数据结构采用红黑树。

用于支持对元素自定义排序规则的场景。

9.SET各个集合的区别

底层实现

数据是否可重复

是否线程安全

数据是否有序

HashSet

基于HashMap

不可重复

否

无序

linkedHashSet

基于linkedHashMap

不可重复

否

有序

TreeSet

红黑树

不可重复

否

有序

10.HashMap

HashMap是无序的，用于存储数据，key不可重复（key可为NULL，但是只能存在一个），value可以重复（可以为NULL，多个），线程不安全。

底层采用数组+链表+红黑树

1. 为什么使用链表：
   链表主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。
2. 为什么使用红黑树：
   同一hash值的数据都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。所以将链表转换为红黑树，这样大大减少了查找时间
3. 链表多久转换为红黑树：
   链表在达到阈值（默认为8），将链表转化为红黑树，以减少搜索时间（链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）
4. 红黑树多久转换为链表：
   红黑树元素小于6时会转换为链表
5. hash值计算：
   HashMap通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值 ，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度）
6. HashMap初始化/扩容：
   HashMap默认初始化大小为16，每次扩容会将其扩充为 2 的幂次方大小
7. 为什么不用B+树来替换红黑树：
   树看重两个性能 插入和查找。插入时有可能要调整树的结构 重新平衡树，B+树 调整树的结构慢一些，所以B+树插入慢，查找快；红黑树插入快 ，查找慢。

11.HashMap遍历方式及性能分析

遍历方式：

• 迭代器（Iterator）方式遍历
• For Each 方式遍历
• Lambda 表达式遍历（JDK 1.8+）
• Streams API 遍历（JDK 1.8+）

entrySet > Streams > keySet > lambda

entrySet 的性能比 keySet 的性能高出了一倍之多，因为 KeySet 相当于循环了两遍 Map 集合，而 EntrySet 只循环了一遍。

12. linkedHashMap

linkedHashMap是有序的，用于存储数据，key不可重复（key可为NULL，但是只能存在一个），value可以重复（可以为NULL，多个），线程不安全。

底层在HashMap的基础上加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。

13.HashTable

HashTable是无序的，用于存储数据，key不可重复（key不为NULL），value可以重复（value不为NULL），线程安全（内部方法基本上经过synchronized修饰），Hashtable 基本被淘汰，不要在代码中使用它。

HashTable底层使用数组+链表结构存储数据

Hashtable默认初始化大小为11，如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小

HashTable锁原理：

Hashtable使用同一把锁 :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

14.ConcurrentHashMap

ConcurrentHashMap是无序的，用于存储数据，key不可重复（key可为NULL，但是只能存在一个），value可以重复（可以为NULL，多个），线程安全。

底层数据结构：

• JDK1.7以前：
          数据结构采用分段的数组（segment）+链表
• JDK1.8:
          数据结构采用Node数组+链表+红黑树，Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode

锁机制：

• JDK1.7以前：
          锁机制采用的分段锁
          分段锁：对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
• JDK1.8:
          锁机制采用synchronized 和 CAS
          只锁定当前链表或红黑树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。

 15.MAP各个集合的区别

底层实现

key是否可重复

key是否可以为NULL

value是否可重复

value是否可以为NULL

是否线程安全

数据是否有序

HashMap

数组+链表+红黑树

不可重复

可以，只能存在一个

可重复

可以存在多个NULL

否

无序

linkedHashMap

数组+链表+红黑树+双向链表

不可重复

可以，只能存在一个

可重复

可以存在多个NULL

否

有序

HashTable

数组+链表

不可重复

不可以

可重复

不可为NULL

是

无序

ConcurrentHashMap

数组+链表+红黑树

不可重复

可以，只能存在一个

可重复

可以存在多个NULL

是

无序