张红尘的博客 张红尘的博客

纵你阅人何其多,始终无人恰似我

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

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

一.继承关系

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
Keynullnullnullnullnullnull6nullnullnull
Valuenullnullnullnullnullnull"随便"nullnullnull

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

7%7=0

数组数组0数组1数组2数组3数组4数组5数组6数组7数组8数组9
Key7nullnullnullnullnull6nullnullnull
Value"第二次"nullnullnullnullnull"随便"nullnullnull

解决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


标题:后端 | Java常用容器知识速成
作者:张红尘
地址:https://www.hcworld.xyz/articles/2021/07/12/1626104283274.html