【Java面试总结】Java集合

以你之姓@ 2024-04-03 12:00 97阅读 0赞

## Java 集合 ##

### 1. 说说List、Set、Map三者的区别 ###

*  **List（对付顺序的好帮手）**：List接口存储一组**不唯一**（可以有多个元素引用相同的对象），**有序**的对象
 *  **Set（注重独一无二的性质）**：**不允许重复**的集合。不会有多个元素引用相同的对象
 *  **Map（用key来搜索的专家）**：使用**键值对存储**。Map会维护与key有关联的值。两个key可以引用相同的对象，但key不能重复，典型的key是String类型，也可以是任意类型

### 2. ArrayList与LinkedList的区别 ###

1.  **是否保证线程安全**：`ArrayList`和`LinkedList`都是不同步的，也就是不保证线程安全；
2.  **底层数据结构**：`ArrayList`底层使用的是`Object`数组；`LinkedList`底层使用的是双向链表 数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
3.  **插入和删除是否受元素位置的影响**： ① . `ArrayList`采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行`add(E e)`方法的时候，`ArrayList`会默认将指定的元素追加到此列表的末尾，这种情况的时间复杂度就是 0(1)。但是如果要在指定位置 i 插入和删除元素的话（`add(int index,E e)`）时间复杂度就是 0(n - i)。因为在进行上述操作的时候，集合中第 i 个元素和第 n- i 个之后的元素都要向后/向前移一位。 ② . `LinkedList`采用链表存储，所以对于`add(E e)`方法的插入和删除的时间复杂度不受元素位置的影响，近似 0(1)，如果是要在指定位置 i 插入或删除元素的话（`add(int index,E e)`）时间复杂度近似为 0(n)，因为需要先移动到指定位置再插入
4.  **是否支持快速随机访问**：`LinkedList`不支持搞笑的随机元素访问，而`ArrayList`支持。快速随机访问就是通过元素的序号快速获取元素对象（对应于`get(int index)`方法）
5.  **内存占用空间**：`ArrayList`的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 `LinkedList`的空间花费则体现在它的每一个元素都需要消耗比 `ArrayList`更多的空间（因 为要存放直接后继和直接前驱以及数据）。

#### list 的遍历方式选择： ####

*  实现了 `RandomAccess`接口的 list，优先选择普通的 for 循环，其次是 foreach
 *  未实现 `RandomAccess`接口的 list，则优先选择 `iterator`遍历（foreach遍历底层也是通过 iterator实现的），大 size 的数据，千万不要使用普通for循环

> 注： `ArrayLis`t实现了RandomAccess接口，而`LinkedList`没有实现。为什么呢？我觉得还是和底层数据结构有关！`ArrayList`底层是数组，而`LinkedList`底层是链表。数组天然支持随机访问，时间复杂度为 O（1），所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素，时间复杂度为 O（n），所以不支持快速随机访问。`ArrayList`实现了`RandomAccess`接口，就表明了他具有快速随机访问功能。`RandomAccess`接口只是标识，并不是说`ArrayList`实现`RandomAccess`接口才具有快速随机访问功能的！

更多关于 `RandomAccess`接口的知识，请百度。

#### 补充内容:双向链表和双向循环链表 ####

**双向链表：**包含两个指针，一个prev指向前一个节点，一个next指向后一个节点。

> 推荐阅读：[看图轻松理解数据结构与算法系列(双向链表)][Link 1]

**双向循环链表：**最后一个节点的 next 指向head，而 head 的prev指向最后一个节点，构成一个环。

### 3. ArrayList 与 Vector 区别呢?为什么要用Arraylist取代Vector呢？ ###

`Vector`类的所有方法都是同步的。可以由两个线程安全地访问一个 Vector 对象，但是一个线程访问 Vector 的话代码要在同步操作上耗费大量的时间。

`ArrayList`不是同步的，所以不需要保证线程安全时建议使用 ArrayList。

### 4. ArrayList 的扩容机制 ###

直接阅读Guide老哥的文章吧，我感觉写的很详细，我已经无法简写摘抄了，缺少一步都相当于缺少了灵魂：[通过源码一步一步分析ArrayList 扩容机制][ArrayList]

### 5. HashMap 和 HashTable 的区别 ###

1.  **线程是否安全**：`HashMap` 是非线程安全的，`HashTable` 是线程安全的。`HashTable` 内部的方法基本都经过 `synchronized`修饰。（如果要保证线程安全，就使用 `ConcurrentHashMap`）
2.  **效率**：因为线程安全的问题，`HashMap` 要比 `HashTable`效率高一点。另外，`HashTable` 基本被淘汰，不要在代码中使用它
3.  **对 Null key 和 Null value的支持**：`HashMap`中，`null` 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为`null`。但是在`HashTable`中 put 中的键值只有一个 null，直接抛出 `NullPointerException`
4.  **初始化容量大小和每次扩充容量的大小不同**： ① . **创建时如果不指定容量初始值**，`HashTable` 默认的初试大小为11，之后每次扩容 ，容量变成原来的 2n+1；`HashMap` 默认的初试大小为 16，之后每次扩容，容量变成原来的2倍。 ② . **创建时如果指定了容量初始值**，那么 `HashTable` 会直接使用给定的大小，而`HashMap` 会将其扩充为2 的幂次方大小。
5.  **底层数据结构**：JDK 1.8 以后的`HashMap` 在解决 哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转换为红黑树，以减少搜索时间。`HashTable` 没有这样的机制。

### 6. HashMap 和 HashSet 的区别 ###

`HashSet` 底层是基于 `HashMap` 实现的（`HashSet`的源码非常非常少，因为除了`clone()`、`writeObject()`、`readObject()`是`HashSet` 自己不得不实现之外，其他方法都是直接调用 `HashMap` 中的方法。

<table> 
 <thead> 
  <tr> 
   <th> <p>HashMap</p> </th> 
   <th> <p>HashSet</p> </th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td> <p>实现了Map接口</p> </td> 
   <td> <p>实现Set接口</p> </td> 
  </tr> 
  <tr> 
   <td> <p>存储键值对</p> </td> 
   <td> <p>仅存储对象</p> </td> 
  </tr> 
  <tr> 
   <td> <p>调用put()向map中添加元素</p> </td> 
   <td> <p>调用add()方法向map中添加元素</p> </td> 
  </tr> 
  <tr> 
   <td> <p>HashMap使用键（Key）计算Hashcode</p> </td> 
   <td> <p>HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性</p> </td> 
  </tr> 
 </tbody> 
</table>

### 7. HashSet如何检查重复 ###

当把对象加入`HashSet`时，`HashSet`会先计算对象的`HashCode`值来判断对象加入的位置，同时也会与其它加入的对象的`HashCode`的值做比较，如果没有相符的`HashCode`，`HashSet`会假设对象没有重复出现。但是如果发现有相同的`HashCode`值的对象，这时会调用`equals()`方法来检查`HashCode`相等的对象是否真的相同。如果两者相同，`HashSet`就不会让加入操作成功。

**`hashcode()`与`equals()`的相关规定：**

1.  如果两个对象相等，则hashcode一定也是相同的
2.  两个对象相等，对两个equals方法返回true
3.  两个对象有相同的hashCode值，它们也不一定是相等的
4.  综上，equals方法被覆盖过，则hashCode方法也必须被覆盖
5.  hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）

**== 与 equals 的区别**

1.  `==`是判断两个变量或实例是不是指向同一个内存空间 ，`equals`是判断两个变量或实例所指向的内存空间的值是不是相同
2.  `==`是指对内存地址进行比较 `equals()`是对字符串的内容进行比较
3.  `==`指引用是否相同 ,`equals()`指的是值是否相同

### 8. HashMap的底层实现 ###

JDK 1.8之前

JDK 1.8之前`HashMap`底层是 **数组和链表** 结合在一起使用也就是 **链表散列**。**HashMap** **通过 key 的hashCode经过扰动函数处理后得到的 hash 值，然后通过 （n - 1）& hash 判断当前元素存放的位置（这里的n指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash值，以及是key 是否相同，如果相同的话，直接覆盖，不相同就通过 拉链法解决冲突。**

**扰动函数指的就是 hashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 `hashCode()` 方法，换句话说使用扰动函数之后可以减少碰撞。**

JDK 1.8 HashMap 的 hash 方法源码:

staticfinalinthash(Objectkey) {
        int h;
        // key.hashCode()：返回散列值也就是hashcode
        // ^ ：按位异或// j>ké无符号右移，忽略符号位，空位都以0补⻬
        return (keyWXnull) ?0 : (h=key.hashCode()) ^ (hj>k16); 
    }

复制

JDK1.7的 HashMap 的 hash 方法源码:

staticinthash(inth) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
    
        h^= (hj>k20) ^ (hj>k12);
        returnh^ (hj>k7) ^ (hj>k4);
    }

复制

JDK 1.8 的 hash方法相比于 JDK 1.7 hash 方法更加简化，但是原理不变

相比于 JDK1.8 的 hash 方法，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。

“拉链法”就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK1.8之后相比于之前的版本， JDK1.8之后在解决哈希冲突时有了较大的变化，当链表⻓度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

> TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。

推荐阅读：[《Java 8系列之重新认识HashMap》][Java 8_HashMap]

注：本块内容后期再做整理修改

### 9. HashMap 的长度为什么是2的幂次方 ###

为了能让 `HashMap` 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。

`Hash` 值 的范围值 `-2147483648`到`2147483647`，前后加起来大概`40亿`的映射空间，只要哈希函数映射得比较均匀松散，一般应用很难出现碰撞的。但问题是一个`40亿`长度的数组，内存是放不下的，所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置，也就是对应的数组 下标。这个数组下标的计算方法是“`（n - 1）& hash`”。（n代表数组⻓度），这也就解释了`HashMap`的⻓度为什么是2的幂次方。

那么，如何设计这个算法呢？

我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“**取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%lengthdehash&(length-1)的前提是 length 是2的n 次方；）。”并且采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的⻓度为什么是2的幂次方。**

### 10. HashMap 多线程操作导致死循环问题 ###

主要原因在于并发下的`Rehash` 会造成元素之间会形成一个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用`HashMap`,因为多线程下使用`HashMap` 还是会存在其他问题比如数据丢失。并发环境下推荐使用 `ConcurrentHashMap`

推荐阅读：[疫苗：Java HashMap的死循环][Java HashMap]

### 11. ConcurrentHashMap 和 Hashtable 的区别 ###

后期补上

### 12. ConcurrentHashMap线程安全的具体实现方式/底层具体实现 ###

后期补上

### 13. comparable 和 Comparator的区别 ###

后期补上

### 14. 集合框架底层数据结构总结 ###

后期补上

### 15. 如何选用集合? ###

主要根据集合的特点来选用，比如我们需要根据键值获取到元素值时就选用`Map`接口下的集合，需要排序时选择`TreeMap`,不需要排序时就选择`HashMap`,需要保证线程安全就选用`ConcurrentHashMap`.当我们只需要存放元素值时，就选择实现`Collection`接口的集合，需要保证元素唯一时选择实现Set接口的集合比如`TreeSet`或`HashSet`，不需要就选择实现`List`接口的比如`ArrayList`或`LinkedList`，然后再根据实现这些接口的集合的特点来选用。

[Link 1]: https://juejin.im/post/6844903648154271757
[ArrayList]: https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/collection/ArrayList-Grow.md
[Java 8_HashMap]: https://zhuanlan.zhihu.com/p/21673805
[Java HashMap]: https://coolshell.cn/articles/9606.html