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概念和底层结构

1.3.1 概念

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

HashMap内部结构：可以看作是数组和链表结合组成的复合结构，数组被分为一个个桶（bucket），每个桶存储有一个或多个Entry对象，每个Entry对象包含三部分key（键）、value（值），next(指向下一个Entry），通过哈希值决定了Entry对象在这个数组的寻址；哈希值相同的Entry对象（键值对），则以链表形式存储。如果链表大小超过树形转换的阈值（TREEIFY_THRESHOLD= 8），链表就会被改造为树形结构。
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 put

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

① 判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
② 根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③ 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
④ 判断table[i] 是否为treeNode，即table[i]是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤ 遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可（包括hashCode以及equals的比较）
⑥ 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

1.3.2.2 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.3 如何重新调整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位置。

1.4 哈希碰撞

由于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冲突，那要解决冲突，又有哪些方法呢？具体如下：

• 链地址法：将哈希表的每个单元作为链表的头结点，所有哈希地址为i的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。也可以这样理解：链地址法其实就是HashMap中用的策略。原理是在HashMap中同样哈希值的位置以一串链表存储起来数据，把多个原始值不同而哈希结果相同的数据以链表存储起来
• 开放定址法：即发生冲突时，去寻找下一个空的哈希地址。只要哈希表足够大，总能找到空的哈希地址。
• 再哈希法：即发生冲突时，由其他的函数再计算一次哈希值。
• 建立公共溢出区：将哈希表分为基本表和溢出表，发生冲突时，将冲突的元素放入溢出表。

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

1.5 红黑树

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

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

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

红黑树示意图如下：

2 ConcurrentHashMap

2.1 分段锁

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锁。

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