Java 中的集合类主要由 Collection
和 Map
这两个接口派生而出
Collection 接口继承体系图
Map 接口继承体系图
大部分集合类都是线程不安全的(Vector
、Hashtable
除外,他俩属于历史悠久的 API 性能较差不建议使用),可以使用 Collections
工具类提供的 synchronizedXxx() 方法,将线程不安全的集合类包装成线程安全的集合类
从 Java5
开始,java.util.concurrent
包下提供了大量支持高效并发访问的集合类
- 以
Concurrent
开头的集合类支持多个线程并发写入并且保存数据线程安全,但读取数据时并不加锁。集合的实现采用了更复杂的算法来保证永远不会锁住整个集合,从而保证了在并发写入和读取时均有较好的性能- 以
CopyOnWrite
开头的集合类:当线程对此类集合执行读取操作时会直接读取集合本身(未加锁不阻塞),而当线程对此类集合执行写操作时会复制一份新的数组,接下来对新的数组执行写入操作。由于对集合的写入操作都是对数组的副本执行操作,因此也保证了是线程安全的
java.util.concurrent 包下的 Collection
java.util.concurrent 包下的 Map
类 | 适用场景 | 说明 |
---|---|---|
HashMap | 无序 | 性能最好的 Map 实现 |
ConcurrentHashMap | 无序且线程安全 | 性能优于 Hashtable,底层采用分段锁/CAS 加锁机制,只锁写不锁读 |
LinkedHashMap | 插入顺序排序 | 底层维护了双向链表使得读数据时看起来是有序的 |
TreeMap | 自定义排序 | 底层实现了 SortedMap 接口,即插入的元素是有顺序的(可定制) |
首次扩容:先判断数组是否为空,若为空则进行第一次扩容,默认初始化大小为 16
,加载因子 (loadFactor) 为 0.75
计算键的 hash 值:通过 HashMap 类的静态方法 hash(Object) 获得键的 hash 值
static final int hash(Object key) {
int h;
// 【key 的 hashCode】 与 【key 的 hashCode 无符号右移 16 位的值】做 按位异或 运算得到元素的 hash 值
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
计算元素 HashMap.Node
在散列表中的索引号:将键的 hash 值与本次哈希表大小 -1
的值进行 按位与 运算获得本次添加的元素在哈希表中的索引号
// 用本次哈希表长度减 1 与本次元素键的 hash 值进行按位与运算获得元素在哈希表中的位置号
if ((p = tab[i = (n - 1) & hash]) == null)
// 位置号上未存储元素则直接存放
tab[i] = newNode(hash, key, value, null);
在哈希表的相应位置上存放元素:
- 如果当前位置元素为空,则直接插入数据
- 如果当前位置元素非空,且 key 已存在,则直接覆盖其 value
- 如果当前位置元素非空,且 key 不存在,则将数据链到链表末端
- 若链表长度达到
8
且哈希表的长度达到64
,则将此条链表转换成红黑树,并将数据插入树中final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 第一次扩容:table 为 HashMap 的静态内部类 Node 类型的数组 transient Node
[] table; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 用本次哈希表长度减 1 与本次元素键的 hash 值进行 按位与 运算获得元素在哈希表中的位置号 if ((p = tab[i = (n - 1) & hash]) == null) // 位置号上未存储元素则直接存放 tab[i] = newNode(hash, key, value, null); // 位置号上已经存放元素,判断当前要添加的元素是否已存在相同元素 else { Node<K,V> e; K k; // 如果当前元素键的 hash 值与哈希表位置号上元素键的 hash 值相同且引用相同或者要添加的元素键不为空且与当前位置上元素的键 equals 比较相同,则推出添加的元素与当前位置号上的元素相同 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 判断当前位置号是否是红黑树数据结构,是则按照红黑树方式添加 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 遍历此位置号上的链表元素,判断是否与当前需要加入的元素相同 for (int binCount = 0; ; ++binCount) { // 不相同,添加到链表尾 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 判断该条链表上的元素个数是否 >= 8个,是则进行树化条件判断 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 如果存在相同的元素则不添加 if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 当前要添加的元素已存在,则不添加,返回旧值 value(新旧交替) if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // size 为哈希表中的元素个数,判断加入的元素个数是否不小于临界值,是则对哈希表进行扩容 if (++size > threshold) resize(); // HashMap 的空方法,留给子类实现以扩展功能 afterNodeInsertion(evict); // 返回 null 代表元素添加成功 return null; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
再次扩容判断:如果数组中元素个数超过临界值 threshold = 当前散列表长度 * 加载因子(loadFactor)
,则进行扩容操作,按 2
倍方式进行扩容
扩展:JDK7 HashMap 的 put 过程
public V put(K key, V value) {
// 校验 key 是否为空
if (key == null)
return putForNullKey(value);
// 获取 key 对应的 hash 值
int hash = hash(key);
// 计算元素在散列表中的索引号
int i = indexFor(hash, table.length);
// 判断散列表该位置上新添加元素的键是否存在,存在则用新 value 替换旧 value 并返回旧 value
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 修改次数+1
modCount++;
// 使用头插法插入当前元素
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
// 判断是否需要扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
// 扩容后,对应的 hash 需要重新计算
hash = (null != key) ? hash(key) : 0;
// 扩容后,对应的 bucketIndex 需要重新计算
bucketIndex = indexFor(hash, table.length);
}
// 插入元素数据
createEntry(hash, key, value, bucketIndex);
}
Collections
工具类将线程不安全的 Map 包装成线程安全的 Mapjava.util.concurrent
包下的 Map 如 ConcurrentHashMap
HashMap 是线程不安全的 Map
HashMap 可以使用 null 作为 key 或 value
map.put(null, null);
map.put("Spring-_-Bear", null);
HashMap 默认初始化大小为 16
,加载因子为 0.75
,按 2
倍方式扩容
当哈希表的大小 >= 64
且某条链表的长度 >= 8
则将该条链表树化为红黑树
HashMap.Entry
。使用头插法插入元素,链表过长时查询效率较低,时间复杂度为 O(n)
HashMap.Node
。使用尾插法插入元素,当散列表长度不小于 64
且某条链表长度不小于 8
时就将该条链表转换为红黑树(条件不满足时又会剪枝为链表),红黑树的查询效率为 O(logN)
以经典 JDK8 的实现为例:
底层使用数组 + 链表 + 红黑树,数组类型是 HashMap.Node
基于 hash 算法和散列表长度计算当前键 K 在散列表中的位置
// 1. 【key 的 hashCode】 与 【key 的 hashCode 无符号右移 16 位的值】做 按位异或 运算得到元素的 hash 值
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
// 2. 用本次哈希表长度减 1 与本次元素键的 hash 值进行按位与运算获得元素在哈希表中的位置号
if ((p = tab[i = (n - 1) & hash]) == null)
散列表该位置不存在元素则直接存放,存在则判断是否存在相同键的元素,存在则用新值替换旧值并返回旧值
// 如果当前元素键的 hash 值与哈希表位置号上元素键的 hash 值相同且引用相同或者要添加的元素键不为空且与当前位置上元素的键 equals 比较相同,则推出添加的元素与当前位置号上的元素相同
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
元素键不重复则判断是树结构还是链表结构,分别添加元素到链表尾或树中(树化判断:散列表长度不小于 64 且链表长度不小于 8)
扩容判断,当散列表数组已使用元素个数大于临界值 = 散列表长度 * 0.75
时按 2 倍方式扩容
初始化容量大小为 16,当数组已使用元素个数大于临界值 = 散列表长度 * 加载因子(0.75)时按 2 倍方式进行扩容(使用 2 倍扩容机制的原因是为了方便进行位运算,提高效率)
初始化大小和加载因子均可由构造器指定,当红黑树节点个数小于 6
时将剪枝为链表
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
HashMap 是线程不安全的实现,当 2 个以上线程同时尝试扩大 HashMap 的容量,原散列表中一条链表上的所有节点加入到扩容后的新数组中时,它们最多将会分布在新数组中的两条链表上
JDK7 采用的是头插法将链表上的元素迁移到新数组中,会产生环形链表和数据丢失
JDK8 做出的优化使用尾插法插入链表元素虽然不会产生环形链表但仍然存在数据覆盖的问题
B/B+
树多用于外存上时,被视为磁盘友好的数据结构B/B+
树的话,在数据量不是很多的情况下,数据都会 “挤在” 一个结点里,这个时候遍历效率就退化成了链表java.util.concurrent.ConcurrentHashMap
(首选)Collections
工具类将 HashMap 包装成线程安全的 MapHashtable
为了解决碰撞,数组中的元素是单向链表类型。当链表长度达到 8 且数组长度达到 64 时,会将链表转换成红黑树提高性能。而当链表长度缩小到 6 时,又会将红黑树转换回单向链表提高性能
Collections
工具类将 HashMap 包装为线程安全的 Map 使用的是 synchronized
互斥锁的方式,性能与吞吐量较低(Hashtable 也基于 synchronized),允许使用 null 作为键和值ConcurrentHashMap
底层采用分段锁/CAS
加锁机制,只锁多线程的写操作而不锁读操作,因而效率较高,不允许使用 null 作为键和值JDK1.7 中的实现:
在 jdk1.7 中,ConcurrentHashMap 是由 Segment
数据结构和 HashEntry
数组结构构成,采取分段锁来保证安全性。Segment 是 ReentrantLock
重入锁,在 ConcurrentHashMap 中扮演锁的角色,HashEntry 则用于存储键值对数据
一个 ConcurrentHashMap 里包含一个 Segment 数组,一个 Segment 里包含一个 HashEntry 数组,Segment 的结构和 HashMap 类似,是一个数组和链表结构
JDK1.8 中的实现:
JDK1.8 的实现已经摒弃了 Segment 的概念,而是直接用 Node 数组 + 链表 + 红黑树
的数据结构来实现,并发控制使用 synchronized
和 CAS
来操作,整个看起来就像是优化过且线程安全的 HashMap,虽然在 JDK1.8 中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本
get 操作:Segment 的 get 操作实现非常简单和高效,先经过一次再散列,然后使用这个散列值通过散列运算定位到 Segment,再通过散列算法定位到元素。get 操作的高效之处在于整个 get 过程都不需要加锁,除非读到空的值才会加锁重读。原因就是将使用的共享变量定义成 volatile 类型
put 操作:当执行 put 操作时,会经历两个步骤:
插入过程会进行第一次 key 的 hash 来定位 Segment 的位置,如果该 Segment 还没有初始化,即通过 CAS 操作进行赋值,然后进行第二次 hash 操作,找到相应的 HashEntry 的位置,这里会利用继承过来的锁的特性,在将数据插入指定的 HashEntry 位置时(尾插法),会通过继承 ReentrantLock
的 tryLock()
方法尝试去获取锁,如果获取成功就直接插入相应的位置,如果已经有线程获取该Segment 的锁,那当前线程会以自旋的方式去继续的调用 tryLock() 方法去获取锁,超过指定次数就挂起,等待唤醒
LinkedHashMap 底层维护了一个数组 + 双向链表,数组的类型是 HashMap$Node[]
,其中存放的元素是 LinkedHashMap$Entry
类型,在 HashMap 的数据结构基础之上,增加了一个双向链表用来记录元素的添加顺序,使得元素看起来是以插入顺序保存的
LinkedHashMap 需要维护元素的插入顺序,因此性能略低于 HashMap。但因为它以链表来维护内部顺序,所以在迭代访问 Map 里的全部元素时将有较好的性能
LinkedHashMap 继承于 HashMap,它在 HashMap 的基础上,通过维护一条双向链表解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。在实现上,LinkedHashMap 很多方法直接继承自 HashMap,仅为维护双向链表重写了部分方法
TreeMap 基于红黑树(Red-Black tree)实现。映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator
进行排序,具体取决于使用的构造方法
TreeMap 的基本操作 containsKey、get、put、remove 方法,它的时间复杂度是O(logN)
TreeMap 包含几个重要的成员变量:root、size、comparator。root 是红黑树 Entry
类型的根节点,size 是红黑树的节点个数,comparator 是比较器对象
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
Set 代表无序的,元素不可重复的集合
Map 代表具有映射关系(key-value)的集合,其所有的 key 是一个 Set 集合,即 key 无序且不能重复
Set代表无序的,元素不可重复的集合
List代表有序的,元素可以重复的集合
Java1.5
在 java.util.concurrent 包下增加的类,底层采用复制数组的方式来实现写操作。
ArrayList 的底层是用对象数组来实现的 transient Object[] elementData;
若创建对象时使用无参构造器,则初始容量为 0,第 1 次添加后容量设置为 10
,此后按照 elementData 容量的 1.5
倍进行扩容
若创建对象时指定了容量,则 elementData 的初始容量为指定大小,需要扩容时按照 1.5 进行扩容
扩容时以 System.arraycopy()
将原数组中的元素复制到新的数组中
CopyOnWriteArrayList 是 Java5 在 java.util.concurrent
并发包里提供的并发类,简单来说它就是一个线程安全且读操作无锁的 ArrayList。正如其名字一样,在写操作时会复制一份新的 List,在新的List上完成写操作,然后再将原引用指向新的List。这样就保证了写操作的线程安全
优点:读操作性能很高,因为无需任何同步措施,比较适用于读多写少的并发场景。在遍历传统的 List 时,若中途有别的线程对其进行修改,则会抛出 ConcurrentModificationException
异常。而 CopyOnWriteArrayList 由于其 “读写分离” 的思想,遍历和修改操作分别作用在不同的 List 容器,所以在使用迭代器进行遍历时候,也就不会抛出 ConcurrentModificationException 异常了
缺点:一是内存占用问题,毕竟每次执行写操作都要将原容器拷贝一份,数据量大时,对内存压力较大,可能会引起频繁 GC。
二是无法保证实时性,Vector
对于读写操作均加锁同步,可以保证读和写的强一致性。而 CopyOnWriteArrayList 由于其实现策略的原因,写和读分别作用在新老不同容器上,在写操作执行过程中,读不会阻塞但读取到的却是老容器的数据
HashSet、TreeSet 都是不能重复的且线程不安全的集合,二者的区别是:
HashSet 中的元素可以是 null,但 TreeSet 中的元素不能是 null
HashSet<Integer> hashSet = new HashSet<>();
hashSet.add(null);
TreeSet<Integer> treeSet = new TreeSet<>();
// java.lang.NullPointerException
treeSet.add(null);
HashSet 不能保证元素的排列顺序,而 TreeSet 支持自然排序、定制排序两种排序的方式
HashSet 底层是采用哈希表实现的,而 TreeSet 底层是采用红黑树实现的
HashSet 的底层是基于 HashMap 实现的,只是 HashMap 中的 value 存储的是固定对象 PRESENT
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
为了应对不同的业务场景,BlockingQueue 提供了 4
组不同的方法用于插入、移除以及对队列中的元素进行检查
操作 | 抛异常 | 特定值 | 阻塞 | 超时 |
---|---|---|---|---|
插入 | add(e) | offer(e) | put(e) | offer(e, time, unit) |
移除 | remove() | poll() | take() | poll(time, unit) |
检查 | element() | peek() |
BlockingQueue 接口的继承体系图及常用实现类,各实现类的区别主要体现在存储结构或元素操作上,但 put 与 take 操作的原理类似
以 ArrayBlockingQueue 为例分析 BlockingQueue 的实现原理:
/**
* Creates an {@code ArrayBlockingQueue} with the given (fixed)
* capacity and the specified access policy.
*
* @param capacity the capacity of this queue
* @param fair if {@code true} then queue accesses for threads blocked
* on insertion or removal, are processed in FIFO order;
* if {@code false} the access order is unspecified.
* @throws IllegalArgumentException if {@code capacity < 1}
*/
public ArrayBlockingQueue(int capacity, boolean fair) {
if (capacity <= 0) throw new IllegalArgumentException();
this.items = new Object[capacity];
// 初始化 put 和 take 函数中用到的关键成员变量,ReentrantLock是 AbstractQueuedSynchronizer(AQS)的子类,它的 newCondition 函数返回的 Condition 实例,是定义在 AQS 类内部的 ConditionObject 类,该类可以直接调用 AQS 相关的函数
lock = new ReentrantLock(fair);
notEmpty = lock.newCondition();
notFull = lock.newCondition();
}
put 函数会在队列尾添加元素,如果队列已满无法添加元素,就一直阻塞等待到直到可以加入为止
/**
* Inserts the specified element at the tail of this queue, waiting
* for space to become available if the queue is full.
*
* @throws InterruptedException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
public void put(E e) throws InterruptedException {
checkNotNull(e);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
// 与一般生产者-消费者的实现方式不同,同步队列使用 ReentrantLock 和 Condition 相结合的机制,即先获得锁再等待,而不是 synchronized 和 wait 的机制
while (count == items.length)
notFull.await();
enqueue(e);
} finally {
lock.unlock();
}
}
再来看一下消费者调用的 take 函数,take 函数在队列为空时会被阻塞,一直到阻塞队列加入了新的元素
public E take() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (count == 0)
notEmpty.await();
return dequeue();
} finally {
lock.unlock();
}
}
扩展阅读之 await 操作:
Object.wait
,而是使用的 Condition.await
,这是为什么呢?Condition 对象可以提供和 Object 的 wait 和 notify 一样的行为,但是后者必须先获取 synchronized 这个内置的 monitor 锁才能调用,而 Condition 则必须先获取 ReentrantLock。这两种方式在阻塞等待时都会将相应的锁释放掉,但是 Condition 的等待可以中断,这是二者唯一的区别扩展阅读之 signal 操作:
signal 函数将 condition wait queue 队列中队首的线程节点转移等待获取锁的 sync queue 队列中。这样的话,await 函数中调用 isOnSyncQueue 函数就会返回 true,导致 awai t函数进入最后一步重新获取锁的状态
我们这里来详细解析一下 condition wait queue 和 sync queue 两个队列的设计原理。condition wait queue 是等待消息的队列,因为阻塞队列为空而进入阻塞状态的 take 函数操作就是在等待阻塞队列不为空的消息。而 sync queue 队列则是等待获取锁的队列,take 函数获得了消息,就可以运行了,但是它还必须等待获取锁之后才能真正进行运行状态
signal 函数其实就做了一件事情,就是不断尝试调用 transferForSignal 函数,将 condition wait queue 队首的一个节点转移到 sync queue 队列中,直到转移成功。因为一次转移成功,就代表这个消息被成功通知到了等待消息的节点
Stream 提供了大量的方法进行聚集操作,这些方法既可以是 “中间的”,也可以是 “末端的”
除此之外,关于流的方法还有如下两个特征:
Stream 常用的中间方法:
方法 | 说明 |
---|---|
filter(Predicate predicate) | 过滤 Stream 中所有不符合 predicate 的元素 |
mapToXxx(ToXxxFunction mapper) | 使用 ToXxxFunction 对流中的元素执行一对一的转换,该方法返回的新流中包含了 ToXxxFunction 转换生成的所有元素 |
peek(Consumer action) | 依次对每个元素执行一些操作,该方法返回的流与原有流包含相同的元素。该方法主要用于调试 |
distinct() | 该方法用于排除流中所有重复的元素(判断元素重复的标准是使用 equals() 比较)。这是一个有状态的方法 |
sorted() | 该方法用于保证流中的元素在后续的访问中处于有序状态。这是一个有状态的方法。 |
limit(long maxSize) | 该方法用于保证对该流的后续访问中最大允许访问的元素个数。这是一个有状态的、短路方法 |
Stream 常用的末端方法:
方法 | 说明 |
---|---|
forEach(Consumer action) | 遍历流中所有元素,对每个元素执行 action |
toArray() | 将流中所有元素转换为一个数组 |
reduce() | 该方法有三个重载的版本,都用于通过某种操作来合并流中的元素 |
min() | 返回流中所有元素的最小值 |
max() | 返回流中所有元素的最大值 |
count() | 返回流中所有元素的数量 |
anyMatch(Predicate predicate) | 判断流中是否至少包含一个元素符合 Predicate 条件 |
noneMatch(Predicate predicate) | 判断流中是否所有元素都不符合 Predicate 条件 |
findFirst() | 返回流中的第一个元素 |
findAny() | 返回流中的任意一个元素 |
除此之外,Java8 允许使用流式 API 来操作集合,Collection 接口提供了一个 stream()
默认方法,该方法可返回该集合对应的流,接下来即可通过流式 API 来操作集合元素。由于 Stream 可以对集合元素进行整体的聚集操作,因此 Stream 极大地丰富了集合的功能
扩展阅读之 Java8 中的流式 API:
Java8 新增了 Stream、IntStream、LongStream、DoubleStream 等流式 API,这些 API 代表多个支持串行和并行聚集操作的元素。Stream 是一个通用的流接口,而 IntStream、LongStream、DoubleStream 则代表元素类型为 int、long、double 的流
Java8 还为上面每个流式 API 提供了对应的 Builder
,例如 Stream.Builder、IntStream.Builder、LongStream.Builder、DoubleStream.Builder,开发者可以通过这些 Builder 来创建对应的流
独立使用 Stream 的步骤如下: