202206 集合 面试

实现原理

Iterator 的实现

• ArrayList 有内部类 Itr，
• 三变量：cursor、lastRet、expectedModCount，
• cursor 表示下个元素索，lastRet 表示上个元素的索引
• 初始化,astRet 比 cursor 少一
• hasNext() 判断 cursor 和 lastRet 是否相等。
• next()  返回 cursor 索引元素，修改 cursor、lastRet (+1),modCount != expectedModCount,抛出异常 ，实现快速失败(fail-fast)，

ArrayList 实现

2.26介绍一下ArrayList的数据结构?

• 底层是数组，第一次插入元素时创建大小为10的数组，超出限制时会增加50%的容量,并且数据以System.arraycopy()复制到新的数组。
• 按数组下标访问元素的性能很高。直接在数组末尾加入元素的性能高，按下标插入、删除元素，则要用System.arraycopy()来移动部分受影响的元素，性能差。

HashMap实现

HashMap put的过程 xx

• 1.首次扩容: (判断数组是否为空),数组为空进行扩容(resize) ;
• 2.计算索引:hash算法计算键值对在数组中的索引;
• 3.插入数据:
• 当前位置元素为空，则直接插入数据;
• 当前位置元素非空，且key已存在，则直接覆盖其value;
• 当前位置元素非空，且key不存在，则将数据链到链表末端;
• 若链表长度达到8，则将链表转换成红黑树，并将数据插入树中;
• 4.再次扩容  (如果数组中元素个数(size）)超过阀值(threshold,现有容量*加载因子),再次扩容。

HashMap xxx

• 键值对存储的容器
• 无序，key不重复；可空键，值；
• 非线性安全
• 初始长度是16,加载因子0.75

HashMap原理 xxx

• 底层数据结构：数组+(链表、红黑树)
• 内部实现数组是Node[]数组
• put的过程
• get方法就是计算出要获取元素的hash值，去对应位置获取即可
• 扩容机制 长度变为原来的两倍,重新插入到新数组。1.7(重新计算hash) 1.8((原)hash和(原)长度求与,第一位为1=索引+长度，否则原索引)
• HashMap大小是2的幂次方？效率高+空间分布均匀 (x)

HashMap原理 *****

• 底层是数组+(链表、红黑树)实现，数组每一个元素是链表结构，链表中的每个元素是Entry对象，存储真正k，v。

put方法实现

• ( 首次扩容: ,(判断数组是否为空) 数组为空进行扩容(resize) ;)
• 1(计算索引: ) (hash方法)计算key的hash值，10进制数字，数字和数组长度-1取模获取数组下标，根据数组下标找到对应单向链表
• 2  把链表中的每个元素和插入的key进行equals比较，相等则更新value值，不相等put到链表末端，
• 3 put过程中，键值对个数超过容量*负载因子，数组扩容2倍
• 4 若链表长度达到默认预值(8)，则将链表转换成红黑树，
•  (找不到对应key的hash值，直接插入数据)

get方法

• 计算key的hash值，找到对应数组下标，遍历对应下标的链表元素进行equals比较，key相等取出元素

最核心实现

• 利用hash计算下标位置，使用equals比较解决hash冲突

为什么使用红黑树

• 时间复杂度为o(logn)

LinkedHasMap实现

说一说你对LinkedHashMap的理解

• 使用双向链表维护元素插入顺序， 与迭代顺序一致。
• 避免对key-value排序，又避免使用TreeMap的成本。
• 需要维护元素的插入顺序，性能略低于HashMap的性能。
• 迭代访问全部元素时将有较好的性能。

2.20请介绍LinkedHashMap的底层原理

•  继承于HashMap，
• 通过维护一条双向链表,解决了HashMap不能随时保持遍历顺序和插入顺序一致的问题。
• 很多方法直接继承自HashMap，仅为维护双向链表重写了部分方法。

TreeMap实现

2.21请介绍TreeMap的底层原理

•  红黑树实现。根据键的自然顺序或者提供的Comparator排序
• root是根节点。Entry类型节点根据根据Key排序，包含的内容是value。key比较大小是根据comparator进行判断的。size是节点个数。
• TreeMap的基本操作 时间复杂度是log(N)。

2.27谈谈CopyOnWriteArrayList的原理

• 线程安全且读操作无锁的ArrayList。
• 在写操作时会复制一份新的List，在新的List上完成写操作，然后再将原引用指向新的List。这样就保证了写操作的线程安全。。
• 优点:读操作性能很高，迭代器遍历不会抛出ConcurrentModificationException异常了。
• 缺点:一是内存占用高，写操作复制原容器 ，二是无法保证实时性，写操作执行时读取的老数据

HashSet实现

2.29说一说HashSet的底层结构

• 基于HashMap实现的，默认构造函数是构建一个初始容量为16，负载因子为0.75的HashMap。它封装了一个HashMap 对象来存储所有的集合元素，所有放入 HashSet中的集合元素实际上由HashMap 的 key来保存，而HashMap 的 value 则存储了一个PRESENT，它是一个静态的Object对象。

面试题

集合是什么

• 存放对象的容器
• 存放的是引用
• 存放不同类型，不限数量的数据。

1.7,1.8 HashMap的区别?

• 1.7 数组+链表实现，同一hash值在一个链表，hash值相等的较多,查找效率低.O(n)
• 1.8，长度超过8，链表转为红黑树,O(logn)

拉链法(链地址法)：

• 数组+链表实现，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

 扩容

• 扩容:重新分配更大的内存,数据复制到新内存。
• 加载因子: 长度超过(容量*加载因子)扩容
• 初始容量 ，ArrayList 10; HashMap,16
• 加载因子，ArrayList 无(1)； HashMap,0.75
• 扩容增量： ArrayList为1.5 ,HashMap为2， 

HashMap的扩容机制

• 初始容量为16，容量以2的次方扩充 (1 更大的数组，2 位运算)
• 是否需要扩充通过负载因子判断，默认为0.75
• 解决碰撞，链表长度到达阈值时(7或8)，转换成红黑树。缩小到另一个阈值时(6),转换回单向链表。
• 数组到达阈值（64)才会转换红黑树。

HashMap1.8 优化，扩容后不需要重新计算hash值

• 使用 元素原hash码，与原始长度（例如8）进行 &(按位与) 运算，
• 第一位为0，放在原索引 的位置上
• 第一位不为0，放在 【原索引+原长度】

  HashMap中 循环链表 的产生 ?

• 1.8之前采用头插法，多线程环境下，同时进行put操作，同时进行扩容时，会出现链表环，导致死循环，新加入的冲突元素将会插到原有链表的头部。
• 1.8采用尾插法解决头插法造成的死循环，也会出现死循环(链表转换为树，对树进行操作时)

解决哈希冲突，碰撞

• 链表长度到达阈值时(7或8)，转换成红黑树。缩小到另一个阈值时(6),转换回单向链表。

HashMap和 ConcurrentHashMap 的区别

• hashmap 线程不安全， 多线程下，put会形成环导致死循环
• CoucurrentHashMap 线程安全，1.7分段锁,减少锁的粒度。1.8 CAS+Synchronized

ConcurrentHashMap

• 不能存储null键和值
• 线程安全

ConcurrentHashMap 实现原理

• 底层是数组+链表+红黑树
• 1.7分段锁,减少锁的粒度。1.8 CAS+Synchronized

ConcurrentHashMap 1.8为何又放弃分段锁

• 多个分段锁浪费内存空间，竞争同一个锁的概率小，反而造成效率低。

2.22 Map和Set有什么区别?

• Set代表无序的，元素不可重复的集合;
• Map代表具有映射关系(key-value)的集合，其所有的key是一个Set集合，即key无序且不能重复。

2.23 List和Set有什么区别?

• Set代表无序的，元素不可重复的集合;
• List代表有序的，元素可以重复的集合。

2.24 ArrayList和LinkedList有什么区别

• 1.ArrayList基于数组，LinkedList基于双向链表;
• 2.对于随机访问，ArrayList要优于LinkedList,ArrayList根据下标以O(1)时间复杂度对元素进行随机访问，而LinkedList的每一个元素都依靠地址指针和它后一个元素连接在一起，查找某个元素的时间复杂度是O(N);
• 3.对于插入和删除操作，LinkedList要优于ArrayList，因为当元素被添加到LinkedList任意位置的时候，不需要像ArrayList那样重新计算大小或者是更新索引;
• 4.LinkedList比ArrayList更占内存，因为 LinkedList的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。 

2.25有哪些线程安全的List?

• 1.Vector 效率低 
• 2.Collections.SynchronizedList，方法带有同步锁，  效率低 
• 3.CopyOnWriteArrayList  复制数组，对新数组读写

2.28说一说TreeSet和HashSet的区别

• 都是不能重复的，线程不安全
• HashSet 可空，不保证排序，哈希表失效
• TreeSet  不可空，自然排序，定制排序。红黑树实现

Java集合面试题（总结最全面的面试题）_普通网友的博客-CSDN博客_java集合类面试题

50道Java集合经典面试题（收藏版）_13284304的技术博客_51CTO博客

全网最全的Java岗集合面试题（含答案） - 哔哩哔哩

java集合面试题_jit-xly的博客-CSDN博客_java集合面试

java集合面试题 - kylinwms - 博客园

重点

50道Java集合经典面试题（收藏版）_13284304的技术博客_51CTO博客