本文目录
-
HashMap的设计思维
- HashMap的底层构造
- 为什么不一开始就应用HashMap构造
- 为什么Map中的节点超过8个时才转换成红黑树
-
为什么HashMap不是线程平安的
- [同时put碰撞导致数据失落](#同时put碰撞导致数据失落) - [扩容期间取出的值不精确](#扩容期间取出的值不精确) -
HashMap在java7和java8中的区别
- [底层数据结构比照](#底层数据结构比照) - [插入方式比照](#插入方式比照) - [扩容形式比照](#扩容形式比照) -
ConcurrentHashMap在java7和java8中的区别
- [数据结构](#数据结构) - [并发水平](#并发水平) - [遇到Hash碰撞](#遇到Hash碰撞)
HashMap的设计思维
HashMap的底层构造
本文次要是解说jdk1.8中的HashMap源码，会对jdk1.7中的HashMap做一些简略的解说用来和jdk1.8中的HashMap进行比照。
咱们先通过下图来了解HashMap的底层构造：
首先咱们通过下面的内容咱们能够看到HashMap构造都是这样一个特点：最开始Map时空的，而后往里面放元素
时会计算hash值，计算hash值之后，第一个value值会占用一个桶（也就是槽点），当前再来雷同hash值的value那么便会用链表的模式在该槽点后持续延长
这就是拉链法。
当链表的长度大于或者等于阙值的（默认是8）的时候，并且同时还满足以后HashMap的容量大于或等于MIN_TREEIFY_CAPACITY(默认64)的要求，就会把链表转成
红黑树结构，如果后续因为删除或者其它起因调整了大小，当红黑树的节点小于或等于6个当前，又会复原链表构造。
为什么不一开始就应用HashMap构造
官网给出的解释是：
Because TreeNodes are about twice the size of regular nodes,
we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD).
And when they become too small (due to removal or resizing) they
are converted back to plain bins.翻译就是：因为TreeNodes的大小大概是一般Node节点的两倍，
所以只有在节点足够多的状况下才会把Nodes节点转换成TreeNodes节点，
是否足够多又由TREEIFY_THRESHOLD决定，而当桶中的节点的数量因为移除或者调整大小变少后，
它们又会被转换回一般的链表构造以节俭空间。
通过源码中得悉，当链表长度达到8就转成红黑树结构，当树节点小于等于6时就转换回去，此处体现了工夫和空间的均衡思维。
为什么Map中的节点超过8个时才转换成红黑树
这个问题官网给的解释是：
In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally,
under random hashCodes, the frequency of nodes in bins follows a Poisson distribution
(http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5
on average for the default resizing threshold of 0.75, although with a large variance
because of resizing granularity. Ignoring variance, the expected occurrences of list
size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are:
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million下面的意思是：在应用散布良好的用户的hashCodes时，很少应用红黑树结构，因为在现实状况下，链表的节点频率遵循泊松散布（意思就是链表各个长度的命中率顺次递加），当命中第8次的时候，
链表的长度是8，此时的概率仅为0.00000006，小于千万分之一。
然而，HashMap中决定某一个元素落到哪一个桶中，是和某个对象的hashCode无关的，如果咱们本人定义一个极其不平均的hashCode，例如：
public int hashCode(){
return 1;
}因为上述的hashCode办法返回的hash值全部都是1，那么就会导致HashMap中的链表比那的很长，如果数据此时咱们向HashMap中放很多节点的话，HashMap就会转换成红黑树结构，所以链表长度超过8就转换成红黑树的设计更多的是为了避免用户本人实现了不好的哈希算法
而导致链表过长，影响查问效率，而此时通过转换红黑树结构用来保障极其状况下的查问效率。
HashMap初始化
HashMap的默认初始化大小是16，加载因子是0.75，扩容的阙值就是12（16*0.75），如果进行HashMap初始化的时候传入了自定义容量大小参数size，那么初始化的大小就是正好大于size的2的整数次方，比方传入10，大小就是16，传入30大小就是32，源码如下：
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;//n>>>1示意n的二进制向右挪动1位，以下同理，而后跟挪动前的n进行异或操作
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}上述源码中，通过将n的高位第一个1一直的右移，而后把高位1前面的全变为1，在最初return的时候返回n+1，就合乎HashMap容量都是2的整数次幂了。
例如下图：
为什么HashMap初始化的容量肯定是2的整数次幂
不论咱们传入的参数是怎么样的数值，HashMap外部都会通过tableSizeFor办法计算出一个正好大于咱们传入的参数的2的整数次幂的数值，那么为什么肯定要是2的整数次幂呢？
咱们先来看看计算key的hash办法如下：
//计算key的hash值，hash值是32位int值，通过高16位和低16进行&操作计算。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}失去了key的hash值后，在计算key在table中的地位索引的时候，代码如下：
if ((p = tab[i = (n - 1) & hash]) == null)正是因为n是2的整数次幂，比方当n是2时，它的二进制是10，4时是100，8时是1000，16时是10000….，那么（n-1）的二进制与之对应就是（2-1）是1，（4-1）是11，（8-1）是111，（16-1）是1111，为什么要用(n – 1) & hash
来计算数组的地位索引呢，正是因为(n – 1) & hash的索引肯定是落在0～（n-1）之间的地位，而不必管hash值是多少，因为“与”操作的后果就是散列值的高位全副归零，只保留低位值，用来做数组下标拜访。以初始长度16为例，
16-1=15，2进制示意是00000000 00000000 00001111。和某散列值做“与”操作如下，后果就是截取了最低的四位值。
为什么HashMap不是线程平安的
咱们先来看HashMap中的put办法的源码，如下：
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容量为空，则进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//计算hash值在表table中的地位，这里采纳&操作是为了更快的计算出地位索引，
//而不是取模运算，如果该地位为空，则间接将元素插入到这个地位
//此处也会产生多线程put，值笼罩问题。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//判断tab表中存在雷同的key。
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 {
//遍历链表寻找链表尾部插入新值，如果发现存在雷同的key，则进行遍历此时e指向反复的key
for (int binCount = 0; ; ++binCount) {
//jdk1.7采纳的是头差法，jdk1.8采纳的是尾差法
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//判断链表的长度是否大于TREEIFY_THRESHOLD，如果大于则转换红黑树结构
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;
}
}
//发现了反复的key，判断是否笼罩，如果笼罩返回旧值，
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//持续更新次数，不是原子操作，多线程put存在并发平安问题
++modCount;
//如果大于阙值(这个阙值和下面那个不一样，这个等于以后容量*加载因子,默认是16*0.75 = 12)，进行扩容。
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}上图局部源码中能够看出HashMap的put办法中有一行代码是++modCount，
咱们都晓得这段代码并不是一个原子操作，它实际上是三个操作，
执行步骤分为三步：读取、减少、保留，而且每步操作之间能够交叉其它线程的执行，
所以导致线程不平安。
另外还有导致线程不平安的状况还有：
同时put碰撞导致数据失落
//put办法中局部源码
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);比方下面的源码中，如果当初有两个线程A和B，它们的key的hash值正好一样，而后它们同时执行到了这个if判断，并且都发现tab中i的地位是空，那么线程A就将本人的元素放到该地位，然而线程B之前也是判断到这个地位为空，
所以他在A之后也将本人的元素放到了该地位而笼罩了之前线程A的元素，这就是多线程同时put碰撞导致数据失落的场景，所以HashMap是非线程平安的
扩容期间取出的值不精确
咱们先来看看HashMap的取值办法get的源码，源码如下：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//如果数组时空的，或者以后槽点是空的，阐明key所对应的value不存在，间接返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//判断第一个节点是否是咱们须要的节点，如果是则间接返回
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);
//遍历链表，查找key
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}下面的get办法的源码中能够看出get办法次要是以下步骤：
- 计算Hash值，并由此值找到对应的槽点。
- 如果数组是空的或者该地位为null，那么间接返回null就能够了。
- 如果该地位处的节点刚好就是咱们须要的，间接返回该节点的值。
- 如果该地位节点是红黑树或者正在扩容，就用find办法持续查找。
- 否则那就是链表，就进行遍历链表查找。
首先HashMap的get办法是从table中查问咱们要查找的key是否存在，如果存在则返回，不存在则间接返回null，
那么如果是在扩容期间，为什么获取的后果不精确呢？咱们再来看看HashMap的扩容办法resize()，局部源码如下：
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//重点在这里
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
.
.
.//此处疏忽
}
}
}下面的源码是HashMap的resize办法的一小部分，首先咱们晓得HashMap的扩容会把旧数组的数据迁徙到新数组中（怎么迁徙的咱们前面再说），在搬迁的过程中会把旧数组正在迁徙的桶置为空比方，正如
下面代码oldTab[j] = null这一行代码，正是把索引j的桶（或者槽点）置为空了，然而如果此时还没有实现所有的数据的迁徙，那么HashMap中依然是应用的旧数组，
此时咱们通过get办法查问的key的所以正好在这个旧数组中索引地位是oldTab[j]的地位，因为这个地位曾经置空了，所以就会返回null，所以产生了扩容期间读取数据不精确。
HashMap在java7和java8中的区别
底层数据结构比照
java7的HashMap的构造示意图如下：
上图中能够看出jdk1.7中HashMap采纳的数据结构是数组+链表的构造。
java8中的HashMap构造示意图如下：
从图中咱们能够看出，java8中的HashMap有三种数据结构：
- 第一种构造是就是数组，数组中空着的地位（槽）代表以后没有数据来填充
- 第二种是和jdk1.7HashMap相似的拉链构造，在每一个槽中会首先填入第一个节点，后续如果计算出雷同的Hash值，就用链表的模式往后延长
- 第三种是红黑树结构，这个是java7中HashMap中没有的数据结构，当第二种状况的链表长度大于某一个阙值（默认为8）的时候，HashMap便会把这个链表从链表构造转化为红黑树的模式，目标是为了保障查找效率，
这里简略介绍一下红黑树，红黑树是一种不严格的均衡二叉查找树,次要解决二叉查找树因为动静更新导致的性能进化,其中的均衡的意思代表着近似均衡,等价于性能不会进化.红黑树中的节点分为两类:彩色节点和红色节点,一颗红黑树须要满足:
- 根节点是彩色。
- 每个叶子节点都是彩色的空节点(null)。
- 任何相邻的节点都不能同时为红色,也就是说红色节点是被彩色离开的。
- 每个节点，从该节点达到其可达到的叶子节点的所有门路，都蕴含雷同数目的彩色节点。
因为红黑树的自均衡特点，所以其查找性能近似于二分查找，工夫复杂度是O(log(n))，相比于链表构造，
如果产生了最坏的状况，可能须要遍历整个链表能力找到指标元素，工夫复杂度为O(n)，远远大于红黑树的O(log(n))，
尤其是在节点越来越多的状况下，O(log(n))
插入方式比照
jdk1.7中插入新节点采纳的是头查法，就是如果来了新节点，将新节点插入到数组中，原数组中的原始节点作为新节点的后继节点，而且是先判断是否须要扩容，在插入。
jdk1.8中插入新节点的形式是尾查法，就是将新来的节点插入到数组中对应槽点的尾部，插入时先插入，在判断是否须要扩容。
扩容形式比照
jdk1.8中采纳的是原地位不变或者地位变为索引+旧容量大小，resize()办法局部源码如下：
//jdk1.8代码扩容形式
//其中的loHead结尾的示意低位链表结尾节点，loTail示意低位链表尾部节点，hiHead结尾的示意高位链表结尾节点，hiTail示意高位链表尾部节点
//因为扩容时，容量为之前的两倍，而扩容的办法又是原地位不变或者地位变为索引+旧容量大小，所以这里把扩容的容量分为两局部
//一部分是原容量大小，用loHead和loTail示意首尾地位节点，一部分是新扩容的容量大小，用hiHead和hiTail示意首尾地位节点
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
//该办法是扩容时采纳的尾查法
next = e.next;
//如果判断等于0，则节点在上面插入新数组中的地位索引等于其在旧数组中的地位索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//如果不能于0，节点在上面插入新数组中的地位索引等于在旧数组中的地位索引+旧数组容量大小
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;
}jdk1.7中的HashMap扩容的时候须要对原数组中的元素进行从新Hash定位在新数组中的地位，transfer办法的源码如下：。
//jdk1.7HashMap的扩容办法
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()办法把原数组中的值放到新数组中，同时根据initHashSeedAsNeeded(newCapacity)返回的boolean值决定是否从新hash
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//设置hashmap扩容后为新的数组援用
table = newTable;
//设置hashmap扩容新的阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
//保留e的后继节点。
Entry<K,V> next = e.next;
//从新hash在新数组中的地位
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//计算节点e在新数组中的地位索引
int i = indexFor(e.hash, newCapacity);
//将原节点e的后继节点指向newTable[i]，采纳的是头插法
e.next = newTable[i];
//将节点e放到newTable[i]数组中，
newTable[i] = e;
//将next付给e，开始下一次循环
e = next;
}
}
}同时因为jdk1.7中HashMap的扩容办法中调用的transfer办法内采纳的是头插法，头插法会使链表产生反转，多线程环境下，会产生循环链表，
下面代码咱们联合图来了解头插法和为什么多线程环境下会产生循环链表：
首先假如此时有原HashMap表的外部数据存储如下图：
此时达到了扩容要求，而后线程1和线程2此时同时进行扩容，线程1和线程2扩容时的新数组（newTable）如下图：
假如线程2先执行transfer办法，并且当它正好执行完了Entry<K,V> next = e.next;这行代码后，cpu工夫片切换到了线程1来执行，并且线程1执行完了transfer办法，如下图：
线程1插入A节点到本人的新表中
线程1插入B节点到本人的新表中
线程1插入C节点到本人的新表中
当线程1执行完了transfer办法后，还没有执行table = newTable这行代码，此时cpu工夫片有切换到了线程2，那么线程2持续接着之前的地位执行，此处须要留神因为
因为之前线程2切换线程1之前曾经执行完了Entry<K,V> next = e.next这行代码，因而在线程2中
变量e存的是A节点了，变量next存的是B节点，而且又因为线程1执行完了transfer办法后，原数组的节点指向如上图能够看出是C指向B，B是指向A的，所以切换到线程2的时候，线程2中的节点指向如下图：
线程2插入A节点到本人的新表中
线程2插入B节点到本人的新表中
因为B节点指向A节点，所以下次插入产生了链表循环，如下图：
综上就是HashMap采纳头插法的时候产生链表循环的场景。
jdk1.8中在对HashMap进行扩容的时候放弃头插法而改为尾插法了，扩容代码我曾经在下面的扩容形式代码中标出，通过尾插法就防止了因为链表反转导致多线程环境下产生链表循环的状况。
ConcurrentHashMap在java7和java8中的区别
数据结构
咱们先看一下jdk1.7中ConcurrentHashMap的底层数据结构，如下图：
图中咱们能够看出concurrentHashMap外部进行了Segment分段，Segment继承了ReentrantLock，能够了解为一把锁，
各个Segment之间互相独立上锁，互不影响，相比HashTable每次操作都须要锁住整个对象而言，效率大大晋升，正是因为concurrentHashMap
的锁粒度是针对每个Segment而不是整个对象。
每个Segment的底层数据结构又和HashMap相似，还是数组和链表组成的拉链构造，默认有0～15共16个Segment，所以最多
能够同时反对16个线程并发操作（每个线程别离散布在不同的Segment上）。16这个默认值能够在初始化的时候设置为其余值，一旦设置确认初始化
之后，是不能够扩容的。
jdk1.8中的ConcurrentHashMap的底层数据结构，如下图：
通过下面两个图中能够看出，jdk1.8中的ConcurrentHashMap在数据结构上比jdk1.7中多了红黑树结构，引入红黑树结构是为了避免查问效率升高。
并发水平
这里咱们简略通过java7和java8的ConcurrentHashMap的含参构造函数看一下比照，首先java7的ConcurrentHashMap的构造函数代码如下：
//通过指定的容量，加载因子和并发等级创立一个新的ConcurrentHashMap
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;
//sshift用来记录向左按位挪动的次数
int sshift = 0;
//ssize用来记录Segment数组的大小
int ssize = 1;
//Segment的大小为大于等于concurrencyLevel的第一个2的n次方的数
while (ssize < concurrencyLevel) {
++sshift;
//2的幂次方，2^1,2^2....
ssize <<= 1;
}
this.segmentShift = 32 - sshift;
this.segmentMask = ssize - 1;
//限度最大初始化容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//c统计每个Segment内有多少元素
int c = initialCapacity / ssize;
//如果有余数，则Segment数量加1
if (c * ssize < initialCapacity)
++c;
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
cap <<= 1;
//创立第一个Segment，并放入Segment[]数组中，作为第一个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];
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}jdk1.7中的并发等级（concurrencyLevel）用Segment的数量来确定，Segment的个数为大于等于concurrencyLevel的第一个2的n次方的整数，例如当concurrencyLevel为12,13,14,15,16时，此时的Segment的数量为16
java8中的源码汇总保留了Segment片段，然而并没有应用，构造函数如下：
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;
}通过下面的代码的比照能够得出一下论断：
- java7中采纳Segment分段锁来保障平安，每个Segment独立加锁，最大并发数就是Segment的个数，默认是16。
- java8中放弃了Segment设计，采纳Node+CAS+synchronized保障线程平安，锁粒度更新，现实状况下table数组元素的个数（也就是数组长度）就是反对并发的最大个数。
遇到Hash碰撞
- java7中遇到Hash抵触，采纳拉链法，查找时间复杂度是O(n)，n是链表的长度。
- java8中遇到Hash抵触，先采纳拉链法，查找时间复杂度是O(n)，当链表长度超过肯定阙值时，
将链表转换为红黑树结构，来保障查找效率，查找时间复杂度升高为O(log(n))，n为树中的节点个数。
微信公众号：程序员内功心法
发表回复