后端 | Java 常用容器知识速成

本贴最后更新于 1225 天前,其中的信息可能已经时过境迁

一.继承关系

1.1 基于 Collection

Iterable 接口: 迭代器(负责迭代元素,用于遍历元素)
Collection 接口: 集合(常用的方法有添加,全部添加,删除,清空集合,是否存在,集合个数等)
List 接口: 列表 (list 提供比数组更丰富的 API,有序,可重复,)
Queue 接口: 队列(遵循先进先出原则,第一个进队列的元素,必定第一个出队列)
Set 接口: Set 集合(不允许出现重复元素,并且无序的集合)

容器继承关系图

1.2 不属于 Collection

Map 接口: 散列表(使用 K-V(键值对)存储的一种数据结构,Key 是无序的、不可重复的,value 是无序的、可重复的)不属于 Collection 接口

Java Map Hierarchy

二.List

2.1 ArrayList

底层实现: Objcet[] (动态数组)

扩容方式: 当原本 ArrayList 的底层的数组容量不足以存放新插入的元素或一组元素时,会触发扩容机制,调用的本地 C 方法。

线程安全性: 不安全
补充:如果要安全的调用 ArrayList,使用 Collections.synchronizedList()方法。其他 API 与原先无异

List<Map<String,Object>> data=Collections.synchronizedList(new ArrayList<Map<String,Object>>());

使用场景:
适合于进行大量的随机访问的情况下使用(说人话就是可以直接根据下标取值),时间复杂度 O(1)

插入与删除: 默认追加到尾部,时间复杂度 O(1)。追加或删除指定位置元素,时间复杂度 O(n-i)

补充:clear()方法可以清空当前 List 且不改动已分配的空间

2.2 LinkedList

底层实现: 双向链表

扩容方式: 正常链表的新增节点

线程安全性: 不安全
补充:如果要安全的调用,同上。其他 API 与原先无异

List<Map<String,Object>> data=Collections.synchronizedList(new LinkedList<Map<String,Object>>());

使用场景:
适合频繁的插入或者删除操作,较少的随机访问(说人话就是可以直接根据下标取值),获取元素的时间复杂度 O(n)。

插入与删除: 默认追加到尾部,时间复杂度约等于 O(1)(为啥不等于一,因为还要创建节点然后追加,而 ArrayList 直接分配好空间直接赋值就行)。追加或删除指定位置元素,时间复杂度近似 O(n)

内存空间占用:
ArrayList 的空间浪费体现在 list 列表的结尾会预留一定的容量空间
LinkedList 的空间花费主要体现在每一个元素都(存放直接后继和直接前驱以及数据) 需要消耗比 ArrayList 更多的空间。

2.3 CopyOnWriteArrayList(不常用)

底层实现: Objcet[] (动态数组)

线程安全性: 安全
补充:如何保证安全性,
读:未加锁。
写:添加或修改时元素时 使用 lock()进行加锁并复制 一份 副本,然后添加或修改,然后使用新副本。

使用场景:
适合于进行大量的随机访问的情况下使用(说人话就是可以直接根据下标取值)以及读多写少的情况,不需要强一致性(不能保证即时一致性),时间复杂度 O(1)。

内存空间占用:
每一次写都需要复制一份副本。严重浪费内存。

2.4 Vector(历史遗留,古早时代的类)

底层实现: Objcet[] (动态数组)

线程安全性: 安全
补充:如何保证安全性,方法全部加了 synchronized 关键字(恶臭的历史残留。进了用这玩意的公司赶紧跑路吧,代码一定是屎山)

三.Set

3.1 HashSet

底层实现: HashMap(使用了 Key 部分)

线程安全性: 不安全

使用场景: 无序,数据去重
允许插入 Null 值

3.2 TreeSet

底层实现: TreeMap,红黑树(自平衡二叉查找树)

线程安全性: 不安全

使用场景: 有序(自然排序,key 的开头第一个字符的顺序 a-z,或者数字的大小 0-9)或自定义排序,数据去重
允许插入 Null 值

注意:要安全调用非线程安全的 Set。调用 Collections.synchronizedSet()

四.Map

4.1 HashMap

底层实现: 哈希表(又称散列表,使用杂凑算法),当链表(存放相同 Hash 值的 Value)长度大于阈值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64(存 Key),那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间。

线程安全性: 不安全

扩容机制:
源码规定了默认扩容加载因子为 0.75

面试官:为什么是 0.75?
如果是 0.5,就是说哈希表填到一半就开始扩容了,这样会导致扩容频繁,并且空间利用率比较低。 如果是 1,就是说哈希表完全填满才开始扩容,这样虽然空间利用提高了,但是哈希冲突机会却大了。
负载因子 0.75 就是冲突的机会 与空间利用率权衡的最后体现,也是实验的经验值。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

使用场景: 需要根据键的 hashCode 值进行存储数据。无序,获取元素的时间复杂度限制为 O(1)的时候。
Key 与 Value 可为 null

内存空间占用:

① 默认的初始化大小为 16。之后每次扩充,容量变为原来的 2 倍。
面试官为什么是 16?
如果太小,4 或者 8,扩容比较频繁;如果太大,32 或者 64 甚至太大,又占用内存空间。
位运算更快,不需十进制和二进制相互转换。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

② 创建时如果给定了容量初始值 HashMap 会将其扩充为 2 的幂次方大小,也就是说 HashMap 总是使用 2 的幂作为哈希表的大小。

简单的杂凑算法演示: 设对 7 求膜,
新增 key:6 ,value:"随便"

6%7=6

数组 数组 0 数组 1 数组 2 数组 3 数组 4 数组 5 数组 6 数组 7 数组 8 数组 9
Key null null null null null null 6 null null null
Value null null null null null null "随便" null null null

新增 key:7 ,value:"第二次"

7%7=0

数组 数组 0 数组 1 数组 2 数组 3 数组 4 数组 5 数组 6 数组 7 数组 8 数组 9
Key 7 null null null null null 6 null null null
Value "第二次" null null null null null "随便" null null null

解决 Hash 冲突: 拉链法(以链表的形式存放相同 Hash 值的 Value),上文的红黑树也可。但是拉链法较简单。

4.2 TreeMap

底层实现: 红黑树

线程安全性: 不安全

使用场景: 有序(自然排序,key 的开头第一个字符的顺序 a-z,或者数字的大小 0-9)或自定义排序。
Key 与 Value 可为 null

注意:要安全调用非线程安全的 Map。调用 Collections.synchronizedMap()

4.3 ConcurrentHashMap(建议使用)

底层实现: 数组 + 链表/红黑二叉树(JDK1.8)在链表长度超过一定阈值(8)时将链表(寻址时间复杂度为 O(N))转换为红黑树(寻址时间复杂度为 O(log(N)))

线程安全性: 安全

保证线程安全的方法:用 Node 数组 + 链表 + 红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。
java8concurrenthashmap.png

效率问题:
synchronized 只锁定当前链表或红黑二叉树的首节点,这样只要 hash 不冲突,就不会产生并发,效率又提升 N 倍。

4.4 Hashtabel(古早的线程安全类)

如何保证安全性,方法全部加了 synchronized 关键字(恶臭的历史残留。进了用这玩意的公司赶紧跑路吧,代码一定是屎山)

资料参考

JavaGuide:https://snailclimb.gitee.io/javaguide
CSDN:https://blog.csdn.net

  • 后端
    44 引用 • 126 回帖 • 1 关注
  • 程序员

    程序员是从事程序开发、程序维护的专业人员。

    570 引用 • 3533 回帖
  • 笔记

    好记性不如烂笔头。

    308 引用 • 793 回帖
  • 面试

    面试造航母,上班拧螺丝。多面试,少加班。

    325 引用 • 1395 回帖
1 操作
z875479694h 在 2021-07-30 18:39:32 更新了该帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...