202206 集合 面试

发布于:2022-11-09 ⋅ 阅读:(14) ⋅ 点赞:(0) ⋅ 评论:(0)

实现原理

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博客