[2024最新] java八股文实用版（附带原理）---java集合篇

介绍一下常见的list实现类？

ArrayList
线程不安全，内部是通过数组实现的，继承了AbstractList，实现了List，适合随机查找和遍历，不适合插入和删除。排列有序，可重复，当容量不够的时候，会将原容量增加50%（即乘以1.5）。
​
LinkedList
LinkedList 是用链表结构存储数据的，线程不安全。很适合数据的动态插入和删除，随机访问和遍历速度比较慢，增删快。另外，他还提供了 List 接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用。底层使用双向链表数据结构。
​
Vector（数组实现、线程同步）
Vector 与 ArrayList 一样，也是通过数组实现的，Vector和ArrayList用法上几乎相同，但Vector比较古老，一般不用。Vector是线程同步的，效率低。即某一时刻只有一个线程能够写 Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问 ArrayList 慢。默认扩展一倍容量。

ArrayList初始容量是多少？

ArrayList 默认的初始容量是 10。意味着当你创建一个新的 ArrayList 而不指定其容量时，它会以一个内部数组长度为 10 的数组来开始。当添加的元素数量超过这个初始容量时，ArrayList 的内部数组会进行扩容，通常是增长为原来的 1.5 倍。

ArrayList是如何扩容的？

1.一个新的ArrayList对象时，它通常会分配一个初始容量为10。
2.当向ArrayList中添加一个新元素，并且该元素的数量超过当前数组的容量时,就会触发扩容操作
3.扩容公式:newCapacity = oldCapacity + (oldCapacity >> 1)，这实际上是将原容量增加50%（即乘以1.5）。
4、扩容过程：创建一个新的数组，其长度为新计算的容量。将原数组中的所有元素复制到新数组中。将ArrayList的内部引用从原数组更新为新数组。将新元素添加到新数组的末尾。

ArrayList的添加与删除元素为什么慢？

ArrayList的添加与删除操作慢，主要是因为其内部实现基于数组，而数组在插入和删除元素时需要移动其他元素来保证连续性和顺序性，这个过程需要耗费较多的时间。

java容器有哪些？

ArrayList如何保证线程安全？

1.借助锁:可以通过在访问 ArrayList 的代码块上使用 synchronized 关键字来手动同步对 ArrayList 的访问。这要求所有访问 ArrayList 的代码都知道并使用相同的锁。
2.使用 Collections.synchronizedList

聊聊常见set类都有哪几种？

HashSet
HashSet线程不安全，基于哈希表实现，具有快速的插入、删除和查找操作。不保证元素的迭代顺序，允许null元素的存在，但只能有一个null元素。
​
LinkedHashSet
LinkedHashSet是HashSet的子类，基于哈希表和双向链表实现，可以维护元素的插入顺序。相比于 HashSet 增加了顺序性，因此当需要保持元素插入顺序时，可以选择使用LinkedHashSet。
​
TreeSet
TreeSet线程不安全，基于红黑树实现，不允许null值存在，可以对元素进行自然排序或自定义排序。可以实现元素按照升序进行排序。

常见set的使用场景

HashSet：适用于需要快速查找的场景，不保证元素的顺序。
LinkedHashSet：适用于需要保持元素插入顺序的场景。
TreeSet：适用于需要元素排序的场景。

HashSet如何实现线程安全？

使用Collections.synchronizedSet
Java 提供了一个简单的方法来创建一个同步的集合，通过Collections.synchronizedSet方法。这个方法返回一个线程安全的集合包装器。使用这个方法后，所有对集合的访问都将是同步的。
​
使用ConcurrentHashMap
如果需要更高效的并发访问，可以使用ConcurrentHashMap来实现类似HashSet的功能。
​
手动同步
如果你不想使用上述任何一种方法，也可以手动同步HashSet的访问。可以使用synchronized关键字来保护对HashSet的访问

介绍一下HashMap？

HashMap主要是用于存储键值对。基于哈希表实现，提供了快速的插入、删除和查找操作，线程不安全的，允许一个 null 键或多个 null 值。
不记录映射的顺序。
​
主要方法
put(K key, V value)：将指定的值与该映射中的指定键关联。
get(Object key)：返回指定键所映射的值。
remove(Object key)：如果存在一个键的映射，则将其从映射中移除。
size()：返回此映射中的键值映射关系的数量。

HashMap怎么计算hashCode的？

HashMap使用键的hashCode()方法来生成哈希值，并对其进行一些处理，以提高哈希表的性能和均匀分布。

生成hashcode为什么要使用扰动函数？

目的：提高哈希码的质量，使其在哈希表中更均匀地分布。
扰动算法的步骤如下：
1. 获取键的哈希码：h = key.hashCode()
2. 右移 16 位：h >>> 16
3. 异或运算：h ^ (h >>> 16)
这种方法通过将高位和低位的哈希码混合在一起，减少了哈希冲突的概率，从而使得哈希码更加均匀地分布在哈希表的桶中。

HashMap的主要参数都有哪些？

初始容量：
初始容量是HashMap在创建时分配的桶数组的大小。默认初始容量是 16。可以在创建HashMap时通过构造函数指定初始容量。
​
负载因子（Load Factor）
负载因子默认负载因子是 0.75，这意味着当HashMap中的条目数达到当前容量的 75% 时，HashMap会进行扩容。负载因子越低，哈希表中的空闲空间越多，冲突越少，但空间利用率也越低。
​
阈值（Threshold）
阈值是HashMap需要扩容的临界点，计算方式为初始容量 * 负载因子。当实际存储的键值对数量超过这个阈值时，HashMap会进行扩容。
​
桶（Bucket）
HashMap内部使用一个数组来存储链表或树（在 Java 8 及之后的版本中，当链表长度超过一定阈值时，会转化为树）。每个数组元素称为一个桶（bucket）。哈希值经过计算后决定了键值对存储在哪个桶中。
​
哈希函数（Hash Function）
HashMap使用哈希函数将键的哈希码转换为数组索引。Java 的HashMap使用了扰动函数（perturbation function）来减少哈希冲突。
​
链表和树（Linked List and Tree）
在桶中的键值对存储方式上，HashMap使用链表来处理哈希冲突。在 Java 8 及之后的版本中，当链表的长度超过阈值（默认是 8）时，链表会转换为红黑树，以提高查找效率。  
​
红黑树转换阈值（Treeify Threshold）
这是一个阈值，当单个桶中的链表长度超过这个值时，链表会转换为红黑树。默认值是 8。
​
扩容因子（Resize Factor）
当HashMap的大小超过阈值时，容量会加倍。即新的容量是旧容量的两倍。
​
迭代器（Iterators）
HashMap提供了键、值和条目的迭代器，用于遍历HashMap中的元素。

为什么hashMap的容量扩容时一定是2的幂次?

在HashMap中，初始化设置长度时，容量自动转成 2 的幂次长度，这样设计有几个重要原因，主要是为了优化性能和简化计算。
​
减少哈希冲突：
哈希冲突发生时，不同的键计算出的索引相同，导致它们被存储在同一个桶中。通过将容量设置为2的幂次，哈希表能够更均匀地分布哈希值，减少冲突。
​
简化扩容
HashMap在需要扩容时，通常会将容量加倍。如果容量总是2的幂次，那么加倍后的容量仍然是2的幂次，这样可以简化扩容过程中的计算和重新哈希操作。
​
内存对齐和效率
计算机内存分配通常更高效地处理 2 的幂次大小的内存块。使用 2 的幂次长度可以更好地利用内存对齐，提高内存访问效率。

解决hash碰撞的方法？

链地址法（Chaining）
在这种方法中，每个桶（bucket）包含一个链表。当发生哈希碰撞时，新的键值对被添加到相应桶的链表中。
​
线性探测（Linear Probing）
当发生哈希碰撞时，线性探测法在哈希表中向后依次查找下一个空闲位置。
​
二次探测（Quadratic Probing）
二次探测法在发生哈希碰撞时，按照平方序列查找空闲位置（如 1, 4, 9, 16, ...）。
​
双重散列（Double Hashing）
双重散列法使用两个不同的哈希函数。当第一个哈希函数发生碰撞时，使用第二个哈希函数计算新的索引。
​
再哈希法（Rehashing）
再哈希法在发生碰撞时，使用不同的哈希函数重新计算哈希值，直到找到空闲位置。

HashMap的负载因子初始值为什么是0.75?

HashMap的负载因子（load factor）初始值设为 0.75 是一个经过权衡的结果，主要考虑了性能和内存使用之间的平衡。

HashMap，扩容过程？怎么解决哈希冲突？

HashMap 扩容过程
1. 当添加元素时，如果数组为空，会进行初始化：默认情况下，会创建一个长度为 16 的数组，并且加载因子默认为 0.75。
2. 当数组中的元素数量大于或等于数组长度与加载因子的乘积时：例如，当数组长度为16，加载因子为0.75，并且元素数量达到12时（16*0.75 = 12），会触发扩容。扩容时，数组长度会翻倍（通常是2的幂），并重新哈希所有元素到新的数组中。
​
哈希冲突解决
1. 链表法（链表或红黑树）：在 HashMap 中，每个位置（索引）可以存储一个链表（或红黑树，当链表长度超过一定阈值时）。当发生哈希冲突时，新的元素会被添加到对应的链表中。在 Java 8 及之后的版本中，当链表长度达到 8 且数组长度大于 64 时，链表会转换为红黑树以优化性能。
2. 哈希函数：为了降低哈希冲突的概率，HashMap 使用了一个哈希函数来计算键的哈希值。这个哈希函数考虑了键对象的哈希码以及键在数组中的索引位置，通过一些位运算得到最终的哈希值。这样可以确保哈希值的分布尽可能均匀，减少冲突的可能性。
3. 初始容量和加载因子：初始容量和加载因子也会影响哈希冲突的概率。较大的初始容量和较小的加载因子可以降低哈希冲突的概率，但也会增加空间开销。因此，在选择这些参数时需要根据具体需求进行权衡。

为什么hashmap多线程会进入死循环？

1、并发修改导致的链表环
当两个或多个线程同时修改HashMap，例如在同一个桶中插入元素，可能会导致链表的指针被错误地更新。
​
2、扩容导致的并发问题
HashMap在容量达到一定阈值时会进行扩容，即重新分配桶数组，并重新哈希所有键值对。如果在扩容过程中，有其他线程同时进行插入操作，可能会导致重新哈希过程中的数据不一致，进而引发死循环。
​
3、解决方案  
使用线程安全的数据结构，在多线程环境中，使用ConcurrentHashMap代替HashMap。ConcurrentHashMap通过分段锁机制来保证线程安全，并发性能更好。

什么是HashTable?

Hashtable很多映射的常用功能与 HashMap类似，不同的是它承自 Dictionary 类，单线程并且是线程安全的。日常不建议使用。

什么是LinkedHashMap?

1. 有序性：LinkedHashMap保证了键值对的顺序，可以是插入顺序（默认）或访问顺序（可选）。
2. 哈希表和链表结合：LinkedHashMap通过哈希表实现快速的键值对查找，同时通过双向链表维护顺序。
3. 允许null键和值：LinkedHashMap允许一个null键和多个null值。
4. 线程不安全：LinkedHashMap不是线程安全的，如果需要在多线程环境中使用，需要通过外部同步机制来保证线程安全。

linkedHashMap为什么能用来做LRUCache（缓存）？

LinkedHashMap 能用来做 LRU 缓存的关键原因在于它可以维护访问顺序，并且通过重写removeEldestEntry方法，可以轻松实现缓存的自动清理。
​
实现 LRU 缓存的步骤
1. 创建一个LinkedHashMap实例，并将accessOrder参数设置为true。
2. 重写removeEldestEntry方法，以便在缓存大小超过预定义的最大容量时自动移除最老的键值对。

linkedhashmap如何保证有序性？

1. 双向链表：LinkedHashMap在内部维护了一个双向链表。每个节点对应一个键值对，并且包含指向前一个节点和后一个节点的引用。通过这个链表，LinkedHashMap可以快速地遍历所有键值对，保持其有序性。
2. 插入顺序：默认情况下，LinkedHashMap按照键值对插入的顺序来维护顺序。每次插入新键值对时，它会将新节点添加到链表的末尾。
3. 访问顺序：如果在构造方法中将accessOrder参数设置为true，LinkedHashMap将按照访问顺序来维护键值对的顺序。每次访问（get或put操作）一个键值对时，它会将对应的节点移动到链表的末尾。

什么是fail-fast机制？

在Java集合框架中，fail-fast是一种机制，用于检测在遍历集合时的结构性修改，并立即抛出异常以防止不一致状态。fail-fast迭代器在检测到集合在迭代过程中被修改后，会抛出ConcurrentModificationException异常。