Java集合框架知识点整理

1.2 集合框架

1.2.1 Java中常见的集合类有哪些

Map接口和Collection接口是所有集合框架的父接口：

Collection接口的子接口包括：Set接口和List接口
- Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet等
- List接口的实现类主要有：ArrayList、LinkedList、Stack以及Vector等
Map接口的实现类主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap以及 Properties等

1.2.2 说一说对ArrayList的理解

底层数据结构：ArrayList底层是基于数组实现的。Java中的数组需要在创建数组时便确定数组的容量，因为数组本身不会自动扩容，对于元素数量不确定的场景如果使用数组则需要预估所需的数组容量，如果估少了还需要重新申请空间并对原数组进行拷贝，这些拷贝数组的场景在开发中非常常见，所以 ArrayList 对这部分重复编码的逻辑进行了封装，实现了动态扩容的效果。
线程安全：ArrayList不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的List类，也可以使用concurrent并发包下的CopyOnWriteArrayList类
扩容机制：List list = new ArrayList<>()如果没有指定参数那么，初始长度为10，如果指定了构造方法参数，那么参数即为初始长度，之后向集合中添加元素，如果空间不足则扩容，默认情况下扩容为原来的容量的1.5倍，同时需要将原有数组中的数据复制到新的数组中
扩容新容量计算方式：int newCapacity = oldCapacity + (oldCapacity >> 1)，相当于1.5倍
1.7和1.8区别：JDK1.7的时候创建ArrayList对象直接初始化数组，JDK1.8的时候采用懒加载，第一次add元素的时候初始化数组
建议开发中使用带参的构造器：ArrayList list = new ArrayList(int capacity)，预估数组长度

1.2.3 说一说对LinkedList的理解

底层数据结构：LinkedList是通过双向链表去实现的。每个节点会保存前一个元素的指针和后一个元素的指针
- 因为链表通过前后指针进行关联，所以内存地址可以是非连续的，而且在内存充足的情况下可以无限延展
- 同时LinkedList实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用
线程安全：LinkedList不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的List类，也可以使用concurrent并发包下的ConcurrentLinkedQueue类
扩容机制：链表不需要扩容

1.2.4 说一说ArrayList和LinkedList的区别

数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。
随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。 ArrayList可以根据数组索引直接获取
增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响数组内的其他数据的下标。
内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。
线程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；

1.2.5 数组和List之间如何相互转化

数组转List：

//数组转List
String[] strs = new String[]{"aaa","bbb"};
//方式一 : asList 这种操作返回的List不支持增删改操作
List<String> list1 = Arrays.asList(strs);
//方式二 : 将数组元素转化为List , 添加到一个新的List集合 , 可以支持增删改操作
List<String> list2 = new ArrayList<>(Arrays.asList(strs));
//方式三 : Collections.addAll()方法
List<String> list3 = new ArrayList<>(strs.length);
Collections.addAll(list3,strs);
//方式四 : stream流将数组元素采集为List
List<String> list4 = Arrays.stream(strs).collect(Collectors.toList());

List转数组：

//方式一 : 使用 list.toArray 方法
List<String> list = new ArrayList<>();
String[] strs1 = list.toArray(new String[2]);
//方式二 : for循环遍历List集合 ,存入数组
String[] strs2 = new String[list.size()];
for (int i = 0; i < list.size(); i++) {
    strs2[i] = list.get(i);
}

1.2.6 说一说HashMap的实现原理

HashMap的数据结构：底层使用hash表数据结构，即数组和链表的结合体，JDK1.8起引入了红黑树，数据结构就变成了数组 + 链表 + 红黑树的形式
HashMap JDK1.8之前：采用的是拉链法。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
HashMap JDK1.8之后：相比于JDK1.7，JDK1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。扩容 resize() 时，红黑树拆分成的树的结点数小于等于临界值6个，则退化成链表。
HashMap 基于 Hash 算法实现的：当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
- 存储时，如果出现hash值相同的key，此时有两种情况。
  - 如果key相同，则覆盖原始值；
  - 如果key不同（出现冲突），则将当前的key-value放入链表中
- 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值

1.2.7 说一说HashMap扩容机制

扩容就是HashMap底层的resize()方法，在两种情况下会执行：

初始化HashMap集合，第一次往里面存元素的时候会执行resize()方法，初始化底层的数组（默认容量是16），如果构造方法中传入了初始容量参数，那么初始长度为大于传入初始容量的第一个2的n次幂
当HashMap集合中存入的键值对数量超过阈值（0.75）的时候会进行扩容，每次扩容容量为之前的2倍

在1.7 中，扩容之后需要重新去计算其Hash值，根据Hash值对节点位置进行重新分配

在1.8版本中，则是根据在同一个桶的位置中进行判断（e.hash & oldCap）是否为0，如果为0 则留在当前位置不动，如果不为0 则要移动到原始位置+增加的数组大小这个位置上，这也是为什么HashMap扩容容量为2的N次幂的一个原因

思考：

为什么HashMap的数组长度一定是2的次幂？
- 计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算代替取模运算，效率更高
- 扩容时重新计算索引效率更高： hash & oldCap == 0 的元素留在原来位置，否则新位置 = 旧位置 + oldCap
为什么扩容阈值设置为0.75？
- 选择扩容阈值为0.75的原因是为了在空间占用与查询时间之间取得较好的权衡
- 大于这个值，空间节省了，但链表就会比较长影响性能
- 小于这个值，冲突减少了，但扩容就会更频繁，空间占用多

1.2.8 说一说HashMap的put方法的具体流程

判断键值对数组table[]是否为空或为null，否则执行resize()进行扩容；
根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向 ⑥，如果table[i]不为空，转向③；
判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤
遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

思考：HashMap在put元素的时候，如何获取到元素存储的位置？

先调用key的hashcode方法，获取到hashcode值，然后再用这个hashcode值与他右移16位后的二进制进行按位异或得到最后的hash值，简称为二次hash。其目的是为了使HashMap集合中的key的分步更加均匀，避免出现某些位置元素特别多，某些位置元素特别少的情况，减少树化概率。

1.2.9 多线程环境下HashMap会出现什么问题

JDK1.7 的时候会出现并发死链问题：
- 因为在JDK1.7的时候底层的数据结构是数组和链表，在数组进行扩容的时候，因为链表是头插法，在进行数据迁移的过程中，有可能导致死循环
- 比如说，现在有两个线程
  - 线程一：读取到当前的hashmap数据，数据中一个链表，在准备扩容时，线程二介入
  - 线程二也读取hashmap，直接进行扩容。因为是头插法，链表的顺序会进行颠倒过来。比如原来的顺序是AB，扩容后的顺序是BA，线程二执行结束
  - 当线程一再继续执行的时候就会出现死循环的问题
  - 线程一先将A移入新的链表，再将B插入到链头，由于另外一个线程的原因，B的next指向了A，所以B->A->B，形成循环
- 当然，JDK 8 将扩容算法做了调整，不再将元素加入链表头（而是保持与扩容前一样的顺序），尾插法，就避免了jdk7中死循环的问题
JDK1.7版本和JDK1.8版本都会出现并发数据丢失问题：
- 多线程情况下，多个线程操作多个key，多个key的hash值相同，在HashMap底层会首先判断该Key对应的索引位置是否存在元素，如果不存在元素就会创建新的node，将node放入到对应的索引位置
- 这个时候：
  - 第一个线程判断元素不存在，创建了node，在存入到数组之前，第二个线程执行了，也判断元素不存在，也会创建node，之后将元素存入数组，这样两个线程都将元素存入到数组的同一个位置，就会有一个线程的数据丢失

1.2.10 说一说HashMap和HashTable的区别

相同点：

HashMap和HashTable都是键值对形式的集合，可以存储键值数据
HashMap和HashTable都实现了Map, Cloneable, Serializable 这三个接口，操作方式基本相同

不同点：

底层数据结构不同：JDK1.7底层都是数组+链表，但JDK1.8中 HashMap加入了红黑树
Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null
添加key-value的hash值算法不同：HashMap添加元素时，使用的是二次HASH，而HashTable是直接采用key的hashCode()
初始化容量不同：HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75
扩容机制不同：当已用容量>总容量 * 负载因子时，HashMap 扩容规则为当前容量翻倍，Hashtable 扩容规则为当前容量翻倍 +1
线程安全：Hashtable是线程安全的的，适用于多线程环境，而HashMap不是线程安全的，多线程环境可能会出现并发问题。因为效率的原因现在Hashtable使用的也很少一般使用ConcurrentHashMap

1.2.11 线程安全的map集合允许有空值吗

HashMap 、LinkedHashMap 的 key 和 value 都允许为 null
ConcurrentHashMap、Hashtable 的 key 和 value 都不允许为 null，为了保证线程安全

1.2.12 说一说HashSet实现原理

HashSet底层其实是用HashMap实现存储的，HashSet封装了一系列HashMap的方法。依靠HashMap来存储元素值，利用hashMap的key键进行存储，而value值默认为Object对象。所以HashSet也不允许出现重复值，判断标准和HashMap判断标准相同，两个元素的hashCode相等并且通过equals()方法返回true。

添加元素的时候将元素添加到HashMap的Key的位置，值的话就是一个PRESENT（一个Object对象）。

1.2.13 你使用过的线程安全的集合有哪些

线程安全的集合有很多，例如：

Vector：就比Arraylist多了个 synchronized （线程安全），因为效率较低，现在已经不太建议使用。
HashTable：就比HashMap多了个synchronized (线程安全)，不建议使用。
ConcurrentHashMap：高并发、高吞吐量的线程安全HashMap实现，推荐使用
CopyOnWriteArrayList : 线程安全的 List，在读多写少的场合性能非常好，远远好于 Vector
ConcurrentLinkedQueue : 高效的并发队列，使用链表实现。可以看做一个线程安全的 LinkedList，这是一个非阻塞队列

1.2.14 HashTable是如何实现线程安全的

HashTable使用 synchronized 来保证线程安全，效率非常低下。在HashTable内部的方法上都加上了synchronized关键字，相当于锁的是整个HASH表结构。

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

1.2.15 说一说ConcurrentHashMap的实现原理

在JDK1.7的时候：ConcurrentHashMap的底层数据结构是Segment数组 + HashEntry的形式实现
- ConcurrentHashMap首先会将数据分为一段一段的存储，每个分段就是一个Segment，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问，在默认情况下，会将底层数据划分为16个分段，所以性能相对于HashTable而言提高了16倍
- Segment数组中的每一个Segment元素保存的是一个HashEntry数组，这个HashEntry数组的结构就跟HashMap比较类似，使用的是数组 + 链表结构
在JDK1.8的时候：放弃了Segment臃肿的设计，底层的数据结构和HashMap的数据结构相同
- 采用Node + CAS + Synchronized来保证并发安全进行实现，synchronized只锁定当前链表或红黑树的首节点，这样只要hash不冲突，就不会产生并发，效率得到提升

思考：这整个过程的cas体现在了哪？

CAS：在判断数组中当前位置为null的时候，使用CAS来把这个新的Node写入数组中对应的位置

1.2.16 如何实现对集合中的数据排序

对集合中的数据排序可以通过以下几种方式实现：

自然排序：通过实现Comparable接口，重写compareTo方法，定义对象的自然排序规则。
定制排序：通过实现Comparator接口，重写compare方法，在排序时传入定制的比较器。
使用工具类：如Collections.sort()方法对List进行排序，或者使用Stream API的sorted()方法。

1.2.17 对集合数据进行遍历的方式有哪些

对集合数据进行遍历的方式主要有以下几种：

增强for循环：适用于数组和实现了Iterable接口的集合，语法简洁。
迭代器：通过Iterator或ListIterator遍历集合，支持在遍历过程中删除元素。
普通for循环：通过索引访问集合元素，适用于List等有序集合。
Stream API：Java 8 引入的流式操作，可以方便地对集合进行遍历、过滤、映射等操作。

1.2.18 增强for循环和Iterator有什么区别

增强for循环底层就是使用的迭代器实现的，所以除了书写形式几乎没有什么区别。

迭代器是用于方便集合遍历的，实现了Iterable接口的集合都可以使用迭代器来遍历。

增强for循环，内部使用的是迭代器，所以它的操作对象是数组和可以使用迭代器的集合。

需要注意的是使用迭代器遍历元素时，除了查看之外，只能做remove操作。

1.2.19 在使用增强for循环遍历的过程中是否可以删除元素

使用增强的for循环，不能对元素进行删除，报出ConcurrentModificationException。

迭代器内部的每次遍历都会记录List内部的modCount当做预期值，然后在每次循环中用预期值与List的成员变量modCount作比较，但是普通list.remove调用的是List的remove，这时modCount++，但是iterator内记录的预期值并没有变化，所以会报错。

如果需要在遍历的过程中删除元素，可以使用Iterable迭代器进行遍历，使用迭代器的remove方法进行删除。

1.2.20 Collection和Collections有什么区别

Collection是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java类库中有很多具体的实现，例如：List、Set。
Collections是一个操作集合的工具类。它包含各种有关集合操作的静态方法，例如：排序、转换、替换、拷贝等。

1.2.21 如何将一个线程不安全的集合转化为线程安全的集合

使用Collections类中的synchronizedXxx()方法，将线程不安全的集合传递进去，就会返回线程安全的集合。

底层使用的是装饰设计模式，对原生的集合进行增强，装饰方法中添加了synchronized保证线程安全。