Java集合常见面试题一

Z时代
2024-01-10
分类：综合

java

参考：

开放地址法

HashMap为什么是线程不安全的？

红黑树、二叉搜索树的实现和性能比较(c++实现红黑树）

B+树索引与Hash索引的区别

为什么链表的长度是8的时转红黑树？+ 加载因子为什么是0.75？

为什么HashMap桶长度超过8才会转换成红黑树

为什么Map桶中个数超过8才转为红黑树

hashmap扩容时死循环问题

1、Arraylist的 add 方法是怎样的

添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为旧容量的 1.5 倍。

扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数

2、HashMap是怎么实现的

1. 存储结构

内部包含了一个 Entry 类型的数组 table。

transient Entry[] table;

Entry 存储着键值对。它包含了四个字段，分别是 key ， value, hashCode, 和 next 指针。从 next 字段我们可以看出 Entry 是一个链表。即数组中的每个位置被当成一个桶，一个桶存放一个链表。HashMap 使用拉链法来解决冲突，同一个链表中存放哈希值和散列桶取模运算结果相同的 Entry。

2. put 操作过过程

根据 key 值计算出 hashCode 值，根据 hashCode 值与 hash 数组长度取余得到桶的下标，如果是key 是 null值，则放在第0个桶中

在对应的的桶链表中查找是否已存在该key, 如果存在则更新，否则执行插入操作

插入操作先判断是否需要扩容，如果需要扩容，则扩容为原来的2倍，把原来的键值对都拷贝到新的数组中，然后执行插入操作

其中取模是将取模运算转换成与数组长度进行按位与运算来提高效率，但是这个操作转换的前提是数组长度必须是 2 的 n 的方，所以限制了数组长度是 2 的 n次方

3. 查找操作过程

计算键值对所在的桶；

在链表上顺序查找，时间复杂度显然和链表的长度成正比。

4. 扩容

当往 HashMap中添加元素时，hashMap 会根据当前数组容量大小，键值对数量，以及装填因子来衡量空间效率和时间效率，如果觉得有必要扩容，HashMap调用 resize()函数进行扩容为原来的两倍，过程中需要调用 transfer() 函数将原 table 中的数据拷贝到新的数组中，这是很耗费时间的。

5. 链表转换成红黑树

JDK1.8 以后，当数组大小已经超过64并且链表中的元素个数超过默认设定（8个）时，将链表转化为红黑树

6.HashMap 的优缺点：

优点：

HashMap通过计算hash值实现快速查找的的功能，所以查找效率特别高

缺点：

线层不安全

如果hash 重复率非常高，就会使得链表长度很长，查找效率低，如果 hash 值冲突非常小，就会造成数组特别长，空间效率低，所以 JDK 1.8 以后，当数组大小已经超过64并且链表中的元素个数超过默认设定（8个）时，将链表转化为红黑树

3、HashMap与ConcurrentHashMap的性能比较

HashMap 和 ConcurrentHashMap 的查找效率都非常高，但是 HashMap 线程不安全，但又因为它没加锁，所以在单线程下它的效率会比ConcurrentHashMap 效率高，ConcurrentHashMap 线程安全，在多线程下效率也非常高，适合在多线程下使用。

CouncurrentHashMap 介绍

和hashmap一样，在jdk1.7中ConcurrentHashMap的底层数据结构是数组加链表。和hashmap不同的是ConcurrentHashMap中存放的数据是一段段的，即由多个Segment(段)组成的。每个Segment中都有着类似于数组加链表的结构。

其中 Segment 的个数控制了并发级别，在一个ConcurrentHashMap创建后Segment的个数是不能变的，扩容过程过改变的是每个Segment的大小。

在这种机制中，任意数量的读取线程可以并发访问Map，执行读取操作的线程和执行写入操作的线程可以并发地访问Map，并且一定数量的写入线程可以并发地修改Map，这使得在并发环境下吞吐量更高，而在单线程环境中只损失非常小的性能

分段锁的优缺点

段Segment继承了重入锁ReentrantLock，有了锁的功能，每个锁控制的是一段，当每个Segment越来越大时，锁的粒度就变得有些大了。

分段锁的优势在于保证在操作不同段 map 的时候可以并发执行，操作同段 map 的时候，进行锁的竞争和等待。这相对于直接对整个map同步synchronized是有优势的。

缺点在于分成很多段时会比较浪费内存空间(不连续，碎片化); 操作map时竞争同一个分段锁的概率非常小时，分段锁反而会造成更新等操作的长时间等待; 当某个段很大时，分段锁的性能会下降。

其中Segment的个数限制了并发级别，在一个ConcurrentHashMap创建后Segment的个数是不能变的，扩容过程过改变的是每个Segment的大小。

java8的ConcurrentHashMap为何放弃分段锁，为什么要使用CAS+Synchronized取代Segment+ReentrantLock

JDK 1.8 以后，ConcrrentHashMap 采用的是在HashMap 的基础上对每个桶加锁的形式实现的，取代了原来 segment + ReetrantLock 的形式。分段锁的缺点是在于分成很多段时会比较浪费内存空间(不连续，碎片化); 操作map时竞争同一个分段锁的概率非常小时，分段锁反而会造成更新等操作的长时间等待(因为加锁操作会涉及到用户态和内核态的切换); Segment的个数限制了并发级别，且随着段的增大，锁的粒度在增大，分段锁的性能会下降，但是改成 CAS + synchroinzed 后，仍是一个完整的数组，不会有碎片化的问题，而且桶的个数代表了并发度，并发级别也比原来的高。

至于对每个桶进行加锁，选择的是 synchronized 而不是 reetrantLock, 这是因为在锁的粒度比较小的情况下，经过优化的synchronized 会比 ReetrantLock 有更好的性能。因为锁的粒度比较小的情况下，如果使用ReentrantLock则需要节点继承AQS来获得同步支持，增加内存开销，而synchronized则是JVM原生支持的，内存开销较小

目前currentHashMap的应用我在spring的的三级缓存中看到过。用来做第一级缓存的容器。

JDK 1.8 CurrentHashap的 put 操作

put操作分成两种情况，

一种是计算出来的下标对应的桶是空的，也就是说我们要此次要插入的这个键值对是这个桶的第一个键值对，这时候我们就需要采用CAS操作来将将这个键值对插入到这个桶的头结点中，这个过程没有加锁，所以没有加锁的开销。

另一种就是计算出来的下标对应的桶不为空，这时先判断该key是否已经存在，如果存在使用CAS操作修改值，如果不存在这时候就需要对桶的头结点进行synchronized加锁，然后把键值对插入到这个桶所在的链表或者红黑树中，因为jdk1.5以后对synchronized进行了优化，引入了偏向锁和自旋锁，所以这个也降低了加锁开销。

锁的粒度比较小的情况下，为什么不用ReentrantLock而用synchronized ?

减少内存开销:如果使用ReentrantLock则需要节点继承AQS来获得同步支持，增加内存开销，而1.8中只有头节点需要进行同步。

内部优化:synchronized则是JVM直接支持的，JVM能够在运行时作出相应的优化措施：锁粗化、锁消除、锁自旋等等。

如何实现线程安全的HashMap

hashTable, synchronizedMap, ConcurrentHashMap

Collections.sychronizedMap与ConcurrentHashMap的区别

hashtable和concurrenthashmap都是线程安全的，有什么不同？

HashTable 是直接用 synchronized 关键字保证线程安全，但是只能每次只能一个线程访问，效率低。ConcurrentHashMap 效率高，并发度高且线程安全。

4、HashMap解决hash冲突的方法

链表头插法（JDK1.7之前）

链表头插法（JDK1.8及JDK1.8之后）

5、常见解决hash冲突的方法

链表法和开放地址法。

链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位；

开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。

开放地址法又分为以下三种：

线性探测：当发现冲突后，就尝试放在下个位置，如果下个位置还是冲突则再尝试下个位置，一直到不冲突为止

二次探测：当发现冲突后，就尝试放在当前位置往后1平方的位置，如果下个位置还是冲突则尝试放在往后2平方的位置，直到不冲突为止

双散列：也成为再哈希法，如果发生冲突，这个位置增量是通过一个哈希函数计算出来的

值得提醒的是，对利用开放地址法查了冲突所产生的哈希表中删除一个元素，不能简单地直接删除，因为这样将截断其它具有相同哈希地址的元素的查找地址，所以应设定一个特殊的标志以表明该元素已被删除。

参考：开放地址法

6、为什么HashMap 长度为2的幂次方

通常，hash表通过【取模操作】确定元素位置

在数组长度 = 2的幂次方条件下，【取模操作等价 hash & (n-1)】。而位操作效率更高。

7、HashMap 扰动函数作用

1. key的hashCode()经过HashMap的【扰动函数】处理得到hash值

扰动函数通过【key.hashCode()的高十六位和低十六位进行异或】，得到hash值。从而减少碰撞。

8、HashMap 并发抛出异常的场景

1. put操作并发问题若线程A B 执行put操作时，若两者【key在数组中定位相同】，读取到【同一个头节点】。则一个线程写入的新头节点必被另一个线程写入的头节点覆盖。

2. resize() 并发问题扩容可能构成环形链表

参考：HashMap为什么是线程不安全的？

9、红黑树

红黑树性质

红黑树又称为自平衡的二叉查找树。

1.每个结点要么是红的要么是黑的。

2.根结点是黑的。

3.每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。

4.如果一个结点是红的，那么它的两个儿子都是黑的。

5.任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这五个性质强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。为什么呢？性质4暗示着任何一个简单路径上不能有两个毗连的红色节点，这样，最短的可能路径全是黑色节点，最长的可能路径有交替的红色和黑色节点。同时根据性质5知道：所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

一颗有n个内结点的红黑树的高度至多为2lg(n+1).

红黑树与二叉查找树的性能比较：

由于二叉树对某个元素的搜索是与该元素的距离树根结点的高度来决定的，而红黑树的高度不会超过2lg(n+1),因此可以在O(logn)时间内做查找，插入和删除，时间非常快，而二叉查找树通常情况不是一个平衡的二叉树，最坏情况下，树的高度可以达到n，因此查找的时间为O（n）。

红黑树和平衡二叉树的优势的插入删除维护平衡旋转的次数更少

参考：

红黑树、二叉搜索树的实现和性能比较(c++实现红黑树）

B+树索引与Hash索引的区别

既然红黑树那么好，为啥hashmap不直接采用红黑树，而是当大于8个的时候才转换红黑树？

因为数据量小的时候往往复杂度高的算法效率高，比如在数据量比较小时，插入排序效率就比快速排序的效率高。

红黑树需要进行左旋，右旋操作，有一定的维护和建立开销，而单链表不需要，
以下都是单链表与红黑树结构对比。
如果元素小于8个，查询成本高，新增成本低
如果元素大于8个，查询成本低，新增成本高

参考：既然红黑树那么好，为啥hashmap不直接采用红黑树，而是当大于8个的时候才转换红黑树？

10、HashMap扩容相关

10.1 为什么要转换成树结构

因为TreeNode结点一般有2个指针，分别指向左右孩子结点，但是普通单链表结点一般只有一个指针，指向后一个结点，所以树状节点的大小大约是常规链表节点的两倍，所以只有当树节点的个数足够多，即树接近一棵满二叉树的时候，我们才会转换成一个二叉树，这样才不会有大量空闲的空指针。但是如果当元素个数变少，二叉树存在大量空指针的时候，就应该重新退化成链表。这样的空间效率更高。

10.2为什么转换成红黑树而不是二叉查找树和平衡查找树

因为红黑树的查找效率比二叉查找树高，插入结点平均旋转次数小于平衡查找树。所以选择了红黑树。

10.3 为什么链表的长度是8的时转红黑树？+ 加载因子为什么是0.75？

首先需要明确的是：加载因子越大空间利用率就越高，可以充分的利用数组的空间；加载因子越小产生碰撞的概率的就越小，进而查找的就越快(耗时少)；简而言之是空间和时间的关系
为什么链表的长度是8的时转红黑树？+ 加载因子为什么是0.75？根据泊松分布可以得出当加载因子为0.75，链表长度为8时，理想情况下随机hashCode算法下所有bin中节点的分布频率会遵循泊松分布，一个hashmap中链表长度达到8个元素的概率为千万分之6，几乎是不可能事件。

参考：为什么链表的长度是8的时转红黑树？+ 加载因子为什么是0.75？

10.4 链表长度达到8就转成红黑树，当长度降到6就转成普通链表。8 和 6的选择的一个牵强的解释

红黑树的平均查找长度是log(n)，如果长度为8，平均查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，而log(6)=2.6，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短

参考：