HashMap源码分析 JDK1.8

Stella981
• 阅读 730

本文按以下顺序叙述:

  • HashMap的感性认识.
  • 官方文档中对HashMap介绍的解读.
  • 到源码中看看HashMap这些特性到底是如何实现的.

把源码啃下来有一种很爽的感觉, 相信你读完后也能体会到~ 如发现有误, 欢迎指出.


在开始之前, 先通过图例对HashMap建立感性认识

- 如果不清楚哈希表是一种什么样的数据结构的话, 可以先看书了解一下, 如果觉得看书麻烦, 推荐看一下浙大数据公开课中的\[第十一讲 散列查找\](https://www.icourse163.org/course/zju0901-93001?from=study), 了解了这种数据结构后理解HashMap就没有问题了. HashMap源码分析 JDK1.8
  • HashMap由一个数组组成, 对于每个键值对, 会通过对键进行哈希计算, 直接得出该键值对存储的位置, 保证了存取键值的操作拥有极其优良的时间性能.
  • 当两个键值对存储的位置发生冲突时, 会通过链表把键值对在对应的位置上用链表连起来. 如果链太长的话, (在JDK1.8后)会把链表转换为存取效率更高的红黑树, 以保证HashMap的整体存取效率.
  • HashMap中有专门记录容量的参数, 如果容量增大到一定的值会进行扩容, 使得HashMap散列更均匀, 整体存取效率更高.

下面是基于官方文档的粗糙翻译

- HashMap和Hashtable是相似的, 只不过它是线程不安全的, 并且允许null值. 它不能保证键值对的有序性, 键值对的顺序甚至会在使用的过程中发生变化 (扩容等操作会重新进行哈希操作, 键值对的位置发生变化). - 在哈希函数能散列均匀的前提下, 它能保证put和get两个基本操作有稳定的时间性能. - 遍历HashMap所需要的时间和它的容量是成正比的, 如果迭代性能很重要, 请不要把初始容量设置得过高(或把负载因子设置得过小, 过小则会经常进行重新哈希的操作). - 两个参数影响着HashMap的性能: 初始容量和负载因子. 这里的初始容量指创建Hash表时所开辟的内存空间. 负载因子是一个小数, 用于判断HashMap是否已经满了. 当map中的元素超过了负载因子和当前容量的乘积后, HashMap会进行扩容, 大概扩为原来大小的两倍. (比如说负载因子是0.75, 初始容量是100, 当实际容量达到\`0.75\*100=75\`时, HashMap就会进行扩容) - 一般来说, 默认负载因子(0.75)在时间和空间成本之间提供了很好的平衡。设置一个更大的负载因子值虽然节省了空间,但是增加了查找的时间成本(查找时间的增加会影响HashMap的大部分操作,包括get和set),所以在设置HashMap的初始容量的时候要考虑map中预期的装填元素数量和负载因子的大小,以最大限度减少扩容的次数. - 要注意的是HashMap是线程不安全的, 官方建议从外部实现对HashMap的同步操作, 官方给出的建议是 \`Map m = Collections.synchronizedMap(new HashMap(...));\` 当然也可以用\`ConcurrentHashMap\`替代. - 使用iterator迭代器遍历HashMap时有一个fail-fast快速容错机制. 在使用迭代器遍历容器的过程中, 任何对HashMap结构进行修改的都会导致\`ConcurrentModificationException\`并发修改异常. 如果不想这个异常出现, 但又想删除某个元素, 就要调用iterator迭代器自身的\`remove\`方法. 如果没有这个机制, 在迭代的过程中增删元素可能会导致HashMap结构的变更(比如扩容), 继续遍历的时候便会出错, 这一机制把这种风险扼杀在摇篮中.

源码分析

1. HashMap的创建

在创建HashMap之前, 先看看它的几个基本属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16, HashMap的默认初始容量

static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量, 如果在创建HashMap时显示指定HashMap的大小, 则不能超过这个值, 否则会默认使用这个值

static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认负载因子

static final int MIN_TREEIFY_CAPACITY = 64;//当HashMap的容量大于这个值, 一个位置冲突过多时才能转为红黑树, 否则解决冲突过多的方式是扩容

static final int TREEIFY_THRESHOLD = 8;//冲突时元素会用链表连起来, 当链表的长度达到了这个值, 就会转换为红黑树

static final int UNTREEIFY_THRESHOLD = 6;//当红黑树的结点数量少于这个值的时候, 会转换回链表. 

/**
 * The next size value at which to resize (capacity * load factor).
 */
int threshold;  //当前容量与负载因子的乘积, 用于判断是否要扩容.
  • HashMap一共有4个构造器. 这里只给出了无参构造, 如果清楚HashMap的使用环境, 可以使用其他有参构造设定初始容量和负载因子.

  • 如果使用无参构造创建HashMap, 会把负载因子设置为0.75, 其他额外的属性都按照默认值进行初始化.

    /**

    • The load factor used when none specified in constructor.

    */ static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**

    • The load factor for the hash table.
    • @serial

    */ final float loadFactor;

    //无参构造 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }

  • 至此, HashMap创建完毕. 在创建HashMap的时候, 并没有为数组分配空间, 那么这些必要步骤什么时候做呢? 请继续看...

2. HashMap的使用

  • HashMap的使用, 无非就是键值对的存储了, 先看存的代码.

    public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

  • 我们发现在调用put()方法的时候其实调用的是putVal()方法.

  • putVal()是个重要的方法, 通过方法, 我们能对HashMap有个深入的理解.

    /**

    • Implements Map.put and related methods
    • @param hash hash for key key的hash code经过再次计算后得出hash值.
    • @param key the key key值
    • @param value the value to put value值
    • @param onlyIfAbsent if true, don't change existing value
    • @param evict if false, the table is in creation mode.
    • @return previous value, or null if none

    */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; 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 { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); 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; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

  • 分析如下:

    Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;

  • 首先判断table是否为空, 如果为空的话会调用resize()方法, 完成对HashMap的初始化, 为HashMap中的数组分配内存空间.

  • resize()有两个作用: 1. 对HashMap进行初始化; 2. 进行两倍的扩容.


这里插入resize()方法的分析, 如需跳过, 点击这里
    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;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        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; //如果是初始化HashMap, 到这里就够了, 会跳过if判断并返回
        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;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    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;
                            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) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
  • 首先判断HashMap容量是否超过了默认的最大值, 如果是就不会进行扩容, 并返回原表.

  • 然后确定新表的大小newCap, 确定新表的threshold值(用于判断是否要扩容)newThr.

  • 确定好这两个值后, 如果是初始化HashMap, 由于原表为空oldTab == null, resize()函数也就结束了, 返回初始好的新表.

  • 如果oldTab != null, 也就说这次调用resize()是进行扩容, 那么在创建好新表后, 就要把原来的数据重新计算并搬运到新表中.

  • 搬运数据的过程还是蛮有意思的, 分析如下:

    在HashMap中计算元素存放位置的代码是 (n - 1) & hash 其中n是哈希表数组的长度, 这行代码保证了元素能落在数组的下标范围内 现在我们要进行扩容, 假设hash值为101010 初始容量 n = 16 , 计算地址: (n - 1) & hash = 1111 & 101010 = 001010 扩后容量 n = 32 , 计算地址: (n - 1) & hash = 11111 & 101010 = 001010 我们发现hash值为101010的时候计算出来的地址是一样的, 那么这个元素就不用挪位了.

    再举例: 假设当前元素hash值为1010101 初始容量 n = 16 , 计算地址: (n - 1) & hash = 1111 & 1010101 = 0000101 扩后容量 n = 32 , 计算地址: (n - 1) & hash = 11111 & 1010101 = 0010101 我们发现这时两个地址不相等, 新地址为: 原地址 + 原长度 (0000101 + 16) = 0010101

    这是一个精心的设计, 是这样的: 原来计算地址时 : (n - 1) = 1111 一共有4位 扩容后计算地址 : (n - 1) = 11111 多了一位, 多在了第五位 回头看hash值 第一个hash值: 101010. 第五位为0 第二个hash值: 1010101. 第五位为1 设计的原理就是: 在计算地址的时候, (n - 1)会比原来多了一位, 假设多的是第n位. 如果hash值的第n位为0那么元素就不用移动, 如果为1, 就要移动到新位置.

    所以从严谨的角度看, 扩容的时候不是对每个元素重新计算哈希, 而是把每个位置上的元素分成两类调整位置.

    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; if ((e.hash & oldCap) == 0) {//判断第n位是否为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) { loTail.next = null; newTab[j] = loHead;//在原位放好不用动的 } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead;//移动的位置: 原位置 + 原长度 } }


下面继续是\`putVal()\`的分析
\`\`\`java if ((p = tab\[i = (n - 1) & hash\]) == null) tab\[i\] = newNode(hash, key, value, null); \`\`\` - 拿到数组后, 根据hash值计算插入地址\`tab\[i = (n - 1) & hash\]\`, 如果该地址中没有元素, 就直接插入. 插入完判断需不需要扩容\`if (++size > threshold)\`, 如果需要就扩容, 不需要的话本次\`put()\`方法就结束了, 返回null. - 如果插入的地方已经有元素了, 也就是发生了冲突. \`\`\`java if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; \`\`\` - 首先会判断Key是否相同, 如果相同, 就就行判断是否能替换值, 能就替换 \`\`\` if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null)//在日常使用中, 基本新value都会替换旧value e.value = value; afterNodeAccess(e); return oldValue; } \`\`\` - 如果不相同, 就要寻找插入的位置, 如果当前桶里装的是链表, 则遍历链表(遍历的过程中仍会判断是否有相同的key), 如果装的是红黑树, 则按照红黑树的策略寻找插入点(期间仍会判断是否有相同的key). \`\`\` else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); 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; } }
- 补充: 在桶里装链表的情况下, 插入元素后会判断链表的长度有没有达到转换为红黑树的要求. 如果达到了就调用`treeifyBin()`方法. 
- 但注意: 并不是调用了`treeifyBin()`就会把桶中的结构转换为红黑树. 回想一下文章开头提及的基本参数, 有一个参数是`MIN_TREEIFY_CAPACITY`, 如果当前数组长度还没有达到这个参数的值, 是不会转换结构的, 会进行扩容`resize()`. 

---

> 结束

- 看到这里, HashMap在你的面前应该是没有什么秘密了. 
- 曾经看过一个有关HashMap并发造成死循环的问题. 左耳朵耗子的博客中有详细的描述, [点此跳转](https://coolshell.cn/articles/9606.html)
- 但是这个问题在JDK1.8中已经处理了. 造成死循环的原因是扩容时重新插入链表时是倒序插入的, JDK1.8中用了两条链表分别操作, 保证了链表插入到Map时还是按顺序插入的, 避免了死循环.
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
9个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这