HashMap源码和实现原理（详解）

墨蓝 2022-01-31 13:59 231阅读 0赞

题记：这是以前写得一篇文章，有对别人文章的引用，现对文章进行补充复习！添加一些jdk1.8看到的内容。

### 1、HashMap的特性 ###

*  HashMap 是一个散列桶（数组和链表）这是jdk1.6和jdk1.7中得实现，而JDK1.8中，HashMap采用位桶+链表+红黑树实现
 *  它存储的内容是键值对 key-value 映射
 *  HashMap 采用了数组，链表和红黑树的数据结构，能在查询和修改方便继承了数组的线性查找和链表的寻址修改，当链表长度超过阈值（8）时，将链表转换为红黑树
 *  HashMap 是非 synchronized，所以 HashMap 很快
 *  HashMap 可以接受 null 键和值，而 Hashtable 则不能（原因就是 equlas() 方法需要对象，因为 HashMap 是后出的 API 经过处理才可以）

### 2、HashMap 的工作原理是什么？ ###

HashMap 是基于 hashing 的原理实现的

Hash算法：
    h 通过hash算法计算得到的的一个整型数值，也就是h是一个由hashcode产生的伪随机数
    h可以近似看做一个由key的hashcode生成的随机数，区别在于相同的hashcode生成的h必然相同
    而不同的hashcode也可能生成相同h，这种情况叫做hash碰撞，好的hash算法应尽量避免hash碰撞
    (ps:hash碰撞只能尽量避免，而无法杜绝,由于h是一个固定长度整型数据,原则上只要有足够多的输入，就一定会产生碰撞)
    关于hash算法有很多种，这里不展开赘述，只需要记住h是一个由hashcode产生的伪随机数即可
    同时需要满足key.hashcode -> h 分布尽量均匀(下文会解释为何需要分布均匀)

**这里先说put存储。HashMap重写了Map中的put方法**

我们使用 put(key, value) 存储对象到 HashMap 中，使用 get(key) 从 HashMap 中获取对象。当我们给 put() 方法传递键和值时，我们先对键调用 hashCode() 方法，计算并返回的 hashCode 是用于找到 Map 数组的 bucket 位置来储存 Node 对象。

这里关键点在于指出，HashMap 是在 bucket 中储存键对象和值对象，作为Map.Node 。

下面简单说下添加键值对put(key,value)的过程：  
1，判断键值对数组tab\[\]是否为空或为null，否则以默认大小resize()；  
2，根据键值key计算hash值得到插入的数组索引i，如果tab\[i\]==null，直接新建节点添加，否则转入3  
3，判断当前数组中处理hash冲突的方式为链表还是红黑树(check第一个节点类型即可),分别处理

以下是 HashMap 初始化

简化的模拟数据结构：

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 </td> 
 <td> <code>Node[] table = </code><code>new</code> <code>Node[</code><code>16</code><code>]; </code><code>// 散列桶初始化，table</code> <code>class</code> <code>Node { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>hash; </code><code>//hash值</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>key; </code><code>//键</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>value; </code><code>//值</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node next; </code><code>//用于指向链表的下一层（产生冲突，用拉链法）</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

存储查找原理：

*  存储：首先获取key的hashcode，然后取模数组的长度，这样可以快速定位到要存储到数组中的坐标，然后判断数组中是否存储元素，如果没有存储则，新构建Node节点，把Node节点存储到数组中，如果有元素，则迭代链表(红黑二叉树)，如果存在此key,默认更新value,不存在则把新构建的Node存储到链表的尾部。
 *  查找：同上，获取key的hashcode，通过hashcode取模数组的长度，获取要定位元素的坐标，然后迭代链表，进行每一个元素的key的equals对比，如果相同则返回该元素。

**HashMap在相同元素个数时，数组的长度越大，则Hash的碰撞率越低，则读取的效率就越高，数组长度越小，则碰撞率高，读取速度就越慢。典型的空间换时间的例子。**

## **如何减少碰撞？** ##

扰动函数可以减少碰撞

原理是如果两个不相等的对象返回不同的 hashcode 的话，那么碰撞的几率就会小些。这就意味着存链表结构减小，这样取值的话就不会频繁调用 equal 方法，从而提高 HashMap 的性能（扰动即 Hash 方法内部的算法实现，目的是让不同对象返回不同hashcode）。

使用不可变的、声明作 final 对象，并且采用合适的 equals() 和 hashCode() 方法，将会减少碰撞的发生

不可变性使得能够缓存不同键的 hashcode，这将提高整个获取对象的速度，使用 String、Integer 这样的 wrapper 类作为键是非常好的选择。

为什么 String、Integer 这样的 wrapper 类适合作为键？

因为 String 是 final，而且已经重写了 equals() 和 hashCode() 方法了。不可变性是必要的，因为为了要计算 hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的 hashcode 的话，那么就不能从 HashMap 中找到你想要的对象。

**如何解决Hash冲突？**

**解决方法一：开放寻址法**

通过在数组以某种方式寻找数组中空余的结点放置
    基本思想是：当关键字key的哈希地址p=H（key）出现冲突时
    以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，

通俗易懂的说法：

简单地讲，也就是说，一间厕所，来了一个顾客就蹲其想蹲的位置，如果又来一个顾客，把厕所单间门拉开，一看里
    面有位童鞋正在用劲，那么怎么办？很自然的，拉另一个单间的门，看看有人不，有的话就继续找坑。当然了，一般来说，
    这个顾客不会按顺序一个一个地拉厕所门，而是会去拉他认为有可能没有被占用的单间的门，这可以通过闻味道，听声音
    来辨别，这就是寻址查找算法。如果找遍了所有厕所单间，看尽了所有人的光屁股，还是找不到坑，那么这座厕所就该扩
    容了。当然了，厕所扩容不会就只单单增加一个坑位，而是综合考虑成本和保证不让太多顾客拉到裤子里，会多增加几个
    坑位，比如增加现有坑位的0.75倍。为什么是0.75呢，这是所长多年经营所得到的经验值，为了让自己的经验发扬光大，
    需要出去演讲，又不能太俗，总不能说“厕所坑位因子”吧，那就把把0.75叫做“装填因子”或者“扩容因子”吧。目
    前很多产品使用0.75这个常数。

**线性探查法：**

当冲突发生时，使用某种探查技术在散列表中形成一个探查（测）序列。沿此序列逐个单元地查找，直到找到给定的地址。按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。

下面给一个线性探查法的例子：

**问题：**已知一组关键字为 (26，36，41，38，44，15，68，12，06，51)，用除余法构造散列函数，用线性探查法解决冲突构造这组关键字的散列表。  
**解答：**为了减少冲突，通常令装填因子 α 由除余法因子是13的散列函数计算出的上述关键字序列的散列地址为 (0，10，2，12，5，2，3，12，6，12)。  
前5个关键字插入时，其相应的地址均为开放地址，故将它们直接插入 T\[0\]、T\[10)、T\[2\]、T\[12\] 和 T\[5\] 中。  
当插入第6个关键字15时，其散列地址2（即 h(15)=15％13=2）已被关键字 41（15和41互为同义词）占用。故探查 h1=(2+1)％13=3，此地址开放，所以将 15 放入 T\[3\] 中。  
当插入第7个关键字68时，其散列地址3已被非同义词15先占用，故将其插入到T\[4\]中。  
当插入第8个关键字12时，散列地址12已被同义词38占用，故探查 hl=(12+1)％13=0，而 T\[0\] 亦被26占用，再探查 h2=(12+2)％13=1，此地址开放，可将12插入其中。  
类似地，第9个关键字06直接插入 T\[6\] 中；而最后一个关键字51插人时，因探查的地址 12，0，1，…，6 均非空，故51插入 T\[7\] 中。

** **

**解决方法二：链地址法**

通过引入链表 数组中每一个实体存储为链表结构，如果发生碰撞，则把旧结点指针指向新链表结点，
    此时查询碰撞结点只需要遍历该链表即可
    在这种方法下，数据结构如下所示
    int类型数据 hashcode 为自身值

如下图可以看出HashMap底层就是一个数组结构，每个数组中又存储着链表（链表的引用）

HashMap是由数组加链表的结合体。如下图：

![format_png][]

这里敲黑板的是**扩容：为什么要扩容？扩容因子是大好，还是小好？**

什么时间开始扩容？
    当链表数组的容量超过初始容量的0.75时，再散列将链表数组扩大2倍，把原链表数组的搬移到新的数组中

数组是定长的，如果扩容因子太小数组就会很大，扩容时老数据要搬移到新数组中所以搬移的次数就会增多，
    增加消耗；如果扩容因子太大，数组长度小，hash冲突的几率增加，造成链表的长度过长，
    假设一种极端情况数组只有一位，链表无限长，这个时候就成了一个单向的遍历查询，
    这个时候的时间复杂度变成了O(n)。
    加载因子（默认0.75）：为什么需要使用加载因子，为什么需要扩容呢？因为如果填充比很大，
    说明利用的空间很多，如果一直不进行扩容的话，链表就会越来越长，这样查找的效率很低，
    因为链表的长度很大（当然最新版本使用了红黑树后会改进很多），扩容之后，将原来链表数组的每
    一个链表分成奇偶两个子链表分别挂在新链表数组的散列位置，这样就减少了每个链表的长度，
    增加查找效率
    
    HashMap本来是以空间换时间，所以填充比没必要太大。但是填充比太小又会导致空间浪费。
    如果关注内存，填充比可以稍大，如果主要关注查找性能，填充比可以稍小。

**当从哈希表中查询数据时，如果key对应一条链表,遍历时如何判断是否应该覆盖？**

当遍历链表时，如果两个key.hashcode的h一致会调用equals()方法判断是否为同一对象,
    equal的默认实现是比较两者的内存地址。
    因此为什么Java强调当重写equals()时需要同时重写hashcode()方法,假设两个不同对象，
    在内存中的地址不同分别为a和b,那么重写equals()以后a.equals(b) =true 
    开发者希望把a,b这两个key视作完全相等
    然而由于内存地址的不同导致hashcode不同,会导致在hashmap中储存2个本应相同的key值

**验证Demo:如果只重写了**

equals()时需要同时重写hashcode()方法,假设两个不同对象，在内存中的地址不同分别为a和b,那么重写equals()以后a.equals(b) =true 开发者希望把a,b这两个key视作完全相等,然而由于内存地址的不同导致hashcode不同,会导致在hashmap中储存2个本应相同的key值

重写hashcode()方法就会只有一个数据。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3c4OTM5MzI3NDc_size_16_color_FFFFFF_t_70][]

以下是具体的 put 过程（JDK1.8）

1.  对 Key 求 Hash 值，然后再计算下标
2.  如果没有碰撞，直接放入桶中（碰撞的意思是计算得到的 Hash 值相同，需要放到同一个 bucket 中）
3.  如果碰撞了，以链表的方式链接到后面
4.  如果链表长度超过阀值（TREEIFY THRESHOLD==8），就把链表转成红黑树，链表长度低于6，就把红黑树转回链表
5.  如果节点已经存在就替换旧值
6.  如果桶满了（容量16\*加载因子0.75），就需要 resize（扩容2倍后重排）

以下是具体 get 过程

**考虑特殊情况：**如果两个键的 hashcode 相同，你如何获取值对象？

当我们调用 get() 方法，HashMap 会使用键对象的 hashcode 找到 bucket 位置，找到 bucket 位置之后，会调用 keys.equals() 方法去找到链表中正确的节点，最终找到要找的值对象。

[![c3b34af2d13802399d5e61bb5b8cb87b.png][]][c3b34af2d13802399d5e61bb5b8cb87b.png 1]

### 4、HashMap 中 hash 函数怎么是实现的? ###

我们可以看到，在 hashmap 中要找到某个元素，需要根据 key 的 hash 值来求得对应数组中的位置。如何计算这个位置就是 hash 算法。

前面说过，hashmap 的数据结构是数组和链表的结合，所以我们当然希望这个 hashmap 里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个。那么当我们用 hash 算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表。 所以，我们首先想到的就是把 hashcode 对数组长度取模运算。这样一来，元素的分布相对来说是比较均匀的。

但是“模”运算的消耗还是比较大的，能不能找一种更快速、消耗更小的方式？我们来看看 JDK1.8 源码是怎么做的（被楼主修饰了一下）

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 </td> 
 <td> <code>static</code> <code>final</code> <code>int</code> <code>hash(Object key) { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>(key == </code><code>null</code><code>){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>0</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>h;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>h = key.hashCode()；返回散列值也就是hashcode</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// ^ ：按位异或</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// &gt;&gt;&gt;:无符号右移，忽略符号位，空位都以0补齐</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//其中n是数组的长度，即Map的数组部分初始化长度</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>(n-</code><code>1</code><code>)&amp;(h ^ (h &gt;&gt;&gt; </code><code>16</code><code>));</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

[![fb98d75b501aafb9109ce705a3118cae.png][]][fb98d75b501aafb9109ce705a3118cae.png 1]

简单来说就是：

*  高16 bit 不变，低16 bit 和高16 bit 做了一个异或（得到的 hashcode 转化为32位二进制，前16位和后16位低16 bit和高16 bit做了一个异或）
 *  (n·1) & hash = -> 得到下标

### 5、拉链法导致的链表过深，为什么不用二叉查找树代替而选择红黑树？为什么不一直使用红黑树？ ###

之所以选择红黑树是为了解决二叉查找树的缺陷：二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成层次很深的问题），遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋、右旋、变色这些操作来保持平衡。引入红黑树就是为了查找数据快，解决链表查询深度的问题。我们知道红黑树属于平衡二叉树，为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少。所以当长度大于8的时候，会使用红黑树；如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

### 6、说说你对红黑树的见解？ ###

[![cf94bb29c4b3cdb330ea4b57a6317187-300x216.png][]][cf94bb29c4b3cdb330ea4b57a6317187-300x216.png 1]

1.  每个节点非红即黑
2.  根节点总是黑色的
3.  如果节点是红色的，则它的子节点必须是黑色的（反之不一定）
4.  每个叶子节点都是黑色的空节点（NIL节点）
5.  从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）

### 8、如果 HashMap 的大小超过了负载因子（load factor）定义的容量怎么办？ ###

HashMap 默认的负载因子大小为0.75。也就是说，当一个 Map 填满了75%的 bucket 时候，和其它集合类一样（如 ArrayList 等），将会创建原来 HashMap 大小的两倍的 bucket 数组来重新调整 Map 大小，并将原来的对象放入新的 bucket 数组中。这个过程叫作 **rehashing**。

因为它调用 hash 方法找到新的 bucket 位置。这个值只可能在两个地方，一个是原下标的位置，另一种是在下标为 **<原下标+原容量>** 的位置。

### 9、重新调整 HashMap 大小存在什么问题吗？ ###

重新调整 HashMap 大小的时候，确实存在条件竞争。

因为如果两个线程都发现 HashMap 需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来。因为移动到新的 bucket 位置的时候，HashMap 并不会将元素放在链表的尾部，而是放在头部。这是为了避免尾部遍历（tail traversing）。如果条件竞争发生了，那么就死循环了。多线程的环境下不使用 HashMap。

为什么多线程会导致死循环，它是怎么发生的？

HashMap 的容量是有限的。当经过多次元素插入，使得 HashMap 达到一定饱和度时，Key 映射位置发生冲突的几率会逐渐提高。这时候， HashMap 需要扩展它的长度，也就是进行Resize。

1.  扩容：创建一个新的 Entry 空数组，长度是原数组的2倍
2.  rehash：遍历原 Entry 数组，把所有的 Entry 重新 Hash 到新数组

### 10、HashTable ###

*  数组 + 链表方式存储
 *  默认容量：11（质数为宜）
 *  put操作：首先进行索引计算 （key.hashCode() & 0x7FFFFFFF）% table.length；若在链表中找到了，则替换旧值，若未找到则继续；当总元素个数超过 容量 \* 加载因子 时，扩容为原来 2 倍并重新散列；将新元素加到链表头部
 *  对修改 Hashtable 内部共享数据的方法添加了 synchronized，保证线程安全

### 11、HashMap 与 HashTable 区别 ###

*  默认容量不同，扩容不同
 *  线程安全性：HashTable 安全
 *  效率不同：HashTable 要慢，因为加锁

### 12、可以使用 CocurrentHashMap 来代替 Hashtable 吗？ ###

*  我们知道 Hashtable 是 synchronized 的，但是 ConcurrentHashMap 同步性能更好，因为它仅仅根据同步级别对 map 的一部分进行上锁
 *  ConcurrentHashMap 当然可以代替 HashTable，但是 HashTable 提供更强的线程安全性
 *  它们都可以用于多线程的环境，但是当 Hashtable 的大小增加到一定的时候，性能会急剧下降，因为迭代时需要被锁定很长的时间。由于 ConcurrentHashMap 引入了分割（segmentation），不论它变得多么大，仅仅需要锁定 Map 的某个部分，其它的线程不需要等到迭代完成才能访问 Map。简而言之，在迭代的过程中，ConcurrentHashMap 仅仅锁定 Map 的某个部分，而 Hashtable 则会锁定整个 Map

### 13、CocurrentHashMap（JDK 1.7） ###

*  CocurrentHashMap 是由 Segment 数组和 HashEntry 数组和链表组成
 *  Segment 是基于重入锁（ReentrantLock）：一个数据段竞争锁。每个 HashEntry 一个链表结构的元素，利用 Hash 算法得到索引确定归属的数据段，也就是对应到在修改时需要竞争获取的锁。ConcurrentHashMap 支持 CurrencyLevel（Segment 数组数量）的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment
 *  核心数据如 value，以及链表都是 volatile 修饰的，保证了获取时的可见性
 *  首先是通过 key 定位到 Segment，之后在对应的 Segment 中进行具体的 put 操作如下：
    
     *  将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。
     *  遍历该 HashEntry，如果不为空则判断传入的  key 和当前遍历的 key 是否相等，相等则覆盖旧的 value
     *  不为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容
     *  最后会解除在 1 中所获取当前 Segment 的锁。
 *  虽然 HashEntry 中的 value 是用 volatile 关键词修饰的，但是并不能保证并发的原子性，所以 put 操作时仍然需要加锁处理

首先第一步的时候会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁。

*  尝试自旋获取锁
 *  如果重试的次数达到了 MAX\_SCAN\_RETRIES 则改为阻塞锁获取，保证能获取成功。最后解除当前 Segment 的锁

### 14、CocurrentHashMap（JDK 1.8） ###

CocurrentHashMap 抛弃了原有的 Segment 分段锁，采用了 `CAS + synchronized` 来保证并发安全性。其中的 `val next` 都用了 volatile 修饰，保证了可见性。

最大特点是引入了 CAS

借助 Unsafe 来实现 native code。CAS有3个操作数，内存值 V、旧的预期值 A、要修改的新值 B。当且仅当预期值 A 和内存值 V 相同时，将内存值V修改为 B，否则什么都不做。Unsafe 借助 CPU 指令 cmpxchg 来实现。

CAS 使用实例

对 sizeCtl 的控制都是用 CAS 来实现的：

*  \-1 代表 table 正在初始化
 *  N 表示有 -N-1 个线程正在进行扩容操作
 *  如果 table 未初始化，表示table需要初始化的大小
 *  如果 table 初始化完成，表示table的容量，默认是table大小的0.75倍，用这个公式算 0.75（n – (n >>> 2)）

CAS 会出现的问题：ABA

**解决：**对变量增加一个版本号，每次修改，版本号加 1，比较的时候比较版本号。

put 过程

*  根据 key 计算出 hashcode
 *  判断是否需要进行初始化
 *  通过 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功
 *  如果当前位置的 hashcode == MOVED == -1,则需要进行扩容
 *  如果都不满足，则利用 synchronized 锁写入数据
 *  如果数量大于 TREEIFY\_THRESHOLD 则要转换为红黑树

get 过程

*  根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值
 *  如果是红黑树那就按照树的方式获取值
 *  就不满足那就按照链表的方式遍历获取值

ConcurrentHashMap 在 Java 8 中存在一个 bug 会进入死循环，原因是递归创建 ConcurrentHashMap 对象，但是在 JDK 1.9 已经修复了。场景重现如下：

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 </td> 
 <td> <code>public</code> <code>class</code> <code>ConcurrentHashMapDemo{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>private</code> <code>Map&lt;Integer,Integer&gt; cache =</code><code>new</code> <code>ConcurrentHashMap&lt;&gt;(</code><code>15</code><code>);</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>static</code> <code>void</code> <code>main(String[]args){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ConcurrentHashMapDemo ch =&nbsp;&nbsp;&nbsp; </code><code>new</code> <code>ConcurrentHashMapDemo();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(ch.fibonaacci(</code><code>80</code><code>));&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>int</code> <code>fibonaacci(Integer i){&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(i==</code><code>0</code><code>||i ==</code><code>1</code><code>) {&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>i;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>cache.computeIfAbsent(i,(key) -&gt; { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"fibonaacci : "</code><code>+key);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>fibonaacci(key -</code><code>1</code><code>)+fibonaacci(key - </code><code>2</code><code>);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>});&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

### HashMap的源码： ###

**1，位桶数组：数组元素Node<K,V>实现了Entry接口**

transient Node<k,v>[] table;//存储（位桶）的数组</k,v>

**2，数组元素Node<K,V>实现了Entry接口 **

//Node是单向链表，它实现了Map.Entry接口 
 static class Node<k,v> implements Map.Entry<k,v> { 
 final int hash; 
 final K key; 
 V value; 
 Node<k,v> next; 
 //构造函数Hash值 键 值 下一个节点 
 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; 
 } 
 //判断两个node是否相等,若key和value都相等，返回true。可以与自身比较为true 
 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; 
 }

3，**源码中的数据域**

public class HashMap<k,v> extends AbstractMap<k,v> implements Map<k,v>, Cloneable, Serializable { 
 private static final long serialVersionUID = 362498820763181265L; 
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 
 static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量 
 static final float DEFAULT_LOAD_FACTOR = 0.75f;//填充比 
 //当add一个元素到某个位桶，其链表长度达到8时将链表转换为红黑树 
 static final int TREEIFY_THRESHOLD = 8; 
 static final int UNTREEIFY_THRESHOLD = 6; 
 static final int MIN_TREEIFY_CAPACITY = 64; 
 transient Node<k,v>[] table;//存储元素的数组 
 transient Set<map.entry<k,v>> entrySet; 
 transient int size;//存放元素的个数 
 transient int modCount;//被修改的次数fast-fail机制 
 int threshold;//临界值 当实际大小(容量*填充比)超过临界值时，会进行扩容 
 final float loadFactor;//填充比（......后面略）

**4，HashMap的构造函数**

HashMap的构造方法有4种，主要涉及到的参数有，指定初始容量，指定填充比和用来初始化的Map

//构造函数1 
 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)) 
 throw new IllegalArgumentException(Illegal load factor: + 
 loadFactor); 
 this.loadFactor = loadFactor; 
 this.threshold = tableSizeFor(initialCapacity);//新的扩容临界值 
 } 
 
 //构造函数2 
 public HashMap(int initialCapacity) { 
 this(initialCapacity, DEFAULT_LOAD_FACTOR); 
 } 
 
 //构造函数3 
 public HashMap() { 
 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 
 } 
 
 //构造函数4用m的元素初始化散列映射 
 public HashMap(Map m) { 
 this.loadFactor = DEFAULT_LOAD_FACTOR; 
 putMapEntries(m, false); 
 }

**5，HashMap如何getValue值 **

get(key)方法时获取key的hash值，计算hash&(n-1)得到在链表数组中的位置first=tab\[hash&(n-1)\],先判断first的key是否与参数key相等，不等就遍历后面的链表找到相同的key值返回对应的Value值即可

public V get(Object key) { 
 Node<K,V> e; 
 return (e = getNode(hash(key), key)) == null ? null : e.value; 
 } 
 /** 
 * Implements Map.get and related methods 
 * 
 * @param hash hash for key 
 * @param key the key 
 * @return the node, or null if none 
 */ 
 final Node<K,V> getNode(int hash, Object key) { 
 Node<K,V>[] tab;//Entry对象数组 
 Node<K,V> first,e; //在tab数组中经过散列的第一个位置 
 int n; 
 K k; 
 /*找到插入的第一个Node，方法是hash值和n-1相与，tab[(n - 1) & hash]*/ 
 //也就是说在一条链上的hash值相同的 
 if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) { 
 /*检查第一个Node是不是要找的Node*/ 
 if (first.hash == hash && // always check first node 
 ((k = first.key) == key || (key != null && key.equals(k))))//判断条件是hash值要相同，key值要相同 
 return first; 
 /*检查first后面的node*/ 
 if ((e = first.next) != null) { 
 if (first instanceof TreeNode) 
 return ((TreeNode<K,V>)first).getTreeNode(hash, key); 
 /*遍历后面的链表，找到key值和hash值都相同的Node*/ 
 do { 
 if (e.hash == hash && 
 ((k = e.key) == key || (key != null && key.equals(k)))) 
 return e; 
 } while ((e = e.next) != null); 
 } 
 } 
 return null; 
 }

**6，红黑二叉树的结构**

//红黑树 
 static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> { 
 TreeNode<k,v> parent; // 父节点 
 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) { 
 super(hash, key, val, next); 
 } 
 
 //返回当前节点的根节点 
 final TreeNode<k,v> root() { 
 for (TreeNode<k,v> r = this, p;;) { 
 if ((p = r.parent) == null) 
 return r; 
 r = p; 
 } 
 }

**7，HashMap.put（key, value）插入方法**

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) {
 //p：链表节点 n:数组长度 i：链表所在数组中的索引坐标
 Node<K,V>[] tab; Node<K,V> p; int n, i;
 //判断tab[]数组是否为空或长度等于0，进行初始化扩容
 if ((tab = table) == null || (n = tab.length) == 0)
 n = (tab = resize()).length;
 //判断tab指定索引位置是否有元素，没有则，直接newNode赋值给tab[i]
 if ((p = tab[i = (n - 1) & hash]) == null)
 tab[i] = newNode(hash, key, value, null);
 //如果该数组位置存在Node
 else {
 //首先先去查找与待插入键值对key相同的Node，存储在e中，k是那个节点的key
 Node<K,V> e; K k;
 //判断key是否已经存在(hash和key都相等)
 if (p.hash == hash &&
 ((k = p.key) == key || (key != null && key.equals(k))))
 e = p;
 //如果Node是红黑二叉树，则执行树的插入操作
 else if (p instanceof TreeNode)
 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
 //否则执行链表的插入操作（说明Hash值碰撞了，把Node加入到链表中）
 else {
 for (int binCount = 0; ; ++binCount) {
 //如果该节点是尾节点，则进行添加操作
 if ((e = p.next) == null) {
 p.next = newNode(hash, key, value, null);
 //判断如果链表长度，如果链表长度大于8则调用treeifyBin方法，判断是扩容还是把链表转换成红黑二叉树
 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执行p的子节点，开始下一次循环（p = e = p.next）
 p = e;
 }
 }
 //在循环中判断e是否为null，如果为null则表示加了一个新节点，不是null则表示找到了hash、key都一致的Node。
 if (e != null) { // existing mapping for key
 V oldValue = e.value;
 //判断是否更新value值。（map提供putIfAbsent方法，如果key存在，不更新value，但是如果value==null任何情况下都更改此值）
 if (!onlyIfAbsent || oldValue == null)
 e.value = value;
 //此方法是空方法，什么都没实现，用户可以根据需要进行覆盖
 afterNodeAccess(e);
 return oldValue;
 }
 }
 //只有插入了新节点才进行++modCount；
 ++modCount;
 //如果size>threshold则开始扩容（每次扩容原来的1倍）
 if (++size > threshold)
 resize();
 //此方法是空方法，什么都没实现，用户可以根据需要进行覆盖
 afterNodeInsertion(evict);
 return null;
 }

1.判断键值对数组tab\[i\]是否为空或为null，否则执行resize()进行扩容；

2.根据键值key计算hash值得到插入的数组索引i，如果table\[i\]==null，直接新建节点添加，转向6，如果table\[i\]不为空，转向3；

3.判断链表（或二叉树）的首个元素是否和key一样，不一样转向④，相同转向6；

4.判断链表（或二叉树）的首节点 是否为treeNode，即是否是红黑树，如果是红黑树，则直接在树中插入键值对，不是则执行5；

5.遍历链表，判断链表长度是否大于8，大于8的话把链表转换为红黑树（还判断数组长度是否小于64，如果小于只是扩容，不进行转换二叉树），在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；如果调用putIfAbsent方法插入，则不更新值（只更新值为null的元素）。

6.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

final void treeifyBin(Node<K,V>[] tab, int hash) {
 int n, index; Node<K,V> e;
 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
 resize();
 else if ((e = tab[index = (n - 1) & hash]) != null) {
 TreeNode<K,V> hd = null, tl = null;
 do {
 TreeNode<K,V> p = replacementTreeNode(e, null);
 if (tl == null)
 hd = p;
 else {
 p.prev = tl;
 tl.next = p;
 }
 tl = p;
 } while ((e = e.next) != null);
 if ((tab[index] = hd) != null)
 hd.treeify(tab);
 }
 }

1、首先判断数组的长度是否小于64，如果小于64则进行扩容  
2、否则把链表结构转换成红黑二叉树结构

**8，HasMap的扩容机制resize();**

**构造hash表时，如果不指明初始大小，默认大小为16（即Node数组大小16），如果Node\[\]数组中的元素达到（填充比\*Node.length）重新调整HashMap大小 变为原来2倍大小,**扩容很耗时

/** 
 * Initializes or doubles table size. If null, allocates in 
 * accord with initial capacity target held in field threshold. 
 * Otherwise, because we are using power-of-two expansion, the 
 * elements from each bin must either stay at same index, or move 
 * with a power of two offset in the new table. 
 * 
 * @return the table 
 */ 
 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; 
 } 
 /*把新表的长度设置为旧表长度的两倍，newCap=2*oldCap*/ 
 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 
 oldCap >= DEFAULT_INITIAL_CAPACITY) 
 /*把新表的门限设置为旧表门限的两倍，newThr=oldThr*2*/ 
 newThr = oldThr << 1; // double threshold 
 } 
 /*如果旧表的长度的是0，就是说第一次初始化表*/ 
 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); 
 } 
 
 
 
 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;//把新表赋值给table 
 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)//说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置 
 newTab[e.hash & (newCap - 1)] = e; 
 else if (e instanceof TreeNode) 
 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 
 /*如果e后边有链表,到这里表示e后面带着个单链表，需要遍历单链表，将每个结点重*/ 
 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为偶数一队，e.hash&oldCap为奇数一对 
 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) {//lo队不为null，放在新表原位置 
 loTail.next = null; 
 newTab[j] = loHead; 
 } 
 if (hiTail != null) {//hi队不为null，放在新表j+oldCap位置 
 hiTail.next = null; 
 newTab[j + oldCap] = hiHead; 
 } 
 } 
 } 
 } 
 } 
 return newTab; 
 }

### modCount 变量的作用 ###

public final void forEach(Consumer<? super K> action) {
 Node<K,V>[] tab;
 if (action == null)
 throw new NullPointerException();
 if (size > 0 && (tab = table) != null) {
 int mc = modCount;
 for (int i = 0; i < tab.length; ++i) {
 for (Node<K,V> e = tab[i]; e != null; e = e.next)
 action.accept(e.key);
 }
 if (modCount != mc)
 throw new ConcurrentModificationException();
 }
 }

从forEach循环中可以发现 modCount 参数的作用。就是在迭代器迭代输出Map中的元素时，不能编辑（增加，删除，修改）Map中的元素。如果在迭代时修改，则抛出ConcurrentModificationException异常。

### 疑问解答： ###

1、hash取余数，为什么不用取模操作呢，而用tab\[i = (n - 1) & hash\]？

它通过 (n - 1) & hash来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时， (n - 1) & hash运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

2、为什么使用红黑二叉树呢？

因为在好的算法，也避免不了hash的碰撞，避免不了链表过长的的情况，一旦出现链表过长，则严重影响到HashMap的性能。JDK8对HashMap做了优化，把链表长度超过8个的，则改成红黑二叉树，提高访问的速度。

**JDK1.8使用红黑树的改进**

在[Java ][Java]jdk8中对HashMap的源码进行了优化，在jdk7中，HashMap处理“碰撞”的时候，都是采用链表来存储，当碰撞的结点很多时，查询时间是O（n）。  
在jdk8中，**HashMap处理“碰撞”增加了红黑树这种数据结构，当碰撞结点较少时，采用链表存储，当较大时（>8个），采用红黑树（特点是查询时间是O（logn））存储（有一个阀值控制，大于阀值(8个)，将链表存储转换成红黑树存储）**

![format_png 1][]

**问题分析：**

你可能还知道哈希碰撞会对hashMap的性能带来灾难性的影响。如果多个hashCode()的值落到同一个桶内的时候，这些值是存储到一个链表中的。最坏的情况下，所有的key都映射到同一个桶中，这样hashmap就退化成了一个链表——查找时间从O(1)到O(n)。

随着HashMap的大小的增长，get()方法的开销也越来越大。由于所有的记录都在同一个桶里的超长链表内，平均查询一条记录就需要遍历一半的列表。

**JDK1.8HashMap的红黑树是这样解决的**：

**如果某个桶中的记录过大的话（当前是TREEIFY\_THRESHOLD = 8），HashMap会动态的使用一个专门的treemap实现来替换掉它。这样做的结果会更好，是O(logn)，而不是糟糕的O(n)。**

它是如何工作的？前面产生冲突的那些KEY对应的记录只是简单的追加到一个链表后面，这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树，**使用哈希值作为树的分支变量，如果两个哈希值不等，但指向同一个桶的话，较大的那个会插入到右子树里。如果哈希值相等，HashMap希望key值最好是实现了Comparable接口的，这样它可以按照顺序来进行插入**。这对HashMap的key来说并不是必须的，不过如果实现了当然最好。如果没有实现这个接口，在出现严重的哈希碰撞的时候，你就并别指望能获得性能提升了。

[format_png]: /images/20220131/af7f3c4a9f6b47c3b5845b54c90c1232.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3c4OTM5MzI3NDc_size_16_color_FFFFFF_t_70]: /images/20220131/620631664a53491b910b61ddf221645e.png
[c3b34af2d13802399d5e61bb5b8cb87b.png]: /images/20220131/34e8f5485f674c7ba1d33ebba6c29a42.png
[c3b34af2d13802399d5e61bb5b8cb87b.png 1]: http://www.importnew.com/31278.html/1294463-20181119002141457-19724606
[fb98d75b501aafb9109ce705a3118cae.png]: /images/20220131/1d2ee8268fa8446cbbb10e42cfee94b5.png
[fb98d75b501aafb9109ce705a3118cae.png 1]: http://www.importnew.com/31278.html/1294463-20181119224252423-2018084724
[cf94bb29c4b3cdb330ea4b57a6317187-300x216.png]: /images/20220131/8afc7ee6c25f4aa1b62639f33c40619d.png
[cf94bb29c4b3cdb330ea4b57a6317187-300x216.png 1]: http://www.importnew.com/31278.html/1294463-20181119224633228-1433434325
[Java]: http://lib.csdn.net/base/java
[format_png 1]: /images/20220131/9d503407c93e48b3aad295c97a2be245.png