面试官问我HashMap哪里不安全,我憋了半天憋出了内伤?

2023-11-13

HashMap在JDK7和JDK8是有了一些不同的,具体体现如下:

  • JDK7HashMap底层是数组+链表,而JDK8是数组+链表+红黑树
  • JDK7扩容采用头插法,而JDK8采用尾插法
  • JDK7的rehash是全部rehash,而JDK8是部分rehash。
  • JDK8对于key的hash值计算相比于JDK7来说有所优化。

JDK7 HashMap

JDK7HashMap在多线程环境下会出现死循环问题。

假如此时A、B线程同时对一个HashMap进行put操作,且HashMap刚号达到扩容条件需要进行扩容

那么这两个线程都会取对HahsMap进行扩容(JDK7HashMap扩容调用 resize()方法,而resize()方法中需要调用transfer()方法将旧数组元素全部rehash到新数组中去重点:这里在多线程环境下就会出现问题)

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    //对数组的每一条链表遍历rehash
    for (Entry<K,V> e : table) {
        while(null != e) {
            //保留下一个节点
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            //得到对应在新数组中的索引位置
            int i = indexFor(e.hash, newCapacity);
            
            //尾插法
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

我们假设现在有一个链表 C——>D,且C、D扩容后计算的索引位置依然不变,那他么还在同一链表中

现在A线程进入到transfer方法拿到A和它的下一个节点B(Entry<K,V> next = e.next;)后,A线程被挂起,此时B线程正常走流程将A、Brehash到新的数组中,那么根据头插法在新的数组中是D——>C

B执行完之后,A线程继续去执行

因为A获取到了 e = C,next = D,所以C可以进行rehash,C进行完后拿到D,发现D.next = C,所以D也可以进行rehash,那么此时因为D——>C,此时会再拿到C,发现C.next = null,但C不是null,所以C再进行rehash,此时链表尾 C——> D ——>C,因为此时e = NULL,所以退出循环,此时出现死循环。C——>D——>C。

各位可以好好想想这些话或者自己在草稿纸上画一画再来看下面的图!

面试官问我HashMap哪里不安全,我憋了半天憋出了内伤?

B正常执行完成

面试官问我HashMap哪里不安全,我憋了半天憋出了内伤?

A继续执行

因为A获取到了 e = C,next = D,所以C可以进行rehash

面试官问我HashMap哪里不安全,我憋了半天憋出了内伤?

C进行完后拿到e = D,发现D.next = C,所以D也可以进行rehash

面试官问我HashMap哪里不安全,我憋了半天憋出了内伤?

那么此时因为D——>C,此时会再拿到C,发现C.next = null,但C不是null,所以C再进行rehash

面试官问我HashMap哪里不安全,我憋了半天憋出了内伤?

此时e = NULL,所以退出循环,此时出现死循环。C——>D——>C。

JDK8 HashMap

JDK1.8会出现数据覆盖的情况

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;
}

第6行代码:假设两个线程A、B都在进行put操作,并且根据key计算出的hash值相同,那么得到得索引下标也相同,当线程A执行完第六行代码后由于时间片耗尽导致被挂起,而线程B得到时间片后在该下标处插入了元素,完成了正常的插入,然后线程A获得时间片,由于之前已经进行了hash碰撞的判断,所有此时不会再进行判断,而是直接进行插入,这就导致了线程B插入的数据被线程A覆盖了,从而线程不安全。

第38行代码++size不安全,还是线程A、B,这两个线程同时进行put操作时,假设当前HashMap的zise大小为10,当线程A执行到第38行代码时,从主内存中获得size的值为10后准备进行+1操作,但是由于时间片耗尽只好让出CPU,线程B快乐的拿到CPU还是从主内存中拿到size的值10进行+1操作,完成了put操作并将size=11写回主内存,然后线程A再次拿到CPU并继续执行(此时size的值仍为10),当执行完put操作后,还是将size=11写回内存,此时,线程A、B都执行了一次put操作,但是size的值只增加了1,所有说还是由于数据覆盖又导致了线程不安全。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

面试官问我HashMap哪里不安全,我憋了半天憋出了内伤? 的相关文章

  • Gradle 构建错误:无法从 https://repo1.maven.org/maven2/io/fabric/tools/gradle/maven-metadata.xml 加载 Maven 元数据

    我在 Android studio 中遇到 gradle 构建错误 如下所示 Error A problem occurred configuring project MyApp Could not resolve all dependen
  • 序列的排列?

    我有具体数量的数字 现在我想以某种方式显示这个序列的所有可能的排列 例如 如果数字数量为3 我想显示 0 0 0 0 0 1 0 0 2 0 1 0 0 1 1 0 1 2 0 2 0 0 2 1 0 2 2 1 0 0 1 0 1 1 0
  • .properties 中的通配符

    是否存在任何方法 我可以将通配符添加到属性文件中 并且具有所有含义 例如a b c d lalalala 或为所有以结尾的内容设置一个正则表达式a b c anything 普通的 Java 属性文件无法处理这个问题 不 请记住 它实际上是
  • 在 Jar 文件中运行 ANT build.xml 文件

    我需要使用存储在 jar 文件中的 build xml 文件运行 ANT 构建 该 jar 文件在类路径中可用 是否可以在不分解 jar 文件并将 build xml 保存到本地目录的情况下做到这一点 如果是的话我该怎么办呢 Update
  • 谷歌应用程序引擎会话

    什么是java应用程序引擎 默认会话超时 如果我们将会话超时设置为非常非常长的时间 会不会产生不良影响 因为谷歌应用程序引擎会话默认情况下仅存储在数据存储中 就像facebook一样 每次访问该页面时 会话仍然永远存在 默认会话超时设置为
  • 在接口中使用默认方法是否违反接口隔离原则?

    我正在学习 SOLID 原则 ISP 指出 客户端不应被迫依赖于他们所使用的接口 不使用 在接口中使用默认方法是否违反了这个原则 我见过类似的问题 但我在这里发布了一个示例 以便更清楚地了解我的示例是否违反了 ISP 假设我有这个例子 pu
  • 来自 dll 的 Java 调用函数

    我有这个 python 脚本导入zkemkeeperdll 并连接到考勤设备 ZKTeco 这是我正在使用的脚本 from win32com client import Dispatch zk Dispatch zkemkeeper ZKE
  • Java 集合的并集或交集

    建立并集或交集的最简单方法是什么Set在 Java 中 我见过这个简单问题的一些奇怪的解决方案 例如手动迭代这两个集合 最简单的单行解决方案是这样的 set1 addAll set2 Union set1 retainAll set2 In
  • Eclipse Maven Spring 项目 - 错误

    I need help with an error which make me crazy I started to study Java EE and I am going through tutorial on youtube Ever
  • Hibernate 的 PersistentSet 不使用 hashCode/equals 的自定义实现

    所以我有一本实体书 public class Book private String id private String name private String description private Image coverImage pr
  • 像 Java 这样的静态类型语言中动态方法解析背后的原因是什么

    我对 Java 中引用变量的动态 静态类型和动态方法解析的概念有点困惑 考虑 public class Types Override public boolean equals Object obj System out println i
  • 如何在用户输入数据后重新运行java代码

    嘿 我有一个基本的java 应用程序 显示人们是成年人还是青少年等 我从java开始 在用户输入年龄和字符串后我找不到如何制作它它们被归类为 我希望它重新运行整个过程 以便其他人可以尝试 的节目 我一直在考虑做一个循环 但这对我来说没有用
  • 当 OnFocusChangeListener 应用于包装的 EditText 时,TextInputLayout 没有动画

    不能比标题说得更清楚了 我有一个由文本输入布局包裹的 EditText 我试图在 EditText 失去焦点时触发一个事件 但是 一旦应用了事件侦听器 TextInputLayout 就不再对文本进行动画处理 它只是位于 editText
  • 如何访问JAR文件中的Maven资源? [复制]

    这个问题在这里已经有答案了 我有一个使用 Maven 构建的 Java 应用程序 我有一个资源文件夹com pkg resources 我需要从中访问文件 例如directory txt 我一直在查看各种教程和其他答案 但似乎没有一个对我有
  • Eclipse 选项卡宽度不变

    我浏览了一些与此相关的帖子 但它们似乎并不能帮助我解决我的问题 我有一个项目 其中 java 文件以 2 个空格的宽度缩进 我想将所有内容更改为 4 空格宽度 我尝试了 正确的缩进 选项 但当我将几行修改为 4 空格缩进时 它只是将所有内容
  • 使用 AsyncTask 传递值

    我一直在努力解决这个问题 但我已经到了不知道该怎么办的地步 我想做的是使用一个类下载文件并将其解析为字符串 然后将该字符串发送到另一个类来解析 JSON 内容 所有部件都可以单独工作 并且我已经单独测试了所有部件 我只是不知道如何将值发送到
  • java.io.Serialized 在 C/C++ 中的等价物是什么?

    C C 的等价物是什么java io Serialized https docs oracle com javase 7 docs api java io Serializable html 有对序列化库的引用 用 C 序列化数据结构 ht
  • Cucumber 0.4.3 (cuke4duke) 与 java + maven gem 问题

    我最近开始为 Cucumber 安装一个示例项目 并尝试使用 maven java 运行它 我遵循了这个指南 http www goodercode com wp using cucumber tests with maven and ja
  • 使用 CXF-RS 组件时,为什么我们使用 而不是普通的

    作为后续这个问题 https stackoverflow com questions 20598199 对于如何正确使用CXF RS组件我还是有点困惑 我很困惑为什么我们需要
  • Spring Rest 和 Jsonp

    我正在尝试让我的 Spring Rest 控制器返回jsonp但我没有快乐 如果我想返回 json 但我有返回的要求 完全相同的代码可以正常工作jsonp我添加了一个转换器 我在网上找到了用于执行 jsonp 转换的源代码 我正在使用 Sp

随机推荐