Java.util 包
大约 36 分钟
Java.util 包
1 AbstractList
先来看看 AbstractList 的继承结构:
AbstractList 是 ArrayList, LinkedList 的父类, 继承了 AbstractCollection 父类, 实现了 List 接口.
我们先来看看 AbstractList 对数据的增、删、改操作:
public boolean add(E e) {
// 加入到 list 末尾
add(size(), e);
return true;
}
// 这里的 abstract 在 public 之前, 奇奇怪怪
abstract public E get(int index);
// 会返回被添加的元素
public E set(int index, E element) {
throw new UnsupportedOperationException();
}
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
// 会返回被移出的元素
public E remove(int index) {
throw new UnsupportedOperationException();
}
抽象定义了增删改操作, 注意 add() 方法封装了一次, 将实际的实现留给子类. add() 方法在数组和链表实现的 list 中的实现方式是不同的.
List 的一大功能是迭代遍历操作, 下面我们看看 AbstractList 定义的迭代方法.
AbstractList 中有两个有关迭代器的内部类 Itr 和 ListItr, 在其中实现了自己的迭代方法. 我们先来看 Itr 类的源码:
private class Itr implements Iterator<E> {
//下一次调用 next() 要返回的元素索引
int cursor = 0;
// 最近一次调用 next() 或 previous() 返回的元素的索引
// 如果是调用 delete()方法, 就设置为 -1
int lastRet = -1;
// 迭代器认为 list 应该有的 modCount 值,
// 如果不等于这个值, 就表示迭代器检测到了并发修改.
int expectedModCount = modCount;
// 判断是否还有下一个元素, 注意在判断的过程中游标 cursor 没有移动
public boolean hasNext() {
return cursor != size();
}
// 迭代获取下一个元素, 会先检查是否存在并发修改
// 调用 get(i) 来获取下一个元素, 并且更新游标数据
public E next() {
checkForComodification();
try {
int i = cursor;
E next = get(i);
lastRet = i;
cursor = i + 1;
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
// 调用 AbstractList 中定义的 remove() 方法删除游标处的元素, 移动游标 cursor.
// 如果是从前向后遍历, 每次修改完都向前移动一次游标
// 如果是从后向前遍历, 游标不变
// 注意游标一定指向最近一次被遍历的元素
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
// 在游标处插入元素, 移动游标
public void add(E e) {
checkForComodification();
try {
int i = cursor;
AbstractList.this.add(i, e);
lastRet = -1;
cursor = i + 1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
// 检查是否存在并发修改
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
主要是通过游标 cursor 的增减来实现迭代器的左右移动. 通过 lastRet 来检测修改. 通过 expectedModCount 来检测是否存在并发修改.
这里主要说一下 expectedModCount 和 modCount 的关系:
expectedModCount是期望修改的次数,modCount是实际修改的次数.expectedModCount只被迭代器持有, 而modCount被外部对象持有并修改.- 在
Itr初始化时会将modCount的值赋给expectedModCount表示当前的操作状态和外部AbstractList的操作状态相同(没有多余的增删改操作). - 每次在迭代器
Itr中完成操作过后, 都会将外部的modCount同步到expectedModCount中 - 在涉及到增删改操作之前, 迭代器都会先检测
expectedModCount和modCount是否相同, 来保证不会发生并发修改(但是并不能保证线程安全).
还有就是 lastRet 属性的作用, 主要用于限制删除操作, 如果 lastRet < 0, 则当前状态不支持删除操作. 在合法情况下, remove() 方法会删除 lastRet 索引对应的元素.
在迭代器中的添加和删除操作都会导致 lastRet 被设置为 -1, 也就是添加/删除操作之后不能进行删除操作.
同时, 只有 next() 方法会为 lastRet 设置合法值(即当前游标所指的位置). 原因如下:
- 如果
Itr初始化后不执行next()方法, 则没有可以删除的元素. - 如果在删除/添加之后不执行
next()方法,lastRet = -1, 当前也没有可以删除的元素. - 如果添加之后可以直接删除, 那么添加就没有意义了, 所以添加之后也将
lastRet设置为-1.
看完基础的 Itr, 再来看看在 Itr 基础上进行扩展的 ListItr 类:ListItr 继承了Itr, 实现了 ListIterator 接口.
ListItr 主要提供了从前向后、从后向前的遍历方法. 并且可以从 List 中的任何一个位置开始遍历.
// 为 AbstractList#removeRange() 方法提供遍历
ListItr(int index) {
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public E previous() {
checkForComodification();
try {
int i = cursor - 1;
E previous = get(i);
lastRet = cursor = i;
return previous;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
其余便和 Itr 没有特别的差异了.
了解完迭代器, 我们来看 AbstractList 定义的子列表类 SubList:
class SubList<E> extends AbstractList<E> {
private final AbstractList<E> l;
private final int offset;
private int size;
SubList(AbstractList<E> list, int fromIndex, int toIndex) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > list.size())
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
l = list;
offset = fromIndex;
size = toIndex - fromIndex;
this.modCount = l.modCount;
}
// ...
}
从构造方法可以看出, SubList 可以理解为是 AbstractList 内容的切片(slice). 从 AbstractList 的内容中截取一部分出来进行操作. 主要需要注意几点:
SubList没有进行任何 copy 操作, 只是AbstractList的一部分(用两个指针限制操作范围而已).- 在
SubList中进行的增删改操作都会影响到父 List - 慎用
2 ArrayList
看完 AbstractList, 我们趁热打铁, 来看看它的子类 ArrayList.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
}
可以看到, ArrayList 实现了 List, RandomAccess, Cloneable, Serializable 接口.
RandomAccess是一个标志接口, 表明实现这个接口的 List 集合是支持快速随机访问的. 即在ArrayList中我们可以通过元素的序号快速访问元素对象.ArrayList实现了Cloneable接口, 重写了clone()方法, 可以被克隆.- 实现了
Serializable接口, 表示可以被序列化后传输.
然后我们直接来看核心源码:
先来看看它维护的一些属性:
private static final long serialVersionUID = 8683452581122892189L;
/**
* 默认初始容量大小为 10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空数组（用于空实例）
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**用于默认大小空实例的共享空数组实例.
* 我们把它从 EMPTY_ELEMENTDATA 数组中区分出来, 以知道在添加第一个元素时容量需要增加
* 多少.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 保存ArrayList数据的数组
*/
transient Object[] elementData;
/**
* ArrayList 所包含的元素个数
*/
private int size;
然后是它的构造方法:
// 带初始容量参数的构造函数, 可以指定创建时的初始容量
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//如果传入的参数等于0, 创建空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
// 无参构造
// DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10，也就是说初始其实是空数组
// 当添加第一个元素的时候数组容量才变成10
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 构造一个包含指定集合的元素的列表, 按照它们由集合的迭代器返回的顺序添加
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
看完构造方法, 我们来看它的元素操作方法:
// 获取数组元素的索引, 注意分了元素为 null 和非空两种情况.
// 采用遍历方式获取对应元素第一次出现的索引.
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
// 如果元素非空, 就直接使用 equals() 方法比较.
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
// 实现的 clone() 方法, 用于克隆 list.
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
// 深拷贝, 将 List 中的元素一起拷贝进新 List.
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
// 还是调用 Arrays.copyOf() 方法进行操作.
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
// 获取元素方法, 根据索引获取元素.
E elementData(int index) {
return (E) elementData[index];
}
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
// 修改元素方法, 同样通过索引修改, 会返回旧值
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
// 添加元素方法, 将元素添加到数组尾部, 添加前会前保证容量足够.
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
// 在特定索引后加入元素
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
// 移出特定索引的元素, 注意实际置空的是最后一个元素.(先调用arraycopy)
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
// 这里是移出列表中第一次出现的对应元素.
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
然后我们来到每个集合的一个关键部分, 扩容机制:
从之前的构造函数可以看出, 如果不传入参数, 默认的初始化容量为 0(空数组); 在真正添加元素时, 才真正分配容量为 10; 如果传入参数, 则初始化容量为参数对应的容量大小.
在实际执行 add() 方法, 会先调用 ensureCapacityInternal() 方法得到最小扩容量. 注意: ArrayList 的扩容因子是 0.5, 即 capacity = capacity + capacity >> 1.
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果是默认初始化的空数组, 就直接扩容到 max(10, 当前需要的最小容量)
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
// 需要的容量比当前容量大
if (minCapacity - elementData.length > 0)
//调用grow方法进行扩容，调用此方法代表已经开始扩容了
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 扩容因子: 0.5
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 检查按扩容因子扩容出的容量是否符合要求,
// 如果不够就用当前需要的最小容量作为新的容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 保证大容量扩容
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
我们发现在调用链中并没有出现 ensureCapacity() 方法, 那么它的作用是什么呢?
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
这个方法其实是提供给用户使用的, 最好在 add() 大量元素之前调用 ensureCapacity() 方法保证数组容量足够, 以减少增量重新分配的次数.
3 LinkedList
看完数组实现的 ArrayList, 我们再来看看双向链表实现的LinkedList:
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
可以看到, LinkedList 继承了 AbstractSequentialList, 实现了 List, Deque, Cloneable, Serializable接口.
实现 Deque 说明 LinkedList 具有队列的结构和功能.AbstractSequentialList 定义了一些顺序访问列表相关的方法, 实际也是通过 ListIterator 实现的.
由于 LinkedList 是由双向链表实现的, 我们先来看看它的节点对象 Node:
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
由于要实现双向链表, 所有 Node 保存了前后两个节点的引用, 提供了初始化构造方法.
扩展:
从源码中还可以看出,LinkedList是循环链表.
我们继续来看 LinkedList 的成员变量以及构造方法, 相较于 ArrayList 还是简单很多:
// 链表实际大小
transient int size = 0;
// 链表头节点
transient Node<E> first;
// 链表尾节点
transient Node<E> last;
public LinkedList() {
}
// 先构造空链表, 然后执行添加操作
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
看完成员变量和构造方法, 我们来看看 LinkedList 的核心方法 -- 元素插入操作:
// 头插法
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
// 尾插法
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
// 在某个元素之前插入
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
// 获取 index 处的节点, 如果靠近头节点就从前向后遍历, 反之从后向前遍历
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
// 删除尾节点
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
// 删除头节点
private E unlinkFirst(Node<E> f) {
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
// 删除任意节点
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
这里就是 LinkedList 的核心方法了, 其他很多插入删除操作都是调用这里的方法进行封装, 提供给不同功能的 LinkedList 使用(如: 双向链表, 队列, 栈等).
在这里做一个总结:
LinkedList是由双向链表实现的.LinkedList可以实现单向队列, 双向队列, 栈的功能.LinkedList不需要指定容量, 也没有扩容机制, 这就是使用链表实现的一个好处.LinkedList中的方法没有被Synchronized方法修饰, 是线程不安全的.
4 HashMap
HashMap 主要用于存放键值对, 是基于哈希表的 Map 实现, 非线程安全. HashMap 可以存放 null 的 key 或 value, null 作为 key 只能有一个, 但是可以有多个 value.
1.8 以前, HashMap 由数组和链表组成, 数组是 HashMap 的主体, 而链表是为了解决哈希冲突而存在的(拉链法); 1.8 以后, HashMap 增加了树的数据结构, 用于复杂扩容情况. 当链表长度大于阈值(默认为 8)(将链表转换成红黑树前会判断，如果当前数组的长度小于 4，那么会选择先进行数组扩容，而不是转换为红黑树)时，将链表转化为红黑树，以减少搜索时间.
HashMap 默认初始化容量为 16, 之后每次扩容都会变为原来的两倍. HashMap 的大小始终是 2 的整数幂.
4.1 数据结构
我们先来看看数据结构:
Java 1.8 之前, HashMap 底层由数组和链表组成, 即链表散列.HashMap 将 key 的 hashcode 经过扰动函数处理后得到 hash 值, 然后通过 (n - 1) & hash 判断当前元素存放的位置(n 为数组长度). 如果当前位置存在元素, 就判断该元素与要存入的元素的 hash 值以及 key 是否相同, 如果相同, 就直接覆盖; 如果不同, 就使用拉链法解决冲突. 扰动函数即 HashMap 的 hash() 方法, 使用扰动函数可以保证解决冲突的效率(避免使用实现比较差的 hashcode() 方法).
来看看 1.8 之前的hash()方法:
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
然后对比一下 1.8 之后的方法, 现在的方法性能高更好(只进行了一次 hash 扰动):
static final int hash(Object key) {
int h;
// key.hashCode()：返回散列值也就是hashcode
// ^ ：按位异或
// >>>:无符号右移，忽略符号位，空位都以0补齐
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1.8 之后, 解决 hash 冲突的方法也发生了变化. 当链表长度大于阈值(默认为 8)时, 会先调用 treeifyBin() 方法. 该方法会根据 HashMap 中的数组来决定是否转换为红黑树, 只有当数组长度大于或等于 64 的情况下, 才会执行转换为红黑树的操作, 来减少搜索时间. 否则, 就是只会执行 resize() 方法对数组进行扩容.
看完总体的数据结构, 我们来研究一下 HashMap 单个数据的保存方式:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
由上面的源码可以看出, HashMap 的单个元素保存在实现了 Map.Entry 接口的 Node 节点中. 节点保存了元素的 hash, key, value 以及下一个节点的引用 next. Node 重写了 hashCode() 和 equals() 方法.
4.2 源码分析
HashMap 继承了 AbstractMap, 实现了 Map, Cloneable, Serializable 接口.
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
再来看看 HashMap 的属性:
// 默认初始化容量, 必须是 2 的正整数次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量, 如果构造函数创建时制定了更大的值, 就设置为最大容量指定的值
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子, 0.75, 在构造函数未指定时使用
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的 table 的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组，总是2的幂次倍
transient Node<K,V>[] table;
// 存放具体元素的集合
transient Set<Map.Entry<K,V>> entrySet;
// 存放元素的个数，注意这个不等于数组的长度
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值(容量*填充因子) 当实际大小超过临界值时，会进行扩容
int threshold;
// 加载因子
final float loadFactor;
loadFactor- 用于控制数组存放数据的疏密程度.
loadFactor越大, 数组越密,查找效率低;loadFactor越小, 数组越稀疏, 空间利用效率低. - 0.75 是
loadFactor一个比较合理的值.
- 用于控制数组存放数据的疏密程度.
threshold- , 当数组大小超过
threshold时, 会触发数组的扩容, 扩容是一个很耗费性能的操作.
- , 当数组大小超过
下面我们看看 HashMap 的 put() 方法:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
// 延迟初始化桶数组到插入操作
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果桶中不包含新节点的引用, 就直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e;
K k;
// 如果键的值以及节点 hash 等于 链表中的第一个节点时, 将 e 指向该键值对
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果桶中引用类型为 TreeNode, 则调用红黑树的插入方法
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);
// 判断是否需要转换为红黑树
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;
}
}
// 判断要加入的键值对是否存在于链表中
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 键值对数量超过阈值时, 触发扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
putVal() 方法具体实现了 Map 接口中定义的 put() 方法. 可以看出, putVal() 方法主要有如下步骤:
- 如果没有初始化, 则初始化桶数组
- 查找要插入的节点是否已经存在
- 如果存在, 就更改旧值
- 如果不存在, 就插入链表中, 并判断链表是否需要转为红黑树
- 判断键值对数量是否大于阈值, 如果大于就扩容
put() 方法涉及了扩容的问题, 我们下面来看看:
需要注意的是: HashMap 的桶数组长度总是 2 的 n 次幂, 阈值大小为 . 如果容量超过阈值, 就会触发扩容.HashMap 的扩容方式与 ArrayList 不同, 它是将桶数组的长度扩大到两倍, 阈值也变为原来的两倍.
扩容之后需要重新计算键值对的位置, 并将它们移动到对应的位置.
来看看具体实现:
final Node<K, V>[] resize() {
Node<K, V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 如果桶数组容量大于最大容量, 就直接将阈值设置为最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 将桶数组容量以及阈值扩大到两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
/*
* 初始化时，将 threshold 的值赋值给 newCap，
* HashMap 使用 threshold 变量暂时保存 initialCapacity 参数的值
*/
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
/*
* 调用无参构造方法时，桶数组容量为默认容量，
* 阈值为默认容量与默认负载因子乘积
*/
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr 为 0 时，按阈值计算公式进行计算
if (newThr == 0) {
float ft = (float) newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 创建新的桶数组并初始化
@SuppressWarnings({"rawtypes", "unchecked"})
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
table = newTab;
if (oldTab != null) {
// 如果旧的桶数组不为空，则遍历桶数组，并将键值对映射到新的桶数组中
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
if ((e = oldTab[j]) != null) {
// 这里将原桶数组对应位置置空, 便于gc
oldTab[j] = null;
if (e.next == null)
// 如果是链表, 就转移桶数组挂在的头节点到新数组
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 重新映射时，需要对红黑树进行拆分
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K, V> loHead = null, loTail = null;
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> next;
// 遍历链表，并将链表节点按原顺序进行分组
do {
next = e.next;
// e.hash & oldCap in [0, 1], 按照 0/1 将原链表分为两组, 达到扩容并均分元素的目的
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 将分组后的链表映射到新桶中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
resize() 方法做了三件事:
- 重新计算
capacity和threshold - 创建新的数组, 并初始化
- 将原来的节点重新映射到新数组,
- 如果节点属于红黑树, 就对红黑树进行拆分
- 如果节点属于链表, 就将节点按照原顺序分为两组
在计算新的容量和阈值的时候有几种情况:
oldCap > 0: 桶数组已经被初始化了oldCap == 0 && oldThr > 0: 对应调用HashMap(int)或HashMap(int, float)构造函数的情况, 这时直接将新容量设置为原阈值, 新阈值会在后续算出oldCap == 0 && oldThr == 0: 对应调用无参构造的情况
在添加或删除元素的过程中, 链表和红黑树可能会互相转换, 我们来看看链表树化、红黑树链化以及拆分:
树化的条件:
- 链表长度 >=
TREEIFY_THRESHOLD - 桶数组容量 >=
MIN_TREEIFY_CAPACITY
通过第二点可以看出: HashMap 优先扩容, 其次树化. 因为如果过早树化, 在后续扩容过程中拆分红黑苏很繁琐.
to be edited ...
再来看看 get() 方法:
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
get() 方法调用 getNode() 方法获取 HashMap 中的元素. 通过 key 的 hashCode 定位桶数组位置, 再通过 key 来定位链表或树中的确切元素.
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab;
Node<K,V> first, e;
int n;
K k;
// 定位桶数组中对应的位置, 确保桶数组存在, 桶数组不为空, 桶数组挂载的头节点存在
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 检查挂载的头节点是否为要查找的元素, 要求是 key 和 hash 相等
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果不是头节点, 就往下查找, 调用红黑树的获取元素的方法 或者 遍历链表查找
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
getNode() 方法主要做了两件事:
- 通过
hash值定位桶数组中散列的位置:table[(n - 1) & hash] - 在桶数组对应位置挂载的链表或红黑树中寻找对应元素.
- 先单独判断一次头节点, 再使用不同的方法遍历后续节点
- 判定方法:
hash值相等 并且key相等
最后我们看看 HashMap 的删除方法:
public V remove(Object key) {
Node<K, V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K, V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K, V>[] tab;
Node<K, V> p;
int n, index;
// 定位桶位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K, V> node = null, e;
K k;
V v;
// 如果键的值与链表第一个节点相等，则将 node 指向该节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
// 如果是 TreeNode 类型，调用红黑树的查找逻辑定位待删除节点
if (p instanceof TreeNode)
node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
else {
// 遍历链表，找到待删除节点
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 删除节点，并修复链表或红黑树
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
删除方法做了两件事:
- 定位元素
- 删除元素并修复链表或红黑树
5 ConcurrentHashMap
我们已经知道 HashMap 是线程不安全的, HashTable 虽然是线程安全的, 但是由于其直接加锁的机制导致效率低下. 所以设计了 ConcurrentHashMap 来支持并发读写.
ConcurrentHashMap 与 HashMap 还是有一些相同之处:
ConcurrentHashMap通过Node<K, V>[]桶数组来保存键值对, 桶数组会挂在链表或者红黑树.ConcurrentHashMap再创建时不会初始化桶数组, 而是在第一次添加元素时初始化, 初始化容量为 16.- 链表树化, 红黑树链化的条件和方式与
HashMap相同.
先来看看ConcurrentHashMap 的一些重要属性:
private static final int MAXIMUM_CAPACITY = 1 << 30;
private static final int DEFAULT_CAPACITY = 16;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
// 表示正在转移
static final int MOVED = -1;
// 表示已经转换成树
static final int TREEBIN = -2;
// hash for transient reservations
static final int RESERVED = -3;
// usable bits of normal node hash
static final int HASH_BITS = 0x7fffffff;
//默认没初始化的数组，用来保存元素
transient volatile Node<K,V>[] table;
//转移的时候用的数组
private transient volatile Node<K,V>[] nextTable;
/**
* 用来控制表初始化和扩容的，默认值为0，当在初始化的时候指定了大小，这会将这个大小保存在sizeCtl中，大小为数组的0.75
* 当为负的时候，说明表正在初始化或扩张，
* -1表示初始化
* -(1+n) n:表示活动的扩张线程
*/
private transient volatile int sizeCtl;
以及一些重要的类:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
Node(int hash, K key, V val, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return val; }
public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
public final String toString(){ return key + "=" + val; }
public final V setValue(V value) {
throw new UnsupportedOperationException();
}
public final boolean equals(Object o) {
Object k, v, u; Map.Entry<?,?> e;
return ((o instanceof Map.Entry) &&
(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
(v = e.getValue()) != null &&
(k == key || k.equals(key)) &&
(v == (u = val) || v.equals(u)));
}
/**
* Virtualized support for map.get(); overridden in subclasses.
*/
Node<K,V> find(int h, Object k) {
Node<K,V> e = this;
if (k != null) {
do {
K ek;
if (e.hash == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
} while ((e = e.next) != null);
}
return null;
}
}
// 构造树的节点
static final class TreeNode<K,V> extends Node<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next,
TreeNode<K,V> parent) {
super(hash, key, val, next);
this.parent = parent;
}
// ...
}
// 红黑树头节点只存储 root 和 first 节点, 不存储具体键值对数据
static final class TreeBin<K,V> extends Node<K,V> {
TreeNode<K,V> root;
volatile TreeNode<K,V> first;
volatile Thread waiter;
volatile int lockState;
// values for lockState
static final int WRITER = 1; // set while holding write lock
static final int WAITER = 2; // set when waiting for write lock
static final int READER = 4; // increment value for setting read lock
}
static final class ForwardingNode<K,V> extends Node<K,V> {
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) {
super(MOVED, null, null, null);
this.nextTable = tab;
}
}
然后我们来看看 ConcurrentHashMap 的重要方法:
在 ConcurrentHashMap 中使用了 unSafe 方法, 通过直接操作内存的方式来保证并发处理的安全性, 使用的是硬件的安全机制.
// 用来返回桶数组的指定位置的节点的原子操作
@SuppressWarnings("unchecked")
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
// cas原子操作，在指定位置设定值
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
// 原子操作，在指定位置设定值
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}
ConcurrentHashMap 提供了如下构造方法:
public ConcurrentHashMap() {
}
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
this.sizeCtl = DEFAULT_CAPACITY;
putAll(m);
}
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}
可以看到, 再初始化时都没有直接初始化桶数组, 而是只设置了容量.
提供了初始化桶数组的方法:
/**
* 初始化数组 table，
* 如果 sizeCtl 小于 0，说明别的数组正在进行初始化，则让出执行权
* 如果 sizeCtl 大于 0 的话，则初始化一个大小为 sizeCtl 的数组
* 否则的话初始化一个默认大小(16)的数组
* 然后设置 sizeCtl 的值为数组长度的 3/4
*/
private final Node<K,V>[] initTable() {
Node<K,V>[] tab;
int sc;
// 第一次 put 的时候，table 还没被初始化，进入 while
while ((tab = table) == null || tab.length == 0) {
// sizeCtl初始值为 0，当小于 0 的时候表示在别的线程在初始化表或扩展表
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
// SIZECTL：表示当前对象的内存偏移量，sc 表示期望值，-1 表示要替换的值，设定为 -1 表示要初始化表了
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
// 指定了大小的时候就创建指定大小的 Node 数组，否则创建指定大小(16)的 Node 数组
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
// 初始化后，sizeCtl 长度为数组长度的 3/4
sizeCtl = sc;
}
break;
}
}
return tab;
}
然后我们看看put()方法:
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
// key 和 value 都不能为空
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f;
int n, i, fh;
// 判断桶数组是否初始化, 如果没有就先初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// 如果桶数组对应位置空的, 就直接添加, 否则取出挂载的头节点
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break;
}
// 如果取出节点的 hash 值等于 MOVED(-1), 表示当前正在对这个数组进行扩容, 复制到新的数组, 当前线程也会去帮助复制
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// 如果当前节点不为空, 也不在扩容时间, 就通过 synchronized 进行加锁, 完成添加操作
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
// 遍历链表, 判断是添加新的元素还是更改原有的元素
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// 如果是红黑树, 就通过 putTreeVal 方法将元素添加到树中
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
// 判断添加的节点处共有多少节点(添加前数量), 判断是否需要扩容或者树化
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// 更新节点数量
addCount(1L, binCount);
return null;
}
可以看出, put() 方法一共做了五件事:
- 如果是第一次
put(), 初始化桶数组 - 获取桶数组对应位置的头节点, 如果为空就直接添加
- 头节点不为空, 就取出来, 根据
hash判断当前状态:- 如果在扩容阶段(
MOVED), 就让当前线程帮助复制元素 - 如果在正常时期, 就通过
synchronized加锁完成添加操作
- 如果在扩容阶段(
- 添加:
- 如果是链表, 就遍历链表决定是添加新节点还是更改原节点
- 如果是红黑树, 就调用红黑树的
putTreeVal()方法添加节点
- 添加完成后, 判断是否需要扩容或树化, 并更新节点数量
然后是另一个难点--扩容机制:
在 put() 方法中, 会调用 treeifyBin() 方法来判断是扩容还是树化. 同时, 在添加完元素后调用的 addCount() 方法中, 也会判断当前数组中的元素是否达到了 sizeCtl 的量, 如果达到了, 会进入 transfer() 方法进行扩容.
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b;
int n, sc;
if (tab != null) {
// 如果没有达到树化的条件, 就先调用 tryPresize() 方法进行扩容
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
// 达到树化条件, 就进行树化
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) {
if (tabAt(tab, index) == b) {
TreeNode<K,V> hd = null, tl = null;
for (Node<K,V> e = b; e != null; e = e.next) {
TreeNode<K,V> p =
new TreeNode<K,V>(e.hash, e.key, e.val,
null, null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
来看看 tryPresize() 的扩容方法:
/*
* 扩容表为指可以容纳指定个数的大小（总是2的N次方）
* 假设原来的数组长度为 16，则在调用 tryPresize 的时候，size 参数的值为 16<<1(32)，此时 sizeCtl 的值为12
* 计算出来 c 的值为 64,则要扩容到 sizeCtl ≥ c 为止
* 第一次扩容之后 数组长：32 sizeCtl：24
* 第二次扩容之后 数组长：64 sizeCtl：48
* 第二次扩容之后 数组长：128 sizeCtl：94 --> 这个时候才会退出扩容
*/
private final void tryPresize(int size) {
/*
* MAXIMUM_CAPACITY = 1 << 30
* 如果给定的大小大于等于数组容量的一半，则直接使用最大容量，
* 否则使用 tableSizeFor() 算出来
* 后面 table 一直要扩容到这个值小于等于 sizeCtrl (数组长度的3/4) 才退出扩容
*/
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table;
int n;
/*
* 如果数组 table 还没有被初始化，则初始化一个大小为 sizeCtrl 和刚刚算出来的 c 中较大的一个大小的数组
* 初始化的时候，设置 sizeCtrl 为 -1，初始化完成之后把 sizeCtrl 设置为数组长度的3/4
* 为什么要在扩张的地方来初始化数组呢？这是因为如果第一次 put 的时候不是 put 单个元素，
* 而是调用 putAll 方法直接 put 一个 map 的话，在 putAll 方法中没有调用initTable 方法去初始化 table，
* 而是直接调用了 tryPresize() 方法，所以这里需要做一个是不是需要初始化 table 的判断
*/
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
}
}
/*
* 一直扩容到 c 小于等于 sizeCtl 或者数组长度大于最大长度的时候退出
* 所以在一次扩容之后，不是原来长度的两倍，而是 2 的 n 次方倍
*/
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
/*
* 如果正在扩容 table 的话，则帮助扩容
* 否则的话，开始新的扩容
* 在 transfer 操作，将第一个参数的 table 中的元素，移动到第二个元素的 table 中去，
* 虽然此时第二个参数设置的是 null，但是，在 transfer 方法中，当第二个参数为null 的时候，会创建一个两倍大小的 table
*/
else if (tab == table) {
int rs = resizeStamp(n);
if (sc < 0) {
Node<K,V>[] nt;
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
}
}
}
to be edited ...(太难了, 还看不懂呜呜呜)
至于 ConcurrentHashMap 的 get() 方法, 原理和 HashMap 是相同的.
public V get(Object key) {
Node<K,V>[] tab;
Node<K,V> e, p;
int n, eh;
K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
// 寻找链表中的元素
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
看了一部分源码, 我们来理解一下 ConcurrentHashMap 的同步机制:
首先是读操作:get() 操作源码中并没有使用任何同步机制, 也没有使用 unsafe 方法, 所以 get() 是支持并发操作的.那么 get() 操作如何保证取到的数据是正确的呢? 先来看看 get() 相关的并发场景:
- 多线程在对
ConcurrentHashMap扩容后, 正在对数据进行迁移, 此时get()的数据正好在被迁移. - 多个线程都在修改
get()的数据, 如 何保证数据不被脏读.
在 get() 源码中, 可以看到是通过对 eh = e.hash 进行判断的:
- 如果
eh和key计算出的hashCode相同, 就说明挂载的第一个节点就符合要求(那么这个节点一定是链表节点) - 如果
eh < 0, 就会出现两种情况:eh == -1说明当前的数据正在迁移中, 就调用ForwardingNode的find()方法在新的数组中查找eh == -2说明该节点是红黑树节点, 就调用红黑树的find()方法进行查找
由 (2.a)的情况就可以解决并发场景1的问题. 在扩容后, 数据被迁移时, 旧数组中的节点会被替换为 ForwardingNode, hash置为 -1, 并且, 在其内部维护了一个 nextTable 指向新的数组, 当发现 hash == -1 时, 就会去新数组中查找. 对于并发场景2的问题, 使用 volatile 关键之就可以解决, 注意 Node 中的 value 使用了 volatile 修饰, 来保证线程之间的可见性.
然后是写操作: 写操作相关的并发场景如下:
- 在扩容是可以写数据吗?
- 多线程写数据如何保证安全?
其实在扩容时可以执行写操作的. 如果当前节点还没有被处理(也就是还没有被设置为 ForwardingNode)的时候, 可以执行写操作. 如果当前节点已经被处理了, 当前先成功就会加入到扩容操作中去. 在多线程方面, 主要是通过 synchronized 关键字和 unsafe 方法实现的线程安全:
- 在取得
sizeCtl、某个位置的Node的时候，使用的都是unsafe的方法，来达到并发安全的目的 - 当需要在某个位置设置节点的时候，则会通过
synchronized的同步机制来锁定该位置的节点。 - 在数组扩容的时候，则通过处理的步长和
ForwardingNode节点来达到并发安全的目的，通过设置hash值为MOVED - 当把某个位置的节点复制到扩张后的
table的时候，也通过synchronized的同步机制来保证线程安全