java集合框架总结
一 java 集合框架图
文章图片
image.png 二 List
2.1 ArrayList
底层数据结构:线性表(数组)
线程安全:否
核心字段:
字段名 | 类型 | 作用 | 备注 |
---|---|---|---|
elementData | Object[] | 保存数据 | - |
size | int | 长度 | - |
modCount | int | 被修改的次数 | - |
若带有容量参数,则使用此容量来初始化elementData,否则把elementData置为空数组
扩容方式:
- 初始容量大小:如果有容量参数,则使用指定初始容量大小,如果无容量参数,则在第一次添加时扩容为。
- 扩容机制:新容量 = 旧容量 * 1.5 即 newCapacity = oldCapaCity + (oldCapacity >> 1)
使用迭代器循遍历ArrayList时,用于检测是否在迭代过程中被修改,即检测ConcurrentModificationException。
- 在ArrayList的所有修改方法中,modCount都会被加1
- 创建迭代器时,会把当前的modCount保存在迭代器的expectedModCount字段中
- 每次迭代时,都会检测迭代器中expectedModCount与modCount是否相等
- 在迭代器中的remove方法中,会在删除元素之后再同步一次modCount
private static class Node {
E item;
Node next;
Node prev;
}
线程安全:否
核心字段:
字段名 | 类型 | 作用 | 备注 |
---|---|---|---|
size | int | 长度 | - |
first | Node | 头节点 | - |
last | Node | 尾节点 | - |
- LinkedList的初始化没有任何操作
- 只有一个节点时,first和last都指向这一个节点
- 如果LinkedList存在多个相同的节点,使用remove(Object o) 方法移除元素时,只会移除第一个
底层数据结构:线性表
线程安全:是
初始化:
默认初始化容量为10,也可以指定大小。
扩容:
初始化时可指定每次扩容增加的容量数,如果没有指定,则每次都翻倍
线程安全方式:
为每个方法都加上synchronized关键字
三 Map 3.1 HashMap 底层数据结构:桶链结构,跳表
是否线程安全:否
核心字段:
字段名 | 类型 | 作用 | 备注 |
---|---|---|---|
table | Node[] | 底层数据,即桶链 | - |
entrySet | Set |
所有的节点数据 | 与table重复,主要是为了entrySet()和values()方法 |
size | int | 数据量 | - |
threshold | int | 扩容阀值 | - |
loadFactor | float | 扩容因子 | - |
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
为什么要这么设计?因为使用hash值散列到桶时,使用的是取余数的方法,这导致hash碰撞的机率只与hashCode的后几位有关,这个函数相当于把高位的值"混"在了低位中。可以参考HashMap的hash函数为什么这么设计
怎么使用hashCode映射到数组的下标的?
首先使用上面的方式,设计出hash值
hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
然后作以下计算
index = (n - 1) & hash
n为数组长度,在HashMap中,n的值一定为2的整数次幂,所以n-1的两进制码一定是000...001111..111结构的。因此这个操作实际上是取了hash值的后面几位
扩容机制:
- 扩容时机:当size >= threshold 时,扩容
- 容量变量:默认值为16,如果给定了初始容量,则会使用比此容量大的最小2的整数次幂,每次扩容时翻倍
- 具体操作:数组长度翻倍,threshold = 新数组长度*loadFactor,把所有元素全部重新计算下标,放入新的数组中。
- 这是一种比较复杂的平衡树,但是又不是绝对平衡,参考30张图带你彻底理解红黑树
核心字段:
字段名 | 类型 | 作用 | 备注 |
---|---|---|---|
comparator | Comparator | 比较器,用于排序 | - |
root | Entry | 根节点 | - |
size | int | 数据长度 | - |
modCount | int | 修改次数 | - |
3.3 其他Map
- IdentityHashMap:
与HashMap的区别在于,它是使用==来判断两个key是否相同,而HashMap使用的是equals - LinkedHashMap
继续自HashMap,但是使用链表记录了插入顺序,即给每个Entry再添加了before, after参数。 - Collections.synchronizedMap
这是Collections的一个方法,用于把一个不安全的Map转成线程安全的Map,实现方法其实就是做了一层包装,把所有的线程不安全的方法都synchronized了
有三个构造方法,不同的构造方法会使用不同的HashMap:
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
可以看出如果带有dummy参数,则会使用LinkedHashMap
4.2 TreeSet 同上,只是TreeSet的一层简单包装,没有特殊逻辑。
4.3 IdentitySet 同上,包装了IdentityHashMap
4.4 LinkedHashSet 继承自HashSet,初始化时调用了父类的带有dummy参数的构造方法,在此它实际上也是LinkedHashMap的一层包装。
参考文档 【java集合框架总结】modCount的作用
HashMap的hash函数为什么这么设计
30张图带你彻底理解红黑树
推荐阅读
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- android第三方框架(五)ButterKnife
- 图书集合完毕
- 标签、语法规范、内联框架、超链接、CSS的编写位置、CSS语法、开发工具、块和内联、常用选择器、后代元素选择器、伪类、伪元素。
- 事件代理
- Java|Java OpenCV图像处理之SIFT角点检测详解
- java中如何实现重建二叉树
- 数组常用方法一
- 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题
- Java|Java基础——数组