【jdk 源码】concurrenthashmap 中静态代码块中altThreshold 的说明

本贴最后更新于 2808 天前,其中的信息可能已经时移世改

源码阅读过程中 在concurrenthashmap  类 遇见altThreshold   变量的查阅

 

ChangeLog:

  • 20131119日,更新了Java8版本中的变化。
  • 0131128日,更新了Java 7u40版本中的变化。(感谢Sunny Chan以及他的同事提示我关注新版本的JDK

共享一个基础char[] 

原先的String类中有4个非静态变量:

  • char[] value用于存储字符串。
  • int offset用于记录字符串首字母在value数组中对应的下标。
  • int count用于记录字符串的长度。
  • int hash用于缓存该字符串的哈希值。

正如你所看到的,绝大多数String对象都会是offset=0并且count=value.length。除非通过调用String.substring方法创建的String对象,或是间接调用Pattern.split这类API创建对象。

String.substring创建的String对象将和原String对象共享同一个内部变量char[] value,这样设计的好处是:

  1. 通过共享字符串节省内存开销。
  2. String.substring方法的时间复杂度为O(1)。

然而,这样的设计有可能会导致内存泄露:如果你从一个长度很长的String对象中提取出一个很短的子串,当这个String对象不再需要时(该对象静候GC回收),你的子串中还保持着这个String对象中存储着完整字符串的char[] value数组的引用。这种情况的解决方法是通过构造函数new String(String)创建一个新的子串对象,进而解除短子串与长母串之间的依赖关系。

自Java 1.7.0_06版本起(包括Java 8的最新版本),String类中不再有offset和count变量。这意味着成员变量char[] value将不会被共享。你可以忘记上述有关内存泄露的描述以及如何使用new String(String)方法来避免内存泄露的发生。但需要记住的是,String.substring现在是线性级的时间复杂度,不再是常数级的时间复杂度。

哈希算法的改变

下面的部分仅适用于Java 7u6以上的Java 7版本,这些代码在Java 8中已被删除。

String类在本次更新中的另一个变化是一个新的哈希算法。Oracle表示新的算法能生成出更好的哈希分布,并且能够提高基于哈希算法的容器的性能,如HashMap、Hashtable、HashSet、 LinkedHashMap、LinkedHashSet、WeakHashMap和ConcurrentHashMap 。与本文第一部分介绍的变化不同,这部分变化是试验性质的,默认是关闭的。

你可能已经猜到了,这部分变化只适用于String类型的Key。如果想要启用它们,需要将系统变量jdk.map.althashing.threshold设置为一个非负的整数值(默认为-1)。当使用新的哈希方法时,这个值将是容器大小的阈值。这里需要注意的是:哈希方法只有在进行重哈希(rehash)的时候才会被更新。因此,如果容器上次执行重哈希是在size=160的时候,而jdk.map.althashing.threshold = 200,这样只有在容器的size增长到大约320的时候,哈希方法才会被更新。

String类现在有一个hash32()方法,它的结果被缓存在成员变量int hash32 中。这个方法最大的变化是,同一个字符串在不同的JVM上执行hash32()的结果可能不同(确切的说,多数情况下都会不同,因为其内部分别调用了一次System.currentTimeMillis()和两次System.nanoTime()用于初始化seed)。因此,某些容器在每次运行程序时迭代顺序都不同。

事实上,我对这个方法的改变有一点意外。如果原先的hashCode方法运行的很好,为什么我们需要一个新的哈希方法呢?我决定使用文章hashcode方法性能调优中的测试程序,测试一下使用hash32方法会产生多少个重复的哈希值。

String.hash32()方法不是公有的,因此我只能通过查看HashMap的源码来找到调用String.hash32()的方法。答案是issun.misc.Hashing.stringHash32(String)。

使用同一数据集(由1百万个各不相同的Key组成)进行测试,String.hash32生成了304个重复的哈希值,而相比之下String.hashCode并没有生成重复的哈希值。我想我们需要静候Oracle进一步的完善或者更多的使用场景说明。

新的哈希算法可能会严重影响高并发、多线程代码

本章节适用于Java 7版本的build 6(包含build 6)至build40(不包含build40)。这部分代码在Java 8中已被删除。有关Java 7u40以上版本的相关介绍请参见下一个章节。

Oracle在后面这些类的哈希实现中遗留了一个bug HashMap、Hashtable、HashSet、LinkedHashMap、LinkedHashSet和WeakHashMap,只有ConcurrentHashMap 不受影响。这是因为所有的非concurrent类中现在都引入了下面的成员变量:

/**
 * A randomizing value associated with this instance that is applied to
 * hash code of keys to make hash collisions harder to find.
 */
transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);

这意味着每一个map或set实例创建的过程中都会调用sun.misc.Hashing.randomHashSeed方法。randomHashSeed后续会调用java.util.Random.nextInt方法。Random类以其多线程环境下不友好而闻名:它有一个Atomic类型的成员变量private final AtomicLong seedfield。Atomic类型在多线程竞争程度较低或者适中的场景下性能表现较好,但在竞争激烈的场景下性能很差。

因此,很多处理HTTP/JSON/XML请求的高负载Web应用可能会被这个bug所影响,因为现有的解析器在表示名值对(name-value)时几乎都使用了上述的存在bug的容器。这些解析器还很可能使用了嵌套的map,这会进一步增加每秒中创建map实例的数量。

如何解决这一问题呢?

1. 使用ConcurrentHashMap :只有在设置系统变量jdk.map.althashing.threshold时才会调用randomHashSeed 方法。但很可惜的是,这种方式仅适用于JDK的核心开发者。

/**
 * A randomizing value associated with this instance that is applied to
 * hash code of keys to make hash collisions harder to find.
 */
private transient final int hashSeed = randomHashSeed(this);

private static int randomHashSeed(ConcurrentHashMap instance) {
if (sun.misc.VM.isBooted() && Holder.ALTERNATIVE_HASHING) {
return sun.misc.Hashing.randomHashSeed(instance);
}

return 0;

}

2. Hacker的方式:修改sun.misc.Hashing类,这种方式极度不推荐。但如果你依然想解决这个bug,解决的思路是:java.util.Random类并不是final的。你可以在Java 7中加入Random 类的一个Thread Local的子类:java.util.concurrent.ThreadLocalRandom,它内部使用了ThreadLocal<ThreadLocalRandom>(感谢Benjamin Possolo指出我在之前的文章中遗漏了这个类的介绍)。除此之外,ThreadLocalRandom属于CPU cache感知型:每个ThreadLocalRandom实例的seed后面增加了64字节的填充(cache行的大小),进而降低2个不同的seed在同一个cache行中碰撞的可能性。

然后你可以修改成员变量sun.misc.Hashing.Holder.SEED_MAKER,将它初始化为Random子类的实例(ThreadLocalRandom)。不用担心这个变量是私有的、静态的而且是final的,反射机制可以帮你

public class Hashing {
    private static class Holder {
        static final java.util.Random SEED_MAKER;

Java 7u40以上的版本中新的哈希算法不再影响高并发、多线程代码

OracleJava 7u40版本中修正了上述的bug

他们使用了上一章节中提到的方法一,仅在重哈希阀值被启用时(通过设置系统变量jdk.map.althashing.threshold启用)才调用sun.misc.Hashing.randomHashSeed方法。Oracle只修改了两个类:HashMap和Hashtable,进而间接修改了 HashSet、LinkedHashMap和LinkedHashSet,因为这三个类是基于HashMap实现的。唯一没有被修改的类是WeakHashMap,但我实在想不出这个类会被大量实例化的应用场景。

相关文章

最近,本文在Reddit上引起了激烈的讨论。我推荐读者们去看一看:

总结

  • 自Java 1.7.0_06版本起,String.substring方法会为每个子串创建一个新的char[] value(而不是共享母串的char[] value)。这意味着String.substring方法的时间复杂度由常数阶变为线性阶。这种变化的好处是String对象占用的内存稍微少了一些(比以前少8个字节),同时确保String.substring方法不会导致内存泄漏(有关Java对象内存布局的详细信息,请见String packing part 1: converting characters to bytes)。
  • Java 7u6+版本中的功能,在Java 8中被删除。自Java 1.7.0_06版本起,String类有了第二个哈希函数:hash32。该方法目前还不是公有的,只能通过使用反射机制或者是调用sun.misc.Hashing.stringHash32(String)来访问该方法。只有当那7种哈希相关的JDK容器的大小超过系统变量jdk.map.althashing.threshold所设定的阀值时,该方法才会被使用。这是一个试验性质的功能,目前我不推荐在代码中使用这一功能。
  • Java 7u6 (包含Java 7u6)至Java 7u40(不包含Java 7u40)版本中的功能,不适用于Java 8新的哈希实现引入了一个性能上的bug,这个bug涉及Java 7u6 (包含Java 7u6)到Java 7u40(不包含Java 7u40)之间所有版本中所有标准的非concurrent的MapSet容器。这个bug只影响多线程应用每秒钟创建Map实例的效率。详情请见本文第三章节。Java 7u40版本已修复这个bug
  • JUC
    17 引用 • 3 回帖 • 1 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3165 引用 • 8206 回帖
  • 代码
    459 引用 • 591 回帖 • 8 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • ZeroNet

    ZeroNet 是一个基于比特币加密技术和 BT 网络技术的去中心化的、开放开源的网络和交流系统。

    1 引用 • 21 回帖 • 591 关注
  • Logseq

    Logseq 是一个隐私优先、开源的知识库工具。

    Logseq is a joyful, open-source outliner that works on top of local plain-text Markdown and Org-mode files. Use it to write, organize and share your thoughts, keep your to-do list, and build your own digital garden.

    4 引用 • 55 回帖 • 6 关注
  • 机器学习

    机器学习(Machine Learning)是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。

    76 引用 • 37 回帖
  • 国际化

    i18n(其来源是英文单词 internationalization 的首末字符 i 和 n,18 为中间的字符数)是“国际化”的简称。对程序来说,国际化是指在不修改代码的情况下,能根据不同语言及地区显示相应的界面。

    7 引用 • 26 回帖 • 1 关注
  • Q&A

    提问之前请先看《提问的智慧》,好的问题比好的答案更有价值。

    6364 引用 • 28618 回帖 • 264 关注
  • Kotlin

    Kotlin 是一种在 Java 虚拟机上运行的静态类型编程语言,由 JetBrains 设计开发并开源。Kotlin 可以编译成 Java 字节码,也可以编译成 JavaScript,方便在没有 JVM 的设备上运行。在 Google I/O 2017 中,Google 宣布 Kotlin 成为 Android 官方开发语言。

    19 引用 • 33 回帖 • 22 关注
  • uTools

    uTools 是一个极简、插件化、跨平台的现代桌面软件。通过自由选配丰富的插件,打造你得心应手的工具集合。

    5 引用 • 13 回帖
  • jsDelivr

    jsDelivr 是一个开源的 CDN 服务,可为 npm 包、GitHub 仓库提供免费、快速并且可靠的全球 CDN 加速服务。

    5 引用 • 31 回帖 • 33 关注
  • PHP

    PHP(Hypertext Preprocessor)是一种开源脚本语言。语法吸收了 C 语言、 Java 和 Perl 的特点,主要适用于 Web 开发领域,据说是世界上最好的编程语言。

    164 引用 • 407 回帖 • 523 关注
  • 程序员

    程序员是从事程序开发、程序维护的专业人员。

    529 引用 • 3527 回帖
  • 创造

    你创造的作品可能会帮助到很多人,如果是开源项目的话就更赞了!

    171 引用 • 988 回帖
  • abitmean

    有点意思就行了

    14 关注
  • IDEA

    IDEA 全称 IntelliJ IDEA,是一款 Java 语言开发的集成环境,在业界被公认为最好的 Java 开发工具之一。IDEA 是 JetBrains 公司的产品,这家公司总部位于捷克共和国的首都布拉格,开发人员以严谨著称的东欧程序员为主。

    180 引用 • 400 回帖
  • Bug

    Bug 本意是指臭虫、缺陷、损坏、犯贫、窃听器、小虫等。现在人们把在程序中一些缺陷或问题统称为 bug(漏洞)。

    76 引用 • 1738 回帖 • 2 关注
  • Sillot

    Sillot (汐洛)孵化自思源笔记,致力于服务智慧新彖乄,具有彖乄驱动、极致优雅、开发者友好的特点
    Github 地址:https://github.com/Hi-Windom/Sillot

    12 引用 • 26 关注
  • InfluxDB

    InfluxDB 是一个开源的没有外部依赖的时间序列数据库。适用于记录度量,事件及实时分析。

    2 引用 • 47 关注
  • Dubbo

    Dubbo 是一个分布式服务框架,致力于提供高性能和透明化的 RPC 远程服务调用方案,是 [阿里巴巴] SOA 服务化治理方案的核心框架,每天为 2,000+ 个服务提供 3,000,000,000+ 次访问量支持,并被广泛应用于阿里巴巴集团的各成员站点。

    60 引用 • 82 回帖 • 590 关注
  • 支付宝

    支付宝是全球领先的独立第三方支付平台,致力于为广大用户提供安全快速的电子支付/网上支付/安全支付/手机支付体验,及转账收款/水电煤缴费/信用卡还款/AA 收款等生活服务应用。

    29 引用 • 347 回帖 • 2 关注
  • 分享

    有什么新发现就分享给大家吧!

    240 引用 • 1729 回帖
  • 房星科技

    房星网,我们不和没有钱的程序员谈理想,我们要让程序员又有理想又有钱。我们有雄厚的房地产行业线下资源,遍布昆明全城的 100 家门店、四千地产经纪人是我们坚实的后盾。

    6 引用 • 141 回帖 • 548 关注
  • Hprose

    Hprose 是一款先进的轻量级、跨语言、跨平台、无侵入式、高性能动态远程对象调用引擎库。它不仅简单易用,而且功能强大。你无需专门学习,只需看上几眼,就能用它轻松构建分布式应用系统。

    9 引用 • 17 回帖 • 591 关注
  • 禅道

    禅道是一款国产的开源项目管理软件,她的核心管理思想基于敏捷方法 scrum,内置了产品管理和项目管理,同时又根据国内研发现状补充了测试管理、计划管理、发布管理、文档管理、事务管理等功能,在一个软件中就可以将软件研发中的需求、任务、bug、用例、计划、发布等要素有序的跟踪管理起来,完整地覆盖了项目管理的核心流程。

    5 引用 • 15 回帖 • 223 关注
  • 链书

    链书(Chainbook)是 B3log 开源社区提供的区块链纸质书交易平台,通过 B3T 实现共享激励与价值链。可将你的闲置书籍上架到链书,我们共同构建这个全新的交易平台,让闲置书籍继续发挥它的价值。

    链书社

    链书目前已经下线,也许以后还有计划重制上线。

    14 引用 • 257 回帖 • 2 关注
  • Openfire

    Openfire 是开源的、基于可拓展通讯和表示协议 (XMPP)、采用 Java 编程语言开发的实时协作服务器。Openfire 的效率很高,单台服务器可支持上万并发用户。

    6 引用 • 7 回帖 • 87 关注
  • IBM

    IBM(国际商业机器公司)或万国商业机器公司,简称 IBM(International Business Machines Corporation),总公司在纽约州阿蒙克市。1911 年托马斯·沃森创立于美国,是全球最大的信息技术和业务解决方案公司,拥有全球雇员 30 多万人,业务遍及 160 多个国家和地区。

    16 引用 • 53 回帖 • 104 关注
  • 京东

    京东是中国最大的自营式电商企业,2015 年第一季度在中国自营式 B2C 电商市场的占有率为 56.3%。2014 年 5 月,京东在美国纳斯达克证券交易所正式挂牌上市(股票代码:JD),是中国第一个成功赴美上市的大型综合型电商平台,与腾讯、百度等中国互联网巨头共同跻身全球前十大互联网公司排行榜。

    14 引用 • 102 回帖 • 405 关注
  • 又拍云

    又拍云是国内领先的 CDN 服务提供商,国家工信部认证通过的“可信云”,乌云众测平台认证的“安全云”,为移动时代的创业者提供新一代的 CDN 加速服务。

    21 引用 • 37 回帖 • 505 关注