集合框架

大约 15 分钟

阅读提示

集合题核心是三条线：整体分类、常用容器对比、HashMap 原理。
回答时尽量带复杂度和适用场景，避免只背定义。

Java集合

回答提示：是一种比较通俗的解释，比较好理解，如果‘参考答案’不太好记住，可以直接复习回答提示也可以。

1、Java中的集合类有哪些？如何分类的？(此问题基本不会被问到，但是要大体理解整个集合的内容，如果能记住此问题（灵活记住），面试集合的基础问题基本都可以回答)

回答提示：

List（列表）：List接口及其实现类用于存储一组有序的元素。元素可以重复，且可以通过索引访问。常见的List实现类有ArrayList、LinkedList等。ArrayList基于动态数组实现，访问元素速度快；LinkedList基于双向链表实现，插入和删除操作效率高。
Set（集合）：Set接口及其实现类用于存储一组无序且唯一的元素。Set不允许出现重复元素，因此常用于去重操作。常见的Set实现类有HashSet、TreeSet等。HashSet基于哈希表实现，元素存储无序；TreeSet基于红黑树实现，元素会按照自然顺序或者自定义顺序排序。
Queue（队列）：Queue接口及其实现类用于在元素之间定义一种先进先出（FIFO）的排序方式。常见的Queue实现类有LinkedList（也实现了List接口）、PriorityQueue等。LinkedList可以用作双端队列；PriorityQueue是一个基于优先级堆的无界队列，元素的排序方式可以通过比较器来定义。
Map（映射）：Map接口及其实现类用于存储键值对。键是唯一的，每个键都映射到一个值。常见的Map实现类有HashMap、TreeMap等。HashMap基于哈希表实现，键值对存储无序；TreeMap基于红黑树实现，键会按照自然顺序或者自定义顺序排序。

参考回答：

集合类存放于 Java.util 包中，主要有 3 种：set(集）、list(列表包含 Queue）和 map(映射)。
Collection：Collection 是集合 List、Set、Queue 的最基本的接口。
Iterator：迭代器，可以通过迭代器遍历集合中的数据
Map：是映射表的基础接口

一定要牢牢记住这张图，大多比较浅的面试题都是从这上面问的。 arrayList的扩容机制认为是1.5倍就可以了

2、那些集合是线程安全的？

参考回答：

Vector：一个线程安全的List实现，它的大部分方法都是同步的，因此可以在多线程环境中使用。不过，由于同步操作会带来性能开销，所以在不需要线程安全的场合，建议使用ArrayList。
Hashtable：一个线程安全的Map实现，它同样是同步的，可以在多线程环境中使用。与HashMap相比，Hashtable的性能可能稍差一些，因为同步操作会增加额外的开销。
Stack：一个线程安全的栈实现，它也是同步的，可以在多线程环境中使用。不过，由于栈这种数据结构的使用场景相对较少，所以在实际开发中可能会更少用到Stack。
ConcurrentHashMap：一个线程安全的 HashMap 实现。早期版本（JDK 1.7 及以前）使用分段锁（Segment Locking）技术来提升并发性能，JDK 1.8 以后则使用了更加细粒度的锁，如链表或红黑树节点上的 synchronized 和 CAS 操作。在多线程环境下，ConcurrentHashMap 的并发性能通常优于 Hashtable 以及通过 Collections.synchronizedMap(new HashMap<>()) 包装得到的同步 HashMap，因为后两者都是对整个 map 加锁，从而限制了并发能力，而 ConcurrentHashMap 则支持更高的并发访问。
CopyOnWriteArrayList：一个线程安全的List实现，它通过在写操作时复制整个数组来实现线程安全。这种策略适用于读多写少的场景，因为写操作会涉及到复制整个数组，所以性能开销较大。

3、ArrayList的扩容机制是什么？

回答提示：

初始容量：ArrayList在创建时默认有一个初始容量，通常是10（但在某些版本或实现中可能有所不同）。
扩容触发：当向ArrayList中添加元素，且当前元素数量达到容量上限时，就会触发扩容操作。
扩容策略：ArrayList的扩容策略是增长大约50%的容量。
数组复制：扩容过程中，ArrayList会创建一个新的、更大容量的数组，并将原有数组中的所有元素复制到新数组中。

参考回答：

ArrayList的扩容机制是这样的：当向ArrayList中添加元素，而当前数组容量不足以容纳更多元素时，ArrayList会自动进行扩容。具体来说，它会创建一个新的数组，新数组的长度通常是当前数组长度的1.5倍（也就是增长50%，但这个值不是固定的，不同的JVM实现可能有所不同，有的是直接扩容为原来的两倍）。然后，ArrayList会将当前数组中的所有元素复制到新数组中，并将新数组设置为当前数组。这样，ArrayList就拥有了更大的容量，可以继续添加更多元素。

4、ArrayList和linkedList的区别？

回答提示：

内部实现：ArrayList是基于动态数组实现的，元素在内存中连续存储；而LinkedList则是基于双向链表实现，元素通过指针相互连接。
随机访问：ArrayList支持快速随机访问，时间复杂度为O(1)；LinkedList则需要遍历，时间复杂度为O(n)。
内存占用：LinkedList每个节点除了存储数据外，还需要存储指向前一个和后一个节点的指针，因此比ArrayList更占内存。
使用场景：ArrayList适用于需要频繁进行随机访问的场景；而LinkedList则更适用于需要频繁进行插入和删除操作的场景。

参考回答：

ArrayList：基于动态数组，连续内存存储，适合下标访问（随机访问），扩容机制：因为数组长度固定，超出长度存数据时需要新建数组，然后将老数组的数据拷贝到新数组，如果不是尾部插入数据还会涉及到元素的移动（往后复制一份，插入新元素），使用尾插法并指定初始容量可以极大提升性能、甚至超过linkedList（需要创建大量的node对象）
LinkedList：基于链表，可以存储在分散的内存中，适合做数据插入及删除操作，不适合查询：需要逐一遍历
遍历LinkedList必须使用iterator不能使用for循环，因为每次for循环体内通过get(i)取得某一元素时都需要对list重新进行遍历，性能消耗极大。另外不要试图使用indexOf等返回元素索引，并利用其进行遍历，使用indexlOf对list进行了遍历，当结果为空时会遍历整个列表。

5、HashMap和HashTable有什么区别？

回答提示：

线程安全性：HashMap是非线程安全的，而HashTable是线程安全的。HashTable通过synchronized关键字实现同步，但可能导致性能下降。
null值处理：HashMap允许null作为键和值，而HashTable不允许。
性能：由于HashMap不需要考虑线程同步，通常性能更高。

参考回答：

区别：

线程安全性

HashMap方法没有synchronized修饰，线程非安全，HashTable线程安全；

空键和空值：

HashMap允许key和value为null，而HashTable不允许

历史遗留：（了解）

Hashtable 是 Java 1.0 中的遗留类，虽然仍然可以使用，但通常建议使用 HashMap，并结合 java.util.concurrent 包中的现代并发类来处理多线程问题。
HashMap 是在 Java 2 中引入的，设计更现代化，使用也更加灵活。

迭代器：(了解)

HashMap 使用的是快速失败（fail-fast）的迭代器，如果在创建迭代器后对集合进行了结构上的修改（除了使用迭代器自身的 remove 方法外），迭代器会抛出 ConcurrentModificationException。
Hashtable 使用的是枚举（Enumeration），不是快速失败的迭代器。

性能：（了解）

在没有线程安全需求的场景中，HashMap 通常比 Hashtable 性能更高，因为它没有同步的开销。

HashMap底层原理

HashMap底层原理（了解）

默认初始容量为（数组长度为16），默认负载系数为0.75（这个表示的意思是扩容机制当容量达到75%的时候自动进行扩容（扩大一倍，扩容也是采用位运算【因为用乘法会影响CPU的性能，计算机不支持乘法运算，最终都会转化为加法运算[01的方式]），当扩容的时候，会创建新的数组，以前存放在数组中的数据将会重新通过hashCode进行排序，类似于hashCode/16取模【其实使用的是位运算，位运算效率更高】得到下标存放在对应的数组中，扩容后hashCode/32.）。
在 JDK 1.7 中 HashMap 是以「数组加链表」的形式组成的，****JDK 1.8 之后新增了「红黑树」的组成结构，「当链表长度大于 8 并且 hash 桶的容量大于 64 时，链表结构会转换成红黑树结构」。所以，它的组成结构如下图所示：

底层数据结构

HashMap 中数组的每一个元素又称为哈希桶，也就是 key-value 这样的实例。在 Java7 中叫 Entry，Java8 中叫 Node。因为它本身所有的位置都为 null，在 put 插入的时候会根据 key 的 hash 去计算一个 index 值。比如，我 put （"枫斗者"，666），在 HashMap 中插入 "枫斗者" 这个元素，通过 hash 算法算出 index 位置是 3。这时的结构如下所示，还是个数组。

			枫斗者
			666
0	1	2	3	4	5	6	7

初次 put没 hash 冲突时，若发生 hash 冲突就得引入链表啦。假设我再次 put （"枫哥"，666），在 HashMap 中插入 "枫哥" 这个元素，通过 hash 算法算出 index 位置也是 3。这时的结构如下所示：形成了链表

0	1	3
		枫斗者
		666
	↓
枫哥
666

再次 put，发生 hash 冲突，它的源码如下所示：「可以看出每个哈希桶中包含了四个字段：hash、key、value、next，其中 next 表示链表的下一个节点」。

static class Node < K, V > implements Map.Entry < K, V > {
    final int hash;
    final K key;
    V value;
    Node < K,
    V > next;

    ...
}

JDK 1.8 之后底层是基于数组+链表+红黑树。
底层原理：
先通过hash算法计算出当前键值的hashCode值，然后对数组长度进行取余【其实是位运算】，从而获得余数（即为下标）存储到对应的数组中【存储的是当前hash值（key计算的hash值），key，value和next】（所以HashMap存取数据元素是无序的）。[底层是位运算，性能更好，且可以更好的避免哈希碰撞]
通过下标存储键值时，如果当前下标没有存放其他键值时会直接存入，如果该下标处，已经存在其他键值时，则会发生哈希碰撞。
发生哈希碰撞后，会继续比较下标处所有key的equals（内容）是否为true（来判断是不是同一个元素。）
如果是true，表示是相同的key，执行覆盖操作。
如果是false，表示是不同的key，执行在最后一个键值对后面追加操作，从而形成单向链表（链表的产生）。
如果链表长度>=8个且当前Map集合中数组长度>=64个，则会形成红黑树；如果当前数组长度<64个，则会扩容键值对数组（16*2），而且会重新进行排序。（并且会重新将所有键值对对32进行取余重新排序进行存储从而导致效率低）
当调用remove方法的时候，会删除元素，当红黑树中剩余的键值对个数<=6个的时候，会重新还原成单向链表。（性能更好）

如何解决hash冲突？

拉链法，将产生hash碰撞的元素都链接到同一个链表中【形成链表结构】
再Hash法，将产生hash碰撞的元素再采用不同的哈希算法进行处理，直至没有哈希冲突。
建立公共溢出区，把哈希表分为基本表和溢出表，将产生哈希冲突的元素存储到公共溢出表
开放寻址法：将产生hash碰撞的元素，去寻找一个新的空闲的哈希地址
线性探测法：就是将在得到的hash值进行加1然后对数组长度取模，直到直到新的位置。
公式：h(x)=(Hash(x)+i)mod (Hashtable.length);（i会逐渐递增加1）
平方探测法（二次探测）：就是将在得到的hash值进行依次为+(i^2)和-(i2)然后对数组长度取模，直到直到新的位置。
公式：h(x)=(Hash(x) +i)mod (Hashtable.length);（i依次为+(i^2)和-(i2)）

HashMap为什么要用到链表结构？（了解）

当我们向HashMap中添加元素时，会先根据key进行哈希运算，把hash值对数组长度进去取模（实际是位运算）得到一个下标，然后通过下标将元素进行存储。如果当前下标位置有数据就产生了哈希碰撞，进行equals比较内容是否相等，如果相等进行覆盖，如果不等，就会在用拉链法然后将这个数据追加到最后一个键值后面，最终形成单向链表。

HashMap为什么选择红黑树？（了解）

当HashMap中同一个索引位置出现哈希碰撞的元素多了，链表会变得越来越长，查询效率会变得越来越慢。因此在JDK1.8之后，当链表长度超过8个，且数组长度>=64个的时候会将链表转坏为红黑树来提高查

HashMap链表和红黑树在什么情况下转换的？（了解）

当链表的长度大于等于8，同时数组的长度大于等于64，链表会自动转化为红黑树,当树中的节点数小于6，红黑树会自动转化为链表

HashMap在什么情况下扩容？（了解）

默认初始容量为（数组长度为16），默认负载系数为0.75（这个表示的意思是扩容机制当容量达到75%的时候自动进行扩容（扩大一倍），当扩容的时候，会创建新的数组（数组中村的entry对象，key是对象通过hash算法运算后取模后的值，value是真正的对象），以前存放在数组中的数据将会重新通过hashCode进行排序，类似于hashCode/16取余得到下标存放在对应的数组中，扩容后hashCode/32.）。
HashMap的扩容公式：initailCapacity * loadFactor 【负载因子】= HashMap
其中initailCapacity是初始容量：默认值为16（懒加载机制，只有当第一次put的时候才创建）
采用位运算的方式1*2的4次方
其中loadFactor是负载因子：默认值为0.75
默认扩大一倍。

HashMap是如何Put一个元素的？

首先，将key进行hash运算，然后对数组长度进行取模（底层是位运算），计算出索引（下标）。此时判断该索引位置是否已经有元素了，如果没有，就直接放到这个位置。如果这个位置已经有元素了，也就是产生了哈希碰撞，那么判断旧元素的key和新元素的key的hash值是否相同，并且将他们进行equals比较，如果相同证明是同一个key，就覆盖旧数据，并将旧数据返回，如果不相同的话再判断当前桶是链表还是红黑树，如果是红黑树，就按红黑树的方式，写入该数据，如果是链表，就依次遍历并比较当前节点的key和新元素的key是否相同，如果相同就覆盖，如果不同就接着往下找，直到找到空节点并把数据封装成新节点挂到链表尾部。然后需要判断，当前链表的长度是否大于转化红黑树的阈值，如果大于就转化红黑树，最后判断数组长度是否需要扩容。

HashMap是如何Get一个元素的？（了解）

首先将key进行哈希运算，计算出数组中的索引位置，判断该索引位置是否有元素，如果没有，就返回null,如果有值，判断该数据的key是否为查询的key，如果是就返回当前值的value
如果第一个元素的key不匹配，判断是红黑树还是链表,如果是红黑树，就就按照红黑树的查询方式查找元素并返回,如果是链表，就遍历并匹配key，让后返回value值

你知道HahsMap死循环问题吗？（了解）

HashMap在扩容数组的时候，会将旧数据迁徙到新数组中，这个操作会将原来链表中的数据颠倒，比如a->b->null，转换成b->a->null这个过程单线程是没有问题的，但是在多线程环境，就可，能会出现a->b->a->b....，这就是死循环
在JDK1.8后，做了改进保证了转换后链表顺序一致，死循环问题得到了解决。但还是会出现高并发时数据丢失的问题，因此在多线程情况下还是建议使用ConcurrentHashMap来保证线程安全问题