java集合框架总结

2019-07-01 本文已影响0人清雨季

一 java 集合框架图

image.png

二 List

2.1 ArrayList

底层数据结构：线性表(数组)
线程安全：否
核心字段：

字段名	类型	作用	备注
elementData	Object[]	保存数据	-
size	int	长度	-
modCount	int	被修改的次数	-

初始化过程：
若带有容量参数，则使用此容量来初始化elementData，否则把elementData置为空数组

扩容方式：

初始容量大小：如果有容量参数，则使用指定初始容量大小，如果无容量参数，则在第一次添加时扩容为 $\color{red}{默认值10}$ 。
扩容机制：新容量 = 旧容量 * 1.5 即 newCapacity = oldCapaCity + (oldCapacity >> 1)
$\color{red}{疑惑，为什么选择10和1.5倍作为扩容机制，有什么考虑吗？}$

modCount的作用：
使用迭代器循遍历ArrayList时，用于检测是否在迭代过程中被修改，即检测ConcurrentModificationException。

在ArrayList的所有修改方法中，modCount都会被加1
创建迭代器时，会把当前的modCount保存在迭代器的expectedModCount字段中
每次迭代时，都会检测迭代器中expectedModCount与modCount是否相等
在迭代器中的remove方法中，会在删除元素之后再同步一次modCount

2.2 LinkedList

底层数据结构：双向链表

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
    }

线程安全：否
核心字段：

字段名	类型	作用	备注
size	int	长度	-
first	Node	头节点	-
last	Node	尾节点	-

LinkedList的初始化没有任何操作
只有一个节点时，first和last都指向这一个节点
如果LinkedList存在多个相同的节点，使用remove(Object o) 方法移除元素时，只会移除第一个

2.3 Vector

ArrayList的线程安全版本
底层数据结构：线性表
线程安全：是

初始化：
默认初始化容量为10，也可以指定大小。

扩容：
初始化时可指定每次扩容增加的容量数，如果没有指定，则每次都翻倍

线程安全方式：
为每个方法都加上synchronized关键字

三 Map

3.1 HashMap

底层数据结构：桶链结构，跳表
是否线程安全：否

核心字段：

字段名	类型	作用	备注
table	Node[]	底层数据，即桶链	-
entrySet	Set<Map.Entry<K,V>>	所有的节点数据	与table重复，主要是为了entrySet()和values()方法
size	int	数据量	-
threshold	int	扩容阀值	-
loadFactor	float	扩容因子	-

hash函数：

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张图带你彻底理解红黑树

3.2 TreeMap

排序Map，底层采用红黑树实现，线程不安全
核心字段：

字段名	类型	作用	备注
comparator	Comparator	比较器，用于排序	-
root	Entry	根节点	-
size	int	数据长度	-
modCount	int	修改次数	-

实现了NavigableMap，可以获取指定Key范围的数据

3.3 其他Map

IdentityHashMap:
与HashMap的区别在于，它是使用==来判断两个key是否相同，而HashMap使用的是equals
LinkedHashMap
继续自HashMap，但是使用链表记录了插入顺序，即给每个Entry再添加了before, after参数。
Collections.synchronizedMap
这是Collections的一个方法，用于把一个不安全的Map转成线程安全的Map，实现方法其实就是做了一层包装，把所有的线程不安全的方法都synchronized了

四 Set

4.1 HashSet

底层使用HashMap实现，使用HashMap的Key来保存元素，所有的事都交给了HashMap处理，HashSet自己并没有什么额外的逻辑，可以说就是单纯的一层包装。
有三个构造方法，不同的构造方法会使用不同的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的一层包装。

参考文档

modCount的作用
 HashMap的hash函数为什么这么设计
 30张图带你彻底理解红黑树