Map
JDK1.7
以下内容针对JDK1.7版本，需要确保安装了JDK1.7
在IDEA中将项目设置Project SDK、Project language level等版本改为1.7
设置 Java Compiler中需要把Use compiler from module target JDK when possible的勾去除
HashMap
1.7版本底层是使用的数组+链表
public class HashMapTest {
public static void main(String[] args) {
HashMap<String, String> map = new HashMap<String, String>();
map.put("123", "2");
map.get("123");
}
}了解ArrayList
ArrayList部分源码
private transient Object[] elementData; // 实际维护的数组
private static final Object[] EMPTY_ELEMENTDATA = {};
public ArrayList() {
super(); // super为空代码块
this.elementData = EMPTY_ELEMENTDATA; // 默认为空数组
}
private int size; // 实际使用的容量
public int size() {
return size;
}
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 判断是否需要扩容
elementData[size++] = e; // 插入到元素下标+1的位置
return true;
}
/* 默认容量,该变量在AbstractList
private static final int DEFAULT_CAPACITY = 10;
*/
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) { // 数组为空(只调用了构造方法初始化)
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // 10
}
ensureExplicitCapacity(minCapacity);
}
// 修改次数,可以通过该值判断被其它线程修改过导致线程不安全
protected transient int modCount = 0;
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果满了则说明数组在插入元素会导致溢出,需要扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) { // 扩容
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}指定下标
public void add(int index, E element) {
rangeCheckForAdd(index); // 下标是否合法,不能超过size
ensureCapacityInternal(size + 1);
// 复制的过程为把相对于当前插入位置(index)后面的数据都向后移动一位
// 所以说ArrayList元素之间插入性能较低
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}ArrayList内部就是数组
如果不指定下标则依次插入,指定下标则插入下标的位置
List<String> list = new ArrayList<>();
list.add("123");
list.add(1, "123");HashMap的下标
HashMap底层也是数组，是如何定义下标的呢
简单理解
通过key调用hashCode方法来作为下标
但是hashCode的数比较大，所以需要取余来确定下标
取余的值就是当前数组的length
当下一个hashCode取余后的值已经存在一个元素(哈希冲突)，则数组该下标还会维护着一个链表
简单的链表
jdk1.7HashMap是往头部插入 一般情况下插入链表头部必然最快
但是HashMap还需要将整个链表遍历一遍,所以插在头部和插在尾部并没有区别
以下代码只是简单的链表理解，无法实现完整链表的功能
public class Node {
// 实际维护的元素
private Object content;
// 链表指向的下一个元素
private Node next;
public Node(Object content, Node next) {
this.content = content;
this.next = next;
}
public static void main(String[] args) {
Node header = new Node(0, null);
// 插入尾部
Node node = new Node(1, null);
header.next = node;
Node node2 = new Node(2, null);
node.next = node2;
// 插入头部,node5代替header成为头节点
// 头部可以直接插入
Node node5 = new Node(4, header);
while (node5.next != null) {
System.out.println(node5.content);
node5 = node5.next;
}
System.out.println(node5.content);
// 插入尾部需要把整个链表遍历一遍
node5.next = new Node(123, null);
System.out.println(node5.next.content);
}
}链表向下移动
每次插入一个元素并且导致哈希冲突时都加入这个链表，但是如果只是插入头部的话，这个链表是无法完整遍历的
这个时候要完整遍历还需要遍历链表头部的元素
解决办法是直接将链表向下移动
伪代码
发生哈希冲突只需要生成链表,并且将数组中的Entry对象的改为链表的头节点
因为链表只需要头节点就可以实现整个链表的遍历
int hashCode = key.hashCode();
int index = hashCode % table.length;
// table[index] = new Entry(key, value, null); // 如果第一次插入
table[index] = new Entry(key, value, table[index]); // 如果已经多次插入HashMap源码
HashMap常量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16 数组初始容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认负载因子
static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824 最大数组容量
static final Entry<?,?>[] EMPTY_TABLE = {}; // 空数组核心代码
transient int size; // HashMap存储的元素数
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; // 核心数组,默认为空
transient int modCount; // 修改次数
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
final float loadFactor; // 负载因子
int threshold; // 阈值
public HashMap(int initialCapacity, float loadFactor) {
// 校验代码
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor)) // Float.isNaN(0.0f / 0.0f)
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 负载因子赋值
this.loadFactor = loadFactor;
threshold = initialCapacity; // 16
init(); // HashMap的init方法为空代码块(为子类设计的方法)
}get
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
// 确定数组下标,循环链表
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
// 如果为true代表找到
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
private V getForNullKey() {
if (size == 0) {
return null;
}
// 如果为null直接从数组[0]寻找
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) // 为null找到
return e.value;
}
return null;
}put方法
Hash值确定下标,但是Hash值较大所以通过indexFor将值缩小(可以简单理解为取余)
通过数组的头节点开始,取链表的下一个节点,下一个节点为空跳出循环(链表最底部为空)
循环中依次判断链表中是否有Hash值相等,key是否相等的元素,如果有则覆盖并将原来的value返回
如果有重复只要找到就return,并且不会实现插入
如果没有重复的值会将整个链表遍历一遍判断是否有重复的值
头插法和尾插发性能没有区别,并且头插法还会导致链表死循环,所以1.8改为尾插法
public V put(K key, V value) {
if (table == EMPTY_TABLE) { // 判断是否为空
inflateTable(threshold);
}
if (key == null) // HashMap键可以为空
return putForNullKey(value);
int hash = hash(key); // 返回Hash值
int i = indexFor(hash, table.length); // 得到数组的下标
// 遍历链表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 判断是否已经有相同的key
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// 取出老value
V oldValue = e.value;
// 覆盖
e.value = value;
// 空代码块,为子类设计的方法
e.recordAccess(this);
// 直接返回老value,不实行插入
return oldValue;
}
}
modCount++;
// 插入链表头部
addEntry(hash, key, value, i);
// 没有重复的key返回null
return null;
}获取数组下标
HashMap并没有直接使用取余,但是起到了类似的效果
最重要的原因是取余性能较慢,位运算较快
需要满足2个必要条件
数组不能越界
必须平均分布
数组容量减1,一般情况下数组容量为16减1为15,转换为二进制 0000 1111
hashCode假设为85,转换为二进制0101 0101
与操作的结果为 0000 0101,可以发现因为与的特性只有后四位才会被改变(同理数组扩容为32后,则只有后五位才会被改变)
后4位取值范围为0000 到 1111,即0-15
hash值的生成是完全随机的,所以同时达成了这两点要求
总而言之,h & (length-1) 只要保证length的长度是2^n的话,就可以实现取模运算
static int indexFor(int h, int length) {
return h & (length-1);
}初始化数组
HashMap初始化并没有直接使用传递过来的size作为数组容量而是对它进行加工
roundUpToPowerOf2 获取大于等于该数的2的幂次方数
1 -> 0000 0001 ->2的0次方
2 -> 0000 0010 ->2的1次方
4 -> 0000 0100 ->2的2次方
8 -> 0000 1000 ->2的3次方
16 -> 0001 0000 ->2的4次方
将一个数转换为2进制,如果高位为1其余为0就是2的幂次方数
左移即翻倍
Integer.highestOneBit 返回小于等于该数的2的幂次方数
所以需要将该数翻倍,即15变30
小于30的2的幂次方数为16
这样就找到了15大于等于该数的2的幂次方数为16
至于减一是因为防止传递进来的数正好是2的幂次方数
16翻倍后为32,32的小于等于该数的2的幂次方数还是32
如果减一就可以避免这个问题,16-1=15,30的小于等于该数的2的幂次方数是16
为什么数组初始化一定要是2的幂次方数呢？
原因是indexFor没有使用取余而是位运算
所以结果必须为2的幂次方数
private void inflateTable(int toSize) { // 初始化数组
int capacity = roundUpToPowerOf2(toSize); // 一般情况下结果为16
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity]; // 生成容量为capacity的Entry数组
initHashSeedAsNeeded(capacity);
}
private static int roundUpToPowerOf2(int number) {
// 大于等与0的2的幂次方数
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
// 如果number为0则返回1,即2的0次方
// Integer.highestOneBit返回小于等于与0的2的幂次方数
// 所以需要将传递进去的参数减一后左移即可返回大于等与0的2的幂次方数
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
/* Integer中的静态方法
public static int highestOneBit(int i) {
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
*/找到小于等于2的幂次方数,这种方式显然比循环效率高
以17为例,17的2进制为 0001 0001 右移1位为 0000 1000,在进行或运算0001 0001,0000 1000结果为 0001 1001(或运算,有1为1)
0001 1001右移2位 0000 0110,或运算结果 0001 1111
0001 1111右移4位 0000 0001,或运算结果为 0001 1111
0001 1111右移8位 0000 0000,或运算结果为 0001 1111
0001 1111右移16位 0000 0000,或运算结果为 0001 1111
0001 1111无符号右移1位结果为 0000 1111
0001 1111与0000 1111相减结果为 0001 0000 转换为十进制结果为16
右移8位后数值就不在改变了,因为此处只是测试17这样较小的值
int类型32 bit,为了防止输入的是较大的数所以还需要右移8位和16位
17 -> 1 0001
>>1 -> 0 1000
| -> 1 1001
>>2 -> 0 0110
| -> 1 1111
>>4 -> 0 0001
| -> 1 1111
>>8 -> 0 0000
| -> 1 1111
>>>1 -> 0 1111
- -> 1 0000若有一个数为 001$ $$$$, $可能为0或1
右移1位 0001 $$$$,或运算 0011 $$$$
右移2位 0000 11$$,或运算 0011 11$$
右移4位 0000 0011,或运算 0011 1111
右移8位之后结果不变,不在列举
其实就是将一个数的最高位之后的数都变为1
最后再将这个数右移1位后相减就是要得到的值
也就是最高位后的数都变为0
Integer.highestOneBit(10); // 8
Integer.highestOneBit(16); // 16
Integer.highestOneBit(17); // 16
Integer.highestOneBit(6); // 4添加元素
首先判断是否需要扩容
HashMap的size是否大于等于阈值并且插入的位置为空
阈值为数组长度*负载因子
扩容容量翻倍
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) { // 判断是否大于阈值(扩容相关)
resize(2 * table.length); // 扩容为原来的两倍
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e); // 插入链表头部并下移
size++;
}扩容
void resize(int newCapacity) {
// 记录老数组
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
// 如果数组最大就不扩容了
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 创建一个新数组
Entry[] newTable = new Entry[newCapacity];
// 转移
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 替代原数组
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}转移
将老数组上的元素全部转移到新数组上
调用indexFor,新数组下标有两种情况
与原数组下标相同
如数组扩容后hash值为69与新数组长度32,0100 0101 与 0001 1111 结果为 0000 0101
与原数组下标翻倍
如数组扩容后hash值为85与新数组长度32,0101 0101 与 0001 1111 结果为 0001 0101
插入依然使用的是头插法
将原链表的尾部插入新链表的头部导致顺序相反
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 循环数组
for (Entry<K,V> e : table) {
// 循环链表
while(null != e) {
// e当前元素,next链表的下一个元素
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 通过新数组长度与hash值算出新的下标
int i = indexFor(e.hash, newCapacity);
// 当前元素next指向新数组
e.next = newTable[i];
// 将新数组指向当前元素(下移)
newTable[i] = e;
// 指向原链表的下一个元素(下次循环)
e = next;
}
}
}当前Entry指向新数组
下移
准备下一次循环
键为空的插入
如果插入的键为null会存在数组的第0位,直接return不再调用hash等方法
遍历数组的第0位的链表
key为null并不代表数组第0位只有一个元素
因为其它的key也可能存在第0位,所以还是需要遍历
/* put方法
if (key == null)
return putForNullKey(value);
*/
private V putForNullKey(V value) {
// 和put类似
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// hash值,bucketIndex固定为0
addEntry(0, null, value, 0);
return null;
}获取hash
hashCode是使用的Object并且可能会被重写,所以需要进行一系列异或操作让hash值更加散列
防止不同hash值的高位不同但低位相同导致的hash冲突
不断的右移让高位也参与进来
防止大量哈希碰撞导致链表过长
异或 不同为1相同为0
比起与、或,异或可以更加任意的改变高位的数值
transient int hashSeed = 0; // hash种子
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode(); // 让生成的hash值更加散列
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}多线程情况下Hashmap可能会导致循环链表
假设有2个线程,HashMap数组扩容后长度为4,内有链表为1、2、3
每个线程都会执行resize方法,并且生成局部变量数组
Entry[] newTable = new Entry[newCapacity];第一个线程扩容完成,链表内的元素为3、2、1
此时的e为1,next为2
因为此时使用的是老数组的e和next
table = newTable; // 最后赋值给成员变量而第二个线程还再进行扩容操作
int newCapacity = newTable.length; // 4
// 开始循环链表
Entry<K,V> next = e.next; // 线程2在此处因为CPU分配暂时暂停
int i = indexFor(e.hash, newCapacity); // 获取下标
e.next = newTable[i]; // 指向newTable[i]
newTable[i] = e; // 下移
e = next;
// 第二次循环
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i]; // 正好相等
newTable[i] = e; // 下移
e = next;
// 第三次循环
Entry<K,V> next = e.next; // 指向null
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i]; // 重写指向头元素(出现问题,导致循环链表)
newTable[i] = e; // 向上移动
e = next; // 指向null,循环结束
table = newTable; // 最后将问题数组赋值给成员变量 转移的时候不直接移动链表头部(这样只需要一次移动,就能转移整个链表)
原因是移动链表只是其中一个原因,更重要的是为了减少链表的长度(转移后的元素可能在原来的下标也有可能在原来的下标*2)
插入到新数组的位置和老数组不一定相等
Hash种子
初始化数组inflateTable和数组扩容resize会调用方法
作用是使之后生成的hash值更散列
int h = hashSeed;
h ^= k.hashCode();hashSeed默认等于false,HashMap中只有该方法才会改变hashSeed的值
第一次调用hashSeed一定为0,所以只有useAltHashing为false,hashSeed才会被改变
final boolean initHashSeedAsNeeded(int capacity) { // capacity为数组的容量
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() &&
// 大于等于数组容量
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) { // 为true才会改变hashSeed
hashSeed = useAltHashing // 生成hashSeed
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}只有改变该环境变量hashSeed才会发生改变
并且新数组容量 >= jdk.map.althashing.threshold才会生成hashSeed
-Djdk.map.althashing.threshold=3
modCount
以下代码在第2次循环时会导致java.util.ConcurrentModificationException
增加for循环就是语法糖,内部就是迭代器
每put一次modCount+1,此时modCount为2
HashIterator中的expectedModCount也为2
第一次循环判断使相等的,所以没有抛出异常
第二次不相等所以抛出异常
解决方法使用迭代器的remove方法
HashMap和keySet的remove方法都可以通过传递key参数删除任意的元素,而iterator只能删除当前元素
如果没有通过modCount、expectedModCount的比较实现快速失败抛出异常,下次循环该元素将成为current指向，此时iterator就遍历了一个已移除的过期数据
并且该方法也可以在一定情况下防止线程不安全的情况发生(一个线程删,一个线程读取)
快速失效是一种能立刻报告表明故障的情况,设计用于立刻停止操作,而不是试图继续可能存在缺陷的过程（注意是可能而不是一定）。也就是说modcount只能提出问题,而无法解决问题,一个线 程不安全的类能够被多个线程同时访问这种设计本身就不合理
HashMap<String, String> map = new HashMap<>();
map.put("1", "2");
map.put("2", "2");
Iterator var2 = map.keySet().iterator();
while(var2.hasNext()) {
String key = (String)var2.next();
if ("2".equals(key)) {
map.remove(key);
}
}remove
modCount为修改次数为3
但是expectedModCount依然为2所以抛出了异常
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
// 获取hash值和数组下标
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
// 遍历链表
while (e != null) {
Entry<K,V> next = e.next;
Object k;
// 找到了
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++; // modCount++
size--;
// 将该元素从链表移除
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}KeySet
部分代码
transient volatile Set<K> keySet = null;
public Set<K> keySet() {
Set<K> ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
}
private final class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return newKeyIterator(); // 返回一个迭代器
}
}迭代器
Iterator<K> newKeyIterator() {
return new KeyIterator();
}
// 调用该内部类时还会调用父类构造方法
private final class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}HashIterator
部分代码
KeyIterator的父类
使用它迭代起的remove则不会抛出异常
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next;
int expectedModCount;
int index;
Entry<K,V> current;
HashIterator() {
// expectedModCount赋值
expectedModCount = modCount;
if (size > 0) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
// 判断modCount和expectedModCount是否不相等
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
// 迭代器的remove方法
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
// 重新赋值modCount,使用迭代器remove则不会出现异常
expectedModCount = modCount;
}
}Entry
entry可以直接理解为链表
部分代码
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; // key
V value; // value
Entry<K,V> next; // 下一个元素
int hash; // hash值
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}ConcurrentHashMap
HashMap使非线程安全的
了解HashTable
HashTable都添加了synchronized代码块解决并发问题
Hashtable是一个保留类,很老旧的类,性能很低,很多地方没有考虑性能
并发安全建议使用ConcurrentHashMap来代替HashTable
使用了大量取余
int index = (hash & 0x7FFFFFFF) % tab.length;ConcurrentHashMap源码
ConcurrentHashMap内部为分段数组
ConcurrentHashMap内有Segment[]属性,Segement内有HashEntry[]属性
HashEntry的长度可以简单理解为根据initialCapacity / concurrencyLevel
常量
static final int DEFAULT_INITIAL_CAPACITY = 16; // 默认初始化容量(每个分段长度)
static final int DEFAULT_CONCURRENCY_LEVEL = 16; // 默认并发级别
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认加载因子
static final int MIN_SEGMENT_TABLE_CAPACITY = 2; // 每个Segment内HashEntry数组最小为2核心代码
算出ssize的值,ssize只要小于并发级别就左移
循环找到大于等于并发级别的2的幂次方数
如果调用默认构造方法则sshift为4,ssize为16
计算c的值
initialCapacity为所有HashEntry的长度,ssize为Segment的长度
为确保每个Segment的HashEntry数量相等,可能需要加1。即Segment长度16,HashEntry总长度却为33,也需要加1,1个Segment对应3个HashEntry
ConcurrentHashMap只要求初始化时HashEntry长度数量一致(放入Segment[0]),之后扩容只会扩容对应的Segment内的HashEntry数组
结算cap的值
c无法直接使用为Segment数组的容量,需要加工为2的幂次方
Segment[0]是原型
public ConcurrentHashMap() {
// 默认长度 加载因子 并发级别
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
}
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
// 校验代码
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// ssize只要小于并发级别就左移
int sshift = 0;
int ssize = 1;
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
this.segmentShift = 32 - sshift;
this.segmentMask = ssize - 1; // 获取segment数组的下标
// 校验代码
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity) // c*ssize为理论HashEntry的总长度
++c; // 向上取整
int cap = MIN_SEGMENT_TABLE_CAPACITY; // 最小为2
while (cap < c)
cap <<= 1; // 结果为2的幂次方
// 创建Segment对象
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
// 创建Segment数组
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
// 把Segment放在Segment[0]
UNSAFE.putOrderedObject(ss, SBASE, s0);
this.segments = ss;
}put
key和value均不能为空
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
// 该Segment数组下标是否为空
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject
(segments, (j << SSHIFT) + SBASE)) == null)
s = ensureSegment(j);
return s.put(key, hash, value, false);
}ensureSegment
CAS保证只有一个线程可以对这个Segment赋值
private Segment<K,V> ensureSegment(int k) {
final Segment<K,V>[] ss = this.segments;
long u = (k << SSHIFT) + SBASE;
Segment<K,V> seg;
// 判断该位置是否为空
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
Segment<K,V> proto = ss[0]; // 从Segment[0]是原型取出
int cap = proto.table.length;
float lf = proto.loadFactor;
int threshold = (int)(cap * lf);
HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
// 再次判断是否为空,如果为空创建
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
// 只是new并没有放入Segment,依然需要判断该位置是否为空
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
// CAS自旋,为null则赋值
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
break;
}
}
}
return seg;
}Segment
可以理解为HashMap
put
tryLock
尝试加锁(不会阻塞),如果获取到返回true,否则返回false
如果失败则调用scanAndLockForPut
与lock的区别为,如果无法获取锁会阻塞直到获取到锁
遍历HashEntry下的链表,如果位置不为空则插入
插入使用了UNSAFE.putOrderedObject是直接改变内存中的值,而tab[index]改动的只是当前线程的值
onlyIfAbsent
是否校验key已经重复（put方法为关闭校验,putIfAbsent方法为开启）
若校验,则key重复也不会更新value
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 加锁
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) { // 遍历链表
if (e != null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) { // 存在覆盖
oldValue = e.value;
if (!onlyIfAbsent) { // 此处为false
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
// e为null则代表进入链表尾部
else {
if (node != null)
node.setNext(first);
else
// 放入指定位置(头插法)
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1; // 内部的size
// HashEntry内的扩容
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
// 将HashEntry改为链表的新头节点
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
// 解锁
unlock();
}
return oldValue;
}scanAndLockForPut
不断尝试获取锁
第一次循环retries为-1
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
// 取当前Hash值的下标
HashEntry<K,V> first = entryForHash(this, hash);
HashEntry<K,V> e = first;
HashEntry<K,V> node = null;
int retries = -1;
while (!tryLock()) {
HashEntry<K,V> f;
if (retries < 0) {
if (e == null) {
// 遍历到链表尾部则创建HashEntry
if (node == null)
node = new HashEntry<K,V>(hash, key, value, null);
retries = 0;
}
else if (key.equals(e.key))
retries = 0;
else
e = e.next;
}
// 如果超过则强制加锁
else if (++retries > MAX_SCAN_RETRIES) {
lock();
break;
}
// 代表
else if ((retries & 1) == 0 &&
(f = entryForHash(this, hash)) != first) {
e = first = f;
retries = -1;
}
}
return node;
}