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

墨蓝 2022-01-31 13:59 311阅读 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 的原理实现的

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

简化的模拟数据结构：








1

2

3

4

5

6

7

Node[] table = new Node[16]; // 散列桶初始化，table

class Node {

    hash; //hash值

    key; //键

    value; //值

    node next; //用于指向链表的下一层（产生冲突，用拉链法）

}

存储查找原理：

  • 存储：首先获取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冲突？

解决方法一：开放寻址法

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

通俗易懂的说法：

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

解决方法二：链地址法

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

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

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

format_png

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

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

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

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

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

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

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

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








1

2

3

4

5

6

7

8

9

10

11

static final int hash(Object key) {

    if (key == null){

        return 0;

    }

    int h;

    h = key.hashCode()；返回散列值也就是hashcode

    // ^ ：按位异或

    // >>>:无符号右移，忽略符号位，空位都以0补齐

    //其中n是数组的长度，即Map的数组部分初始化长度

    return (n-1)&(h ^ (h >>> 16));

}

fb98d75b501aafb9109ce705a3118cae.png

简单来说就是：

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

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

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

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

cf94bb29c4b3cdb330ea4b57a6317187-300x216.png

  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 已经修复了。场景重现如下：








1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

public class ConcurrentHashMapDemo{

    private Map<Integer,Integer> cache =new ConcurrentHashMap<>(15);

 

    public static void main(String[]args){

        ConcurrentHashMapDemo ch =    new ConcurrentHashMapDemo();

        System.out.println(ch.fibonaacci(80));       

    }

 

    public int fibonaacci(Integer i){       

        if(i==0||i ==1) {               

            return i;       

        }

 

        return cache.computeIfAbsent(i,(key) -> {

            System.out.println(“fibonaacci : “+key);

            return fibonaacci(key -1)+fibonaacci(key - 2);       

        });      

    }

}

HashMap的源码：

1，位桶数组：数组元素Node实现了Entry接口

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

2，数组元素Node实现了Entry接口 

  1. //Node是单向链表，它实现了Map.Entry接口  
  2. static class Node<k,v> implements Map.Entry<k,v> {  
  3.     final int hash;  
  4.     final K key;  
  5.     V value;  
  6.     Node<k,v> next;  
  7.     //构造函数Hash值 键 值 下一个节点  
  8.     Node(int hash, K key, V value, Node<k,v> next) {  
  9.         this.hash = hash;  
  10.         this.key = key;  
  11.         this.value = value;  
  12.         this.next = next;  
  13.     }  
  15.     public final K getKey()        { return key; }  
  16.     public final V getValue()      { return value; }  
  17.     public final String toString() { return key + = + value; }  
  19.     public final int hashCode() {  
  20.         return Objects.hashCode(key) ^ Objects.hashCode(value);  
  21.     }  
  23.     public final V setValue(V newValue) {  
  24.         V oldValue = value;  
  25.         value = newValue;  
  26.         return oldValue;  
  27.     }  
  28.     //判断两个node是否相等,若key和value都相等，返回true。可以与自身比较为true  
  29.     public final boolean equals(Object o) {  
  30.         if (o == this)  
  31.             return true;  
  32.         if (o instanceof Map.Entry) {  
  33.             Map.Entry<!--?,?--> e = (Map.Entry<!--?,?-->)o;  
  34.             if (Objects.equals(key, e.getKey()) &&  
  35.                 Objects.equals(value, e.getValue()))  
  36.                 return true;  
  37.         }  
  38.         return false;  
  39.     }

3，源码中的数据域 

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

4，HashMap的构造函数

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

  1. //构造函数1  
  2. public HashMap(int initialCapacity, float loadFactor) {  
  3.     //指定的初始容量非负  
  4.     if (initialCapacity < 0)  
  5.         throw new IllegalArgumentException(Illegal initial capacity:  +  
  6.                                            initialCapacity);  
  7.     //如果指定的初始容量大于最大容量,置为最大容量  
  8.     if (initialCapacity > MAXIMUM_CAPACITY)  
  9.         initialCapacity = MAXIMUM_CAPACITY;  
  10.     //填充比为正  
  11.     if (loadFactor <= 0 || Float.isNaN(loadFactor))  
  12.         throw new IllegalArgumentException(Illegal load factor:  +  
  13.                                            loadFactor);  
  14.     this.loadFactor = loadFactor;  
  15.     this.threshold = tableSizeFor(initialCapacity);//新的扩容临界值  
  16. }  
  18. //构造函数2  
  19. public HashMap(int initialCapacity) {  
  20.     this(initialCapacity, DEFAULT_LOAD_FACTOR);  
  21. }  
  23. //构造函数3  
  24. public HashMap() {  
  25.     this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted  
  26. }  
  28. //构造函数4用m的元素初始化散列映射  
  29. public HashMap(Map<!--? extends K, ? extends V--> m) {  
  30.     this.loadFactor = DEFAULT_LOAD_FACTOR;  
  31.     putMapEntries(m, false);  
  32. }

5，HashMap如何getValue值

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

  1. public V get(Object key) {  
  2.         Node<K,V> e;  
  3.         return (e = getNode(hash(key), key)) == null ? null : e.value;  
  4.     }  
  5.       /** 
  6.      * Implements Map.get and related methods 
  7.      * 
  8.      * @param hash hash for key 
  9.      * @param key the key 
  10.      * @return the node, or null if none 
  11.      */  
  12.     final Node<K,V> getNode(int hash, Object key) {  
  13.         Node<K,V>[] tab;//Entry对象数组  
  14.     Node<K,V> first,e; //在tab数组中经过散列的第一个位置  
  15.     int n;  
  16.     K k;  
  17.     /*找到插入的第一个Node，方法是hash值和n-1相与，tab[(n - 1) & hash]*/  
  18.     //也就是说在一条链上的hash值相同的  
  19.         if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {  
  20.     /*检查第一个Node是不是要找的Node*/  
  21.             if (first.hash == hash && // always check first node  
  22.                 ((k = first.key) == key || (key != null && key.equals(k))))//判断条件是hash值要相同，key值要相同  
  23.                 return first;  
  24.       /*检查first后面的node*/  
  25.             if ((e = first.next) != null) {  
  26.                 if (first instanceof TreeNode)  
  27.                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);  
  28.                 /*遍历后面的链表，找到key值和hash值都相同的Node*/  
  29.                 do {  
  30.                     if (e.hash == hash &&  
  31.                         ((k = e.key) == key || (key != null && key.equals(k))))  
  32.                         return e;  
  33.                 } while ((e = e.next) != null);  
  34.             }  
  35.         }  
  36.         return null;  
  37.     }

6，红黑二叉树的结构

  1. //红黑树  
  2. static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> {  
  3.     TreeNode<k,v> parent;  // 父节点  
  4.     TreeNode<k,v> left; //左子树  
  5.     TreeNode<k,v> right;//右子树  
  6.     TreeNode<k,v> prev;    // needed to unlink next upon deletion  
  7.     boolean red;    //颜色属性  
  8.     TreeNode(int hash, K key, V val, Node<k,v> next) {  
  9.         super(hash, key, val, next);  
  10.     }  
  12.     //返回当前节点的根节点  
  13.     final TreeNode<k,v> root() {  
  14.         for (TreeNode<k,v> r = this, p;;) {  
  15.             if ((p = r.parent) == null)  
  16.                 return r;  
  17.             r = p;  
  18.         }  
  19.     }

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

  1. public V put(K key, V value) {
  2.         return putVal(hash(key), key, value, false, true);
  3.     }
  5.     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  6.                    boolean evict) {
  7.         //p：链表节点  n:数组长度   i：链表所在数组中的索引坐标
  8.         Node<K,V>[] tab; Node<K,V> p; int n, i;
  9.         //判断tab[]数组是否为空或长度等于0，进行初始化扩容
  10.         if ((tab = table) == null || (n = tab.length) == 0)
  11.             n = (tab = resize()).length;
  12.         //判断tab指定索引位置是否有元素，没有则，直接newNode赋值给tab[i]
  13.         if ((p = tab[i = (n - 1) & hash]) == null)
  14.             tab[i] = newNode(hash, key, value, null);
  15.         //如果该数组位置存在Node
  16.         else {
  17.             //首先先去查找与待插入键值对key相同的Node，存储在e中，k是那个节点的key
  18.             Node<K,V> e; K k;
  19.             //判断key是否已经存在(hash和key都相等)
  20.             if (p.hash == hash &&
  21.                 ((k = p.key) == key || (key != null && key.equals(k))))
  22.                 e = p;
  23.             //如果Node是红黑二叉树，则执行树的插入操作
  24.             else if (p instanceof TreeNode)
  25.                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  26.             //否则执行链表的插入操作（说明Hash值碰撞了，把Node加入到链表中）
  27.             else {
  28.                 for (int binCount = 0; ; ++binCount) {
  29.                     //如果该节点是尾节点，则进行添加操作
  30.                     if ((e = p.next) == null) {
  31.                         p.next = newNode(hash, key, value, null);
  32.                         //判断如果链表长度，如果链表长度大于8则调用treeifyBin方法，判断是扩容还是把链表转换成红黑二叉树
  33.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  34.                             treeifyBin(tab, hash);
  35.                         break;
  36.                     }
  37.                     //如果键值存在，则退出循环
  38.                     if (e.hash == hash &&
  39.                         ((k = e.key) == key || (key != null && key.equals(k))))
  40.                         break;
  41.                     //把p执行p的子节点，开始下一次循环（p = e = p.next）
  42.                     p = e;
  43.                 }
  44.             }
  45.             //在循环中判断e是否为null，如果为null则表示加了一个新节点，不是null则表示找到了hash、key都一致的Node。
  46.             if (e != null) { // existing mapping for key
  47.                 V oldValue = e.value;
  48.                 //判断是否更新value值。（map提供putIfAbsent方法，如果key存在，不更新value，但是如果value==null任何情况下都更改此值）
  49.                 if (!onlyIfAbsent || oldValue == null)
  50.                     e.value = value;
  51.                 //此方法是空方法，什么都没实现，用户可以根据需要进行覆盖
  52.                 afterNodeAccess(e);
  53.                 return oldValue;
  54.             }
  55.         }
  56.         //只有插入了新节点才进行++modCount；
  57.         ++modCount;
  58.         //如果size>threshold则开始扩容（每次扩容原来的1倍）
  59.         if (++size > threshold)
  60.             resize();
  61.         //此方法是空方法，什么都没实现，用户可以根据需要进行覆盖
  62.         afterNodeInsertion(evict);
  63.         return null;
  64.     }

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，如果超过，进行扩容。

  1. final void treeifyBin(Node<K,V>[] tab, int hash) {
  2.         int n, index; Node<K,V> e;
  3.         if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
  4.             resize();
  5.         else if ((e = tab[index = (n - 1) & hash]) != null) {
  6.             TreeNode<K,V> hd = null, tl = null;
  7.             do {
  8.                 TreeNode<K,V> p = replacementTreeNode(e, null);
  9.                 if (tl == null)
  10.                     hd = p;
  11.                 else {
  12.                     p.prev = tl;
  13.                     tl.next = p;
  14.                 }
  15.                 tl = p;
  16.             } while ((e = e.next) != null);
  17.             if ((tab[index] = hd) != null)
  18.                 hd.treeify(tab);
  19.         }
  20.     }

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

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

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

  1. /** 
  2.     * Initializes or doubles table size.  If null, allocates in 
  3.     * accord with initial capacity target held in field threshold. 
  4.     * Otherwise, because we are using power-of-two expansion, the 
  5.     * elements from each bin must either stay at same index, or move 
  6.     * with a power of two offset in the new table. 
  7.     * 
  8.     * @return the table 
  9.     */  
  10.    final Node<K,V>[] resize() {  
  11.        Node<K,V>[] oldTab = table;  
  12.        int oldCap = (oldTab == null) ? 0 : oldTab.length;  
  13.        int oldThr = threshold;  
  14.        int newCap, newThr = 0;  
  16. /*如果旧表的长度不是空*/  
  17.        if (oldCap > 0) {  
  18.            if (oldCap >= MAXIMUM_CAPACITY) {  
  19.                threshold = Integer.MAX_VALUE;  
  20.                return oldTab;  
  21.            }  
  22. /*把新表的长度设置为旧表长度的两倍，newCap=2*oldCap*/  
  23.            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  
  24.                     oldCap >= DEFAULT_INITIAL_CAPACITY)  
  25.       /*把新表的门限设置为旧表门限的两倍，newThr=oldThr*2*/  
  26.                newThr = oldThr << 1; // double threshold  
  27.        }  
  28.     /*如果旧表的长度的是0，就是说第一次初始化表*/  
  29.        else if (oldThr > 0) // initial capacity was placed in threshold  
  30.            newCap = oldThr;  
  31.        else {               // zero initial threshold signifies using defaults  
  32.            newCap = DEFAULT_INITIAL_CAPACITY;  
  33.            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  
  34.        }  
  38.        if (newThr == 0) {  
  39.            float ft = (float)newCap * loadFactor;//新表长度乘以加载因子  
  40.            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?  
  41.                      (int)ft : Integer.MAX_VALUE);  
  42.        }  
  43.        threshold = newThr;  
  44.        @SuppressWarnings({"rawtypes","unchecked"})  
  45. /*下面开始构造新表，初始化表中的数据*/  
  46.        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];  
  47.        table = newTab;//把新表赋值给table  
  48.        if (oldTab != null) {//原表不是空要把原表中数据移动到新表中      
  49.            /*遍历原来的旧表*/        
  50.            for (int j = 0; j < oldCap; ++j) {  
  51.                Node<K,V> e;  
  52.                if ((e = oldTab[j]) != null) {  
  53.                    oldTab[j] = null;  
  54.                    if (e.next == null)//说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置  
  55.                        newTab[e.hash & (newCap - 1)] = e;  
  56.                    else if (e instanceof TreeNode)  
  57.                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);  
  58. /*如果e后边有链表,到这里表示e后面带着个单链表，需要遍历单链表，将每个结点重*/  
  59.                    else { // preserve order保证顺序  
  60.                 新计算在新表的位置，并进行搬运  
  61.                        Node<K,V> loHead = null, loTail = null;  
  62.                        Node<K,V> hiHead = null, hiTail = null;  
  63.                        Node<K,V> next;  
  65.                        do {  
  66.                            next = e.next;//记录下一个结点  
  67.           //新表是旧表的两倍容量，实例上就把单链表拆分为两队，  
  68. 　　　　　　　　　　　　　//e.hash&oldCap为偶数一队，e.hash&oldCap为奇数一对  
  69.                            if ((e.hash & oldCap) == 0) {  
  70.                                if (loTail == null)  
  71.                                    loHead = e;  
  72.                                else  
  73.                                    loTail.next = e;  
  74.                                loTail = e;  
  75.                            }  
  76.                            else {  
  77.                                if (hiTail == null)  
  78.                                    hiHead = e;  
  79.                                else  
  80.                                    hiTail.next = e;  
  81.                                hiTail = e;  
  82.                            }  
  83.                        } while ((e = next) != null);  
  85.                        if (loTail != null) {//lo队不为null，放在新表原位置  
  86.                            loTail.next = null;  
  87.                            newTab[j] = loHead;  
  88.                        }  
  89.                        if (hiTail != null) {//hi队不为null，放在新表j+oldCap位置  
  90.                            hiTail.next = null;  
  91.                            newTab[j + oldCap] = hiHead;  
  92.                        }  
  93.                    }  
  94.                }  
  95.            }  
  96.        }  
  97.        return newTab;  
  98.    }

modCount 变量的作用

  1. public final void forEach(Consumer<? super K> action) {
  2.             Node<K,V>[] tab;
  3.             if (action == null)
  4.                 throw new NullPointerException();
  5.             if (size > 0 && (tab = table) != null) {
  6.                 int mc = modCount;
  7.                 for (int i = 0; i < tab.length; ++i) {
  8.                     for (Node<K,V> e = tab[i]; e != null; e = e.next)
  9.                         action.accept(e.key);
  10.                 }
  11.                 if (modCount != mc)
  12.                     throw new ConcurrentModificationException();
  13.             }
  14.         }

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

  1.                                          ![format_png 1][]

问题分析：

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

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

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

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

发表评论

表情：
评论列表 （有 0 条评论，311人围观）

还没有评论，来说两句吧...

相关阅读

    相关 HashMap实现原理及源码分析

    哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表，而Hash

    末蓝、末蓝、/ 0 赞/ 391 阅读

    相关 HashMap实现原理及源码分析

    　　哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的

    朱雀朱雀/ 0 赞/ 372 阅读