HashMap原理，碰撞，ConcurrentHashMap_hashmap底层实现原理 hash冲突

1 HashMap

1.1 哈希算法

Hashing(哈希法)的概念
散列法（Hashing）是一种将字符组成的字符串转换为固定长度（一般是更短长度）的数值或索引值的方法，称为散列法，也叫哈希法。由于通过更短的哈希值比用原始值进行数据库搜索更快，这种方法一般用来在数据库中建立索引并进行搜索，同时还用在各种解密算法中。

1.2 对比：Hashtable、HashMap、TreeMap

1.2.1 Hashtable

Hashtable 是早期Java类库提供的一个哈希表实现继承自Dictionary，本身是同步的方法是synchronized，不支持null键和值，由于同步导致的性能开销，所以已经很少被推荐使用。

1.2.2 HashMap

HashMap与HashTable主要区别在于HashMap不是同步的，支持null键和值等。通常情况下，HashMap 进行 put 或者 get 操作，可以达到常数时间的性能，所以它是绝大部分利用键值对存取场景的首选。

1.2.3 TreeMap

TreeMap 则是基于红黑树的一种提供顺序访问的 Map，和 HashMap 不同，它的 get、put、remove 之类操作都是 O（log(n)）的时间复杂度，具体顺序可以由指定的 Comparator 来决定，或者根据键的自然顺序来判断。

1.3 HashMap概念和底层结构

jdk1.7在多线程和头插情况下会形成链表而死锁，jdk1.8是尾插+红黑树结构

1.3.1 概念

HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。HashMap储存的是键值对，HashMap很快。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap内部结构：可以看作是数组和链表结合组成的复合结构，数组被分为一个个桶（bucket），每个桶存储有一个或多个Entry对象，每个Entry对象包含三部分key（键）、value（值），next(指向下一个Entry），通过哈希值决定了Entry对象在这个数组的寻址；哈希值相同的Entry对象（键值对），则以链表形式存储。

如果链表大小超过树形转换的阈值（TREEIFY_THRESHOLD= 8）并且数组长度大于64，才将链表转换成红黑树，变成红黑树的目的是提高搜索速度，高效查询，链表就会被改造为树形结构。
将链表转换成红黑树前会判断，如果当前数组的长度小于64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间
hashMap的结构示意图如下：

查询时间复杂度：HashMap的本质可以认为是一个数组，数组的每个索引被称为桶，每个桶里放着一个单链表，一个节点连着一个节点。很明显通过下标来检索数组元素时间复杂度为O(1)，而且遍历链表的时间复杂度是O(n)，所以在链表长度尽可能短的前提下，HashMap的查询复杂度接近O(1)

数组：存储区间连续，占用内存严重，寻址容易，插入删除困难；
链表：存储区间离散，占用内存比较宽松，寻址困难，插入删除容易；
Hashmap综合应用了这两种数据结构，实现了寻址容易，插入删除也容易。

1.3.2 原理

HashMap的工作原理
HashMap的工作原理 ：HashMap是基于散列法（又称哈希法）的原理，使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket（桶）位置来储存Entry对象。HashMap是在bucket中储存键对象和值对象，作为Map.Entry。并不是仅仅只在bucket中存储值。

1.3.2.1 加载因子设置0.75，初始化临界值12

HashMap中的threshold是HashMap所能容纳键值对的最大值。计算公式为length*LoadFactory。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数也越大

loadFactory越趋近于1，那么数组中存放的数据（entry也就越来越多），数据也就越密集，也就会有更多的链表长度处于更长的数值，我们的查询效率就会越低，当我们添加数据，产生hash冲突的概率也会更高

默认的loadFactory是0.75，loadFactory越小，越趋近于0，数组中个存放的数据(entry)也就越少，表现得更加稀疏

0.75是对空间和时间效率的一种平衡选择

如果负载因子小一些比如是0.4，那么初始长度16*0.4=6，数组占满6个空间就进行扩容，很多空间可能元素很少甚至没有元素，会造成大量的空间被浪费
如果负载因子大一些比如是0.9，这样会导致扩容之前查找元素的效率非常低

loadfactory设置为0.75是经过多重计算检验得到的可靠值，可以最大程度的减少rehash的次数，避免过多的性能消耗

1.3.2.2 哈希表底层怎么计算hash值

hashCode方法是Object中的方法，所有的类都可以对其进行使用，首先底层通过调用hashCode方法生成初始hash值h1，然后将h1无符号右移16位得到h2，之后将h1与h2进行按位异或（^）运算得到最终hash值h3，之后将h3与(length-1)进行按位与（&）运算得到hash表索引

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
1
2
3
4

计算hash值时为什么要让低16bit和高16bit进行异或处理

我们计算索引需要将hashCode值与length-1进行按位与运算，如果数组长度很小，比如16，这样的值和hashCode做异或实际上只有hashCode值的后4位在进行运算，hash值是一个随机值，而如果产生的hashCode值高位变化很大，而低位变化很小，那么有很大概率造成哈希冲突，所以我们为了使元素更好的散列，将hash值的高位也利用起来

举个例子
如果我们不对hashCode进行按位异或，直接将hash和length-1进行按位与运算就有可能出现以下的情况

如果下一次生成的hashCode值高位起伏很大，而低位几乎没有变化时，高位无法参与运算

可以看到，两次计算出的hash相等，产生了hash冲突，所以无符号右移16位的目的是使高混乱度地区与地混乱度地区做一个中和，提高低位的随机性，减少哈希冲突

其他可以计算出hash值的算法有

• 平方取中法
• 取余数
• 伪随机数法

1.3.2.3 put

HashMap具体的存取过程：
put存值的方法，过程如下：

1. 首先根据key的值计算hash值，找到该元素在数组中存储的下标
2. 如果数组是空的，则调用resize进行初始化；
3. 如果没有哈希冲突直接放在对应的数组下标里
4. 如果冲突了，且key已经存在，就覆盖掉value
5. 如果冲突后是链表结构，就判断该链表是否大于8，如果大于8并且数组容量小于64，就进行扩容；如果链表节点数量大于8并且数组的容量大于64，则将这个结构转换成红黑树；否则，链表插入键值对，若key存在，就覆盖掉value
6. 如果冲突后，发现该节点是红黑树，就将这个节点挂在树上
   

1.3.2.4 一般用什么作为HashMap的key

一般用Integer、String这种不可变类当HashMap当key

因为String是不可变的，当创建字符串时，它的hashcode被缓存下来，不需要再次计算，相对于其他对象更快
因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的，这些类很规范的重写了hashCode()以及equals()方法

1.3.2.5 get

get取值的方法，过程如下:

① 指定key通过hash函数得到key的hash值int hash=key.hashCode();
② 调用内部方法 getNode()，得到桶号(一般为hash值对桶数求模)int index =hash%Entry[].length;
jdk1.6版本后使用位运算替代模运算，int index=hash&( Entry[].length - 1）;
③ 比较桶的内部元素是否与key相等，若都不相等，则没有找到。相等，则取出相等记录的value
④ 如果得到key所在的桶的头结点恰好是红黑树节点，就调用红黑树节点的 getTreeNode() 方法，否则就遍历链表节点。
getTreeNode 方法使通过调用树形节点的 find()方法进行查找。由于之前添加时已经保证这个树是有序的，因此查找时基本就是折半查找，效率很高。
⑤ 如果对比节点的哈希值和要查找的哈希值相等，就会判断 key是否相等，相等就直接返回；不相等就从子树中递归查找。

1.3.2.6 如何重新调整HashMap大小

问题：“如果HashMap的大小超过了负载因子(loadFactor)定义的容量，怎么办？”
HashMap的扩容阈值（threshold =capacity* loadFactor容量范围是16到2的30次方），就是通过它和size进行比较来判断是否需要扩容。默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组（jdk1.6，但不超过最大容量），来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。

HashMap在容量超过负载因子所定义的容量之后，就会扩容。java里的数组是无法自己扩容的，将HashMap的大小扩大为原来数组的两倍

扩容之后原位置的节点只有两种调整

• 保持原位置不动（新bit位为0时）
• 散列原索引+扩容大小的位置去（新bit位为1时）

扩容之后元素的散列设置的非常巧妙，节省了计算hash值的时间，我们来看一 下具体的实现

当数组长度从16到32，其实只是多了一个bit位的运算，我们只需要在意那个多出来的bit为是0还是1，是0的话索引不变，是1的话索引变为当前索引值+扩容的长度，比如5变成5+16=21

这样的扩容方式不仅节省了重新计算hash的时间，而且保证了当前桶中的元素总数一定小于等于原来桶中的元素数量，避免了更严重的hash冲突，均匀的把之前冲突的节点分散到新的桶中去

1.4 哈希碰撞

1.4.1 hash冲突概念

由于Hash算法并不完美，有可能两个不同的原始值在经过哈希运算后得到同样的结果，再对长度求模，比如：hash(key)%len，这样就是哈希碰撞。

解决 hash 冲突的常见方法：
针对哈希表直接定址可能存在hash冲突，举一个简单的例子，例如：
第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A。
第二个键值对B，通过计算其index也等于0， HashMap会将B.next =A,Entry[0] =B,
第三个键值对C，通过计算其index也等于0，那么C.next = B,Entry[0] = C；
这样我们发现index=0的地方事实上存取了A,B,C三个键值对,它们通过next这个属性链接在一起。 对于不同的元素，可能计算出了相同的函数值，这样就产生了hash冲突，那要解决冲突，又有哪些方法呢

1.4.2 解决hash冲突方法

具体如下：

• 链地址法：将哈希表的每个单元作为链表的头结点，所有哈希地址为i的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。也可以这样理解：链地址法其实就是HashMap中用的策略。原理是在HashMap中同样哈希值的位置以一串链表存储起来数据，把多个原始值不同而哈希结果相同的数据以链表存储起来
• 开放定址法也称为再散列法：即发生冲突时，去寻找下一个空的哈希地址。只要哈希表足够大，总能找到空的哈希地址。基本思想就是，如果p=H(key)出现冲突时，则以p为基础，再次hash，p1=H§，如果p1再次出现冲突，则以p1为基础，以此类推，直到找到一个不冲突的哈希地址pi。因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素，而且因为存在再次hash，所以只能在删除的节点上做标记，而不能真正删除节点
  点击了解ThreadLocal的内部类ThreadLocalMap采用的开放定址法
• 再哈希法（双重散列，多重散列）：即发生冲突时，由其他的函数再计算一次哈希值。提供多个不同的hash函数，R1=H1(key1)发生冲突时，再计算R2=H2（key1），直到没有冲突为止。这样做虽然不易产生堆集，但增加了计算的时间。
• 建立公共溢出区：将哈希表分为基本表和溢出表，发生冲突时，将冲突的元素放入溢出表。

注意开放定址法和再哈希法的区别是

开放定址法只能使用同一种hash函数进行再次hash，再哈希法可以调用多种不同的hash函数进行再次hash

HashMap采用哪种方法解决冲突的呢？
HashMap就是使用链地址法来解决冲突的（jdk8中采用平衡树来替代链表存储冲突的元素，但hash() 方法原理相同）。当两个对象的hashcode相同时，它们的bucket位置相同，碰撞就会发生。此时，可以将 put 进来的 K- V 对象插入到链表的尾部。对于储存在同一个bucket位置的链表对象，可通过键对象的equals()方法用来找到键值对。

1.5 红黑树

1.5.1 红黑树定义

红黑树：Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)（二叉树最大查找次数等于树的深度），效率非常之高。例如，Java集合中的TreeSet和TreeMap，以及Linux虚拟内存的管理，都是通过红黑树去实现的。
红黑树的特性：

• 每个节点或者是黑色，或者是红色。
• 根节点是黑色。
• 每个叶节点是黑色。 [注意：这里叶节点，是指为空(NIL或NULL)的叶子节点！]
• 如果一个节点是红色的，则它的子节点必须是黑色的，红色节点的孩子和父亲都不能是红色。从每个叶子到根的所有路径上不能有两个连续的红色节点
• 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对接近平衡的二叉树，并不是一个完美平衡二叉查找树。

TreeNode<K,V>用来实现红黑树相关的存储结构

红黑树示意图如下：

点击了解更多二叉树各种类型相关知识

1.5.2 转换红黑树条件

1.5.2.1 阈值8和数组长度64

在将链表转换成红黑树前会判断，如果当前数组的长度小于64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间
如果链表大小超过树形转换的阈值（TREEIFY_THRESHOLD= 8）并且数组长度大于64，才将链表转换成红黑树，变成红黑树的目的是提高搜索速度，高效查询，链表就会被改造为树形结构

1.5.2.2 为什么要在数组长度大于64之后,链表才会进化为红黑树

在数组比较小时如果出现红黑树结构，反而会降低效率，而红黑树需要进行左旋右旋，变色，这些操作来保持平衡，同时数组长度小于64时，搜索时间相对要快些，总之是为了加快搜索速度，提高性能

JDK1.8以前HashMap的实现是数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当HashMap中有大量的元素都存放在同一个桶中时，这个桶下有一条长长的链表，此时HashMap就相当于单链表，假如单链表有n个元素，遍历的时间复杂度就从O（1）退化成O（n），完全失去了它的优势，为了解决此种情况，JDK1.8中引入了红黑树（查找的时间复杂度为O（logn））来优化这种问题

1.5.2.3 为什么Map桶中节点个数超过8才转为红黑树

8作为阈值作为HashMap的成员变量，在源码的注释中并没有说明阈值为什么是8
在HashMap中有这样一段注释说明，我们继续看

因为树节点的大小大约是普通节点的两倍，所以我们只在箱子包含足够的节点时才使用树节点（参见TREEIFY_THRESHOLD）。
当他们边的太小（由于删除或调整大小）时，就会被转换回普通的桶，在使用分布良好的hashcode时，很少使用树箱。
理想情况下，在随机哈希码下，箱子中节点的频率服从泊松分布
第一个值是：

• 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

树节点占用空间是普通Node的两倍，如果链表节点不够多却转换成红黑树，无疑会耗费大量的空间资源，并且在随机hash算法下的所有bin节点分布频率遵从泊松分布，链表长度达到8的概率只有0.00000006，几乎是不可能事件，所以8的计算是经过重重科学考量的

从平均查找长度来看，红黑树的平均查找长度是logn，如果长度为8，则logn=3，而链表的平均查找长度为n/4，长度为8时，n/2=4，所以阈值8能大大提高搜索速度
当长度为6时红黑树退化为链表是因为logn=log6约等于2.6，而n/2=6/2=3，两者相差不大，而红黑树节点占用更多的内存空间，所以此时转换最为友好

1.6 为什么HashMap线程不安全

为什么HashMap线程不安全

• 多线程下扩容死循环。JDK1.7中的HashMap使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题
• 多线程的put可能导致元素的丢失。多线程同时执行put操作，如果计算出来的索引位置是相同的，那会造成前一个key被后一个key覆盖，从而导致元素的丢失。此问题在JDK1.7和JDK1.8中都存在
• put和get并发时，可能导致get为null。线程1执行put时，因为元素个数超出threshold而导致rehash，线程2此时执行get，有可能导致这个问题，此问题在JDK1.7和JDK1.8中都存在

2 ConcurrentHashMap

我们都知道 HashMap 是一个线程不安全的类，多线程环境下，使用 HashMap 进行 put 操作会引起死循环，导致CPU利用率接近100%，所以如果 并发量很高的话，所以是不推荐使用 HashMap 的。而我们所知的，HashTable 是线程安全的，但是因为 HashTable 内部使用的 synchronized 来保证线程的安全，所以，在多线程情况下，HashTable 虽然线程安全，但是他的效率也同样的比较低下。
所以就出现了一个效率相对来说比 HashTable 高，但是还比 HashMap 安全的类，那就是 ConcurrentHashMap，而 ConcurrentHashMap 在 JDK8 中却放弃了使用分段锁，使用了数组+链表/红黑树

2.1 jdk1.8之前

2.1.1 分段锁 Segment

HashTable容器在竞争激烈的并发环境下表现出效率低下的原因，是因为所有访问HashTable的线程都必须竞争同一把锁，那假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是ConcurrentHashMap所使用的锁分段技术

ConcurrentHashMap分段锁：
首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。这里按顺序是很重要的，否则极有可能出现死锁，在ConcurrentHashMap内部，段数组是final的，并且其成员变量实际上也是final的，但是，仅仅是将数组声明为final的并不保证数组成员也是final的，这需要实现上的保证。这可以确保不会出现死锁，因为获得锁的顺序是固定的。

ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁ReentrantLock，在ConcurrentHashMap里扮演锁的角色，HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构， 一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素， 每个Segment守护者一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。

2.1.2 分段锁 Segment 缺点

分段锁很容易理解，既然其他的锁都是锁全部，那分段锁是不是和其他的不太一样，它就相当于把一个方法切割成了很多块，在单独的一块上锁的时候，其他的部分是不会上锁的，也就是说，这一段被锁住，并不影响其他模块的运行，分段锁如果这样理解是不是就好理解了，我们先来看看 JDK7 中的 ConcurrentHashMap 的分段锁的实现。

在 JDK7 中 ConcurrentHashMap 底层数据结构是数组加链表，源码如下：

//初始总容量，默认16
static final int DEFAULT_INITIAL_CAPACITY = 16;
//加载因子，默认0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//并发级别，默认16
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
 
static final class Segment<K,V> extends ReentrantLock implements Serializable { 
	transient volatile HashEntry<K,V>[] table; 
}
1
2
3
4
5
6
7
8
9
10

上面的源码中，有 Segment<K,V>，这个类才是真正的的主要内容， ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

我们看到了 Segment<K,V>，而他的内部，又有HashEntry数组结构组成. Segment 继承自 RentrantLock 在这里充当的是一个锁，而在其内部的 HashEntry 则是用来存储键值对数据.

最后也就出现了，如果不是在同一个分段中的 put 数据，那么 ConcurrentHashMap 就能够保证并行的 put ，也就是说，在并发过程中，他就是一个线程安全的 Map 。

那么为什么 JDK8 舍弃掉了分段锁呢？

在 JDK7 中 Segment 继承了重入锁 ReentrantLock，但是 如果每个 Segment 在增长的时候，锁的粒度也会在不断的增长。
一个Segment 里包含一个HashEntry数组，每个锁控制的是一段，那么如果分成很多个段的时候，这时候加锁的分段还是不连续的，是不是就会造成内存空间的浪费。
所以分段锁在某些特定的情况下是会对内存造成影响的，什么情况呢？我们倒着推回去就知道：

1. 每个锁控制的是一段，当分段很多，并且加锁的分段不连续的时候，内存空间的浪费比较严重。
   大家都知道，并发是什么样子的，就相当于百米赛跑，你是第一，我是第二这种形式，同样的，线程也是这样的，在并发操作中，因为分段锁的存在，线程操作的时候，争抢同一个分段锁的几率会小很多，既然小了，那么应该是优点了，但是大家有没有想过如果这一分块的分段很大的时候，那么操作的时间是不是就会变的更长了。
   所以第二个问题出现了：
2. 如果某个分段特别的大，那么就会影响效率，耽误时间。
   所以，这也是为什么在 JDK8 不在继续使用分段锁的原因。

2.1.3 synchronized+cas 的优势

从下面几个角度讨论这个问题：

• 锁的粒度
  首先锁的粒度并没有变粗，甚至变得更细了。原来每扩容一次，ConcurrentHashMap 的并发度就扩大一倍。 原来的分段锁，锁的是一个段，大小是cap/conlevel 的桶的数量，现在只需要锁一个桶
• Hash冲突
JDK1.7中，ConcurrentHashMap从过二次hash的方式（Segment -> HashEntry）能够快速的找到查找的元素。在1.8中通过链表加红黑树的形式弥补了put、get 时的性能差距。
• 扩容
JDK1.8中，在ConcurrentHashmap进行扩容时，其他线程可以通过检测数组中的节点决定是否对这条链表（红黑树）进行扩容，减小了扩容的粒度，提高了扩容的效率。不是每次都要整体扩容，只需要对当前链表或者红黑树扩容，减小了扩容的粒度

为什么是synchronized，而不是ReentranLock

• 减少内存开销
  假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承AQS来获得同步支持。但并不是每个节点都需要获得同步支持的，只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。
• 获得JVM的支持
  可重入锁毕竟是API这个级别的，后续的性能优化空间很小。 synchronized 则是JVM直接支持的，JVM 能够在运行时作出相应的优化措施：锁粗化、锁消除、锁自旋等等。这就使得 synchronized 能够随着JDK版本的升级而不改动代码的前提下获得性能上的提升

2.2 jdk1.8之后

JDK1.8的实现已经抛弃了Segment分段锁机制，利用CAS+Synchronized来保证并发更新的安全。数据结构采用：数组+链表/红黑树。

2.2.1 主要属性

外部类的基本属性

volatile Node<K,V>[] table;   // Node数组用于存放链表或者树的头结点
static final int TREEIFY_THRESHOLD = 8;   // 链表转红黑树的阈值 > 8 时
static final int UNTREEIFY_THRESHOLD = 6;  // 红黑树转链表的阈值  <= 6 时
static final int TREEBIN   = -2;    // 树根节点的hash值
static final float LOAD_FACTOR = 0.75f;// 负载因子
static final int DEFAULT_CAPACITY = 16;   // 默认大小为16
内部类 
class Node<K,V> implements Map.Entry<K,V> {
    int hash;       
   final K key;       
   volatile V val;
   volatile Node<K,V> next;
}

jdk1.8中虽然不在使用分段锁，但是仍然有Segment这个类，但是没有实际作用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.2.2 主要方法

2.2.2.1 构造方法

构造方法并没有直接new出来一个Node的数组，只是检查数值之后确定了容量大小。

ConcurrentHashMap(int initialCapacity) {
        if (initialCapacity < 0)   
            throw new IllegalArgumentException(); 
如果传入的数值>= 最大容量的一半，就使用最大容量，否则使用1.5*initialCapacity +1 ，然后向上取最近的 2 的 n 次方数； 
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }
1
2
3
4
5
6
7
8
9

2.2.2.2 put方法：

步骤：

1. 检查Key或者Value是否为null，
2. 得到Key的hash值
3. 如果Node数组是空的，此时才初始化 initTable()，
4. 如果找的对应的下标的位置为空，直接new一个Node节点并放入， break；
5. 如果对应头结点不为空， 进入同步代码块
6. 判断此头结点的hash值，是否大于零，大于零则说明是链表的头结点在链表中寻找，
   如果有相同hash值并且key相同，就直接覆盖，返回旧值 结束
   如果没有则就直接放置在链表的尾部
   此头节点的Hash值小于零，则说明此节点是红黑二叉树的根节点
   调用树的添加元素方法
   判断当前数组是否要转变为红黑树

public V put(K key, V value) {
    return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());// 得到 hash 值
    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();
 
        // 找该 hash 值对应的数组下标，得到第一个节点 f
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 如果数组该位置为空，
            //    用一次 CAS 操作将新new出来的 Node节点放入数组i下标位置
            //          如果 CAS 失败，那就是有并发操作，进到下一个循环
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;          // no lock when adding to empty bin
        }
        // hash 居然可以等于 MOVED，这个需要到后面才能看明白，不过从名字上也能猜到，肯定是因为在扩容
         else if ((fh = f.hash) == MOVED)
            // 帮助数据迁移，这个等到看完数据迁移部分的介绍后，再理解这个就很简单了
            tab = helpTransfer(tab, f);
 
        else { // 到这里就是说，f 是该位置的头结点，而且不为空
 
            V oldVal = null;
            // 获取链表头结点监视器对象
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) { // 头结点的 hash 值大于 0，说明是链表
                        // 用于累加，记录链表的长度
                        binCount = 1;
                        // 遍历链表
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            // 如果发现了"相等"的 key，判断是否要进行值覆盖，然后也就可以 break 了
                            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;
                            }
                        }
                    }
                    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;
                        }
                    }
                }
            }
            // binCount != 0 说明上面在做链表操作
            if (binCount != 0) {
                // 判断是否要将链表转换为红黑树，临界值： 8
                if (binCount >= TREEIFY_THRESHOLD)
                    // 如果当前数组的长度小于 64，那么会进行数组扩容，而不是转换为红黑树
                    treeifyBin(tab, i);   // 如果超过64，会转成红黑树
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    // 
    addCount(1L, binCount);
    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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

2.2.2.3 get 方法

首先获取到Key的hash值，
然后找到对应的数组下标处的元素
如果此元素是我们要找的，直接返回，
如果此元素是null 返回null
如果Key的值< 0 ,说明是红黑树，

public V get(Object key) {
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        int h = spread(key.hashCode());   //获得Hash值
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            if ((eh = e.hash) == h) {  // 比较 此头结点e是否是我们需要的元素
                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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

注意：get操作时，发现get操作全程是没有加任何锁的，由于table这个变量是transient volatile Node<K,V>[] table;，用volatile修饰的，在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的，所以读取时无需加锁

2.2.2.4 扩容：tryPresize（）

扩容后数组容量为原来的 2 倍。

private final void tryPresize(int size) {
        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;
            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;
                    }
                }
            }
            else if (c <= sc || n >= MAXIMUM_CAPACITY)
                break;
            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);
            }
        }
    }
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

2.2.2.5 其他内部类结构

2.2.2.5.1 Node

ConcurrentHashMap存储结构的基本单元，实现了Map.Entry接口，用于存储数据。它对value和next属性设置了volatile同步锁(与JDK7的Segment相同)，它不允许调用setValue方法直接改变Node的value域，它增加了find方法辅助map.get()方法。

2.2.2.5.2TreeNode

继承于Node，但是数据结构换成了二叉树结构，它是红黑树的数据的存储结构，用于红黑树中存储数据，当链表的节点数大于8时会转换成红黑树结构，他就是通过TreeNode作为存储结构代替Node来转换成黑红树。

2.2.2.5.3 TreeBin

从字面含义中可以理解为存储树形结构的容器，而树形结构就是指TreeNode，所以TreeBin就是封装TreeNode的容器，它提供转换黑红树的一些条件和锁的控制。

2.2.2.5.4 ForwardingNode

一个用于连接两个table的节点类。它包含一个nextTable指针，用于指向下一张表。而且这个节点的key value next指针全部为null，它的hash值为-1. 这里面定义的find的方法是从nextTable里进行查询节点，而不是以自身为头节点进行查找。

2.2.2.5.5 Unsafe和CAS

在ConcurrentHashMap中，随处可以看到U, 大量使用了U.compareAndSwapXXX的方法，这个方法是利用一个CAS算法实现无锁化的修改值的操作，他可以大大降低锁代理的性能消耗。这个算法的基本思想就是不断地去比较当前内存中的变量值与你指定的一个变量值是否相等，如果相等，则接受你指定的修改的值，否则拒绝你的操作。因为当前线程中的值已经不是最新的值，你的修改很可能会覆盖掉其他线程修改的结果。这一点与乐观锁，SVN的思想是比较类似的。

2.2.3 通过什么保证线程安全

通过使用Synchroized关键字来同步代码块，而且只是在put方法中加锁，在get方法中没有加锁
在加锁时是使用头结点作为同步锁对象。，并且定义了三个原子操作方法

// 获取tab数组的第i个node<br>   
 @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算法设置i位置上的node节点。csa（你叫私有空间的值和内存中的值是否相等），即这个操作有可能不成功。
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);
}
// 利用volatile方法设置第i个节点的值，这个操作一定是成功的。
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
    U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.2.4 和hashTable的保证线程安全的机制有何联系

Hashtable通过synchronized修饰方法 来保证线程安全
通过synchronized同步代码块和CAS操作来实现线程安全
由此抛出的问题：为什么要用synchronized，cas不是已经可以保证操作的线程安全吗？
原因：
CAS也是适用一些场合的，比如资源竞争小时，是非常适用的，不用进行内核态和用户态之间的线程上下文切换，同时自旋概率也会大大减少，提升性能，但资源竞争激烈时（比如大量线程对同一资源进行写和读操作）并不适用，自旋概率会大大增加，从而浪费CPU资源，降低性能