【一些面经】Java集合

【一些面经】Java集合,第1张

【一些面经】Java集合 1.ArrayList

存储的元素是有序的,可重复,线程不安全。

底层使用Object数组存储数据,适用于频繁的查找工作。

支持高效的随机元素访问(快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法))。

插入/删除时间受元素位置影响。

比如:

  • add(e) 默认插入到数组末尾
  • add(index, e) 需要将index及index后的元素往后移一位
  • remove(e) 底层循环通过元素的equals方法判断元素是否相同,将移除元素后面的元素往前移一位
  • remove(index) 移除索引位上的元素,并将后面的元素往前移一位

空间浪费体现在 list 列表的结尾会预留一定的容量空间。

2. ArrayList扩容

无参方法构建ArrayList时,实际上初始化的是一个空数组,当进行元素添加 *** 作时,才真正分配容量,扩容长度为10(JDK6 无参初始化时,直接创建了长度为10 的数组)。

扩容长度一般为当前长度的1.5倍。

3.linkedList

存储的元素是有序的,可重复,线程不安全。

底层使用双向链表(JDK1.6之前使用的双向循环链表, JDK1.7取消循环)。

不支持高效的随机元素访问。

插入/删除受元素位置影响(区别于ArrayList):

  • add(e)/addFirst(e)/addLast(e)/removeFirst(e)/removeLast(e) 时间复杂度类似于ArrayList的add(e)
  • add(index, e) 需要将元素先移动至指定位置再进行插入,当数组长度很长的时候,index越靠近数据长度中部,插入速度越慢
  • remove() -> removeFirst() 无参方法会直接删除链表的头结点
  • remove(e) -> 遍历链表,如果传入null,当节点为null时删除节点,传入对象时 通过对象的equals方法判断判断是否相同,相同则删除节点
  • remove(index) -> 通过checkElementIndex(index) 判断节点是否存在 如果存在则删除节点

空间浪费体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继(next)和直接前驱(prev)以及数据(data))。

4.Vector

存储的元素是有序的,可重复,线程安全。

底层使用Object数组存储数据。

5.List各个集合的区别

底层实现

数据是否可重复

是否线程安全

数据是否有序

ArrayList

Object数组

可重复

有序

linkedList

双向链表(JDK1.6前为循环双向链表)

可重复

有序

Vector

Object数组

可重复

有序

6.HashSet

存储的元素是无序的,不可重复,不是线程安全的。

基于HashMap实现,底层数据结构是哈希表(基于 HashMap 实现)。

用于不需要保证元素插入和取出顺序的场景。

7.linkedHashSet

存储的元素是有序的,不可重复,不是线程安全的。

基于linkedHashMap实现,底层数据结构采用链表+哈希表(基于linkedHashMap实现)。

用于保证元素的插入和取出顺序。

8.TreeSet

存储的元素是有序的,不可重复,不是线程安全的。

底层数据结构采用红黑树。

用于支持对元素自定义排序规则的场景。

9.SET各个集合的区别

底层实现

数据是否可重复

是否线程安全

数据是否有序

HashSet

基于HashMap

不可重复

无序

linkedHashSet

基于linkedHashMap

不可重复

有序

TreeSet

红黑树

不可重复

有序

10.HashMap

HashMap是无序的,用于存储数据,key不可重复(key可为NULL,但是只能存在一个),value可以重复(可以为NULL,多个),线程不安全。

底层采用数组+链表+红黑树

  1. 为什么使用链表:
    链表主要为了解决哈希冲突而存在的(“拉链法”解决冲突)。
  2. 为什么使用红黑树:
    同一hash值的数据都存储在一个链表里。但是当位于一个桶中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。所以将链表转换为红黑树,这样大大减少了查找时间
  3. 链表多久转换为红黑树:
    链表在达到阈值(默认为8),将链表转化为红黑树,以减少搜索时间(链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)
  4. 红黑树多久转换为链表:
    红黑树元素小于6时会转换为链表
  5. hash值计算:
    HashMap通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值 ,然后通过 (n - 1) & hash 判断当前元素存放的位置(这里的 n 指的是数组的长度)
  6. HashMap初始化/扩容:
    HashMap默认初始化大小为16,每次扩容会将其扩充为 2 的幂次方大小
  7. 为什么不用B+树来替换红黑树:
    树看重两个性能 插入和查找。插入时有可能要调整树的结构 重新平衡树,B+树 调整树的结构慢一些,所以B+树插入慢,查找快;红黑树插入快 ,查找慢。
11.HashMap遍历方式及性能分析

遍历方式:

  • 迭代器(Iterator)方式遍历
  • For Each 方式遍历
  • Lambda 表达式遍历(JDK 1.8+)
  • Streams API 遍历(JDK 1.8+)

entrySet > Streams > keySet > lambda

entrySet 的性能比 keySet 的性能高出了一倍之多,因为 KeySet 相当于循环了两遍 Map 集合,而 EntrySet 只循环了一遍。

12. linkedHashMap

linkedHashMap是有序的,用于存储数据,key不可重复(key可为NULL,但是只能存在一个),value可以重复(可以为NULL,多个),线程不安全。

底层在HashMap的基础上加了一条双向链表,使得上面的结构可以保持键值对的插入顺序。

13.HashTable

HashTable是无序的,用于存储数据,key不可重复(key不为NULL),value可以重复(value不为NULL),线程安全(内部方法基本上经过synchronized修饰),Hashtable 基本被淘汰,不要在代码中使用它。

HashTable底层使用数组+链表结构存储数据

Hashtable默认初始化大小为11,如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小

HashTable锁原理:

Hashtable使用同一把锁 :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。

14.ConcurrentHashMap

ConcurrentHashMap是无序的,用于存储数据,key不可重复(key可为NULL,但是只能存在一个),value可以重复(可以为NULL,多个),线程安全。

底层数据结构:

  • JDK1.7以前:
            数据结构采用分段的数组(segment)+链表
  • JDK1.8:
            数据结构采用Node数组+链表+红黑树,Node 只能用于链表的情况,红黑树的情况需要使用 TreeNode

锁机制:

  • JDK1.7以前:
            锁机制采用的分段锁
            分段锁:对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。
  • JDK1.8:
            锁机制采用synchronized 和 CAS
            只锁定当前链表或红黑树的首节点,这样只要 hash 不冲突,就不会产生并发,效率又提升 N 倍。
 15.MAP各个集合的区别

底层实现

key是否可重复

key是否可以为NULL

value是否可重复

value是否可以为NULL

是否线程安全

数据是否有序

HashMap

数组+链表+红黑树

不可重复

可以,只能存在一个

可重复

可以存在多个NULL

无序

linkedHashMap

数组+链表+红黑树+双向链表

不可重复

可以,只能存在一个

可重复

可以存在多个NULL

有序

HashTable

数组+链表

不可重复

不可以

可重复

不可为NULL

无序

ConcurrentHashMap

数组+链表+红黑树

不可重复

可以,只能存在一个

可重复

可以存在多个NULL

无序

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5606493.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-15
下一篇 2022-12-15

发表评论

登录后才能评论

评论列表(0条)

保存