java集合概览

似乎我在 java 集合部分中的源码分析部分,了解的不够?但是时间不多了!需要加把劲了!

Java 集合概览

由两大接口派生而来:一个是 Collection 接口,主要用于存放单一元素;另一个是 Map 接口,主要用于存放键值对。对于 Collection 接口,下面又有三个主要的子接口:List、Set 、 Queue。

这里只列举了主要的继承派生关系,并没有列举所有关系。

集合框架底层数据结构总结

List

Set

Queue

Map

可能会被问到的重点问题!

加*的代表是重点!总的来说:ArrayListLinkedListHashMapConcurrentHashMap 为重点!其他的了解即可。

ArrayList 底层的实现原理是什么

new ArrayList(10) list 扩容几次?0 次

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

面试官再问:

ArrayList 和 LinkedList 的区别是什么?(*)

ArrayList 与 LinkedList 区别?

HashMap 的底层实现(*)

HashMap 的底层实现

JDK 1.7 和 1.8 的 HashMap 有什么区别?

HashMap 的 put 操作具体流程(*)

流程图:
../../../../ZZZ-Misc/Z-Attachment/images/Pasted image 20241210161902.png
(重)

  1. 判断键值对数组 table 是否为空或为 null,否则执行 resize()进行扩容(初始化)
  2. 根据键值 key 计算 hash 值得到数组索引
  3. 如果 table[i]==null 条件成立,直接新建节点添加
  4. 如果 table[i]!=null
    • 判断 table[i]的首个元素是否和 key 一样,如果相同直接覆盖 value
    • 判断 table[i] 是否为 treeNode,即 table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对
    • 遍历 table[i],链表的尾部插入数据,然后判断链表长度是否大于 8,大于 8 的话把链表转换为红黑树,在红黑树中执行插入操作,遍历过程中若发现 key 已经存在直接覆盖 value
  5. 插入成功后,判断实际存在的键值对数量 size 是否超多了最大容量 threshold (数组长度*0.75),如果超过,进行扩容

HashMap 的扩容机制是什么?

流程图:
../../../../ZZZ-Misc/Z-Attachment/images/Pasted image 20241210183948.png

HashMap 的寻址算法?

../../../../ZZZ-Misc/Z-Attachment/images/Pasted image 20241210193345.png|475

HashMap JDK 1.7 在多线程下死循环问题

参考视频:

在 jdk 1.7 的 hashmap 中在数组进行扩容的时候,因为链表是头插法,在进行数据迁移的过程中,有可能导致死循环

比如说,现在有两个线程
线程一:读取到当前的 hashmap 数据,数据中一个链表,在准备扩容时,线程二介入
线程二:也读取 hashmap,直接进行扩容。因为是头插法,链表的顺序会进行颠倒过来。比如原来的顺序是 AB,扩容后
的顺序是 BA,线程二执行结束。

线程一:继续执行的时候就会出现死循环的问题。
线程一先将 A 移入新的链表,再将 B 插入到链头,由于另外一个线程的原因,B 的 next 指向了 A,所以 B->A->&,形成循环。
当然,JDK 8 将扩容算法做了调整,不再将元素加入链表头(而是保持与扩容前一样的顺序),尾插法,就避免了 idk 7中
死循环的问题。