Java集合经典面试题

基础知识

Java集合框架体系

image-20250308165857396

常见复杂度表示形式

时间复杂度

image-20250308170120745

空间复杂度

image-20250308170814615

image-20250308170841010

List相关面试题

数组结构—数组

image-20250308171339118

image-20250308171442534

image-20250308171537103

image-20250308171644837

image-20250308171656156

image-20250308171723069

image-20250308171805575

ArrayList源码分析

成员变量

image-20250309160258200

构造函数

image-20250309160409163

关键方法

image-20250309160803800

image-20250309160908463

第10次时，minCapacity = elementData.length，所以不需要扩容

第11次时，minCapacity = 11 > elementData.length，会扩容1.5倍，elementData的长度变为15。

ArrayList底层实现原理

image-20250309161409638

ArrayList list = ArrayList(10)中的list扩容几次

image-20250309161453786

如何实现数组和list之间的转换

image-20250309170226249

image-20250309170434111

ArrayList和LinkedList的区别是什么

相关内容——链表：

image-20250309170726347

回答：

  1. 底层数据结构
  2. 效率
  3. 空间
  4. 线程是否安全

image-20250309170831914

image-20250309170942764

HashMap相关面试题

数据结构

二叉树

image-20250309171434960

image-20250309171452763

image-20250309171507145

二叉搜索树

image-20250309171550340

image-20250309171650559

image-20250309171708178

image-20250309171730845

红黑树

image-20250309171802495

性质：

image-20250309171945880

复杂度：
image-20250309172033745

image-20250309172046399

散列表

在HashMap中的最重要的一个数据结构，在散列表中又使用了红黑树和链表

概念

image-20250309172503250

image-20250309172527208

散列函数

image-20250309172604044

散列冲突

image-20250309172653022

拉链法

image-20250309172719284

时间复杂度

image-20250309172749225

image-20250309172834217

image-20250309172848571

image-20250309172859851

总结

image-20250309172928131

说一下HashMap实现原理

image-20250309173122070

HashMap的jdk1.7和jdk1.8有什么区别

image-20250309173303688

image-20250309173332129

HashMap的put方法的具体流程

HashMap源码分析

常见属性

image-20250309173556472

image-20250309173712859

添加数据

image-20250309175053425

image-20250309175157896

讲一讲HashMap的扩容机制

HashMap源码分析

image-20250309195404495

image-20250309195808913

计算方式的原因：

  • e.hash & (newCap - 1)：相当于用当前数的哈希值对新的容量取模，比如哈希值为17，新的容量为16，则相当于将17与二进制1111进行与运算，拿到低位的值，即取模后的值
  • e.hash & oldCap：如上面的例子，将17和10000进行与运算，不为0则说明这个哈希值比16大，则需要后移增加容量的大小，如17将会移到17的位置（17%32=17）

HashMap的寻址方法

image-20250309200731249

右移16位后将高位和低位混合，提高随机性。

为何HashMap的数组长度一定是2的次幂

image-20250309200933043

image-20250309200956382

HashMap在1.7情况下的多线程死循环问题

image-20250309202116766

image-20250309202140327

线程2先迁移，先将A迁移过来，在用头插法将B迁移到A的前面，如下图：

image-20250309202408844

然后线程1先将A迁移过来，e指向next指向的，即B，next指向B的后面，此时为A，然后将B迁移上去，此时e指向A，next指向A的后面，即null，如下：

image-20250309202853495

然后将A迁移上去，e指向null，如下：

image-20250309202940052

这样导致A和B互相指向，在访问时会产生死循环。

image-20250309203046160