pol*_*nts 75 java string hashcode
我注意到在Java 6的String源代码中,hashCode只缓存0以外的值.下面的代码片段展示了性能上的差异:
public class Main{
static void test(String s) {
long start = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
s.hashCode();
}
System.out.format("Took %d ms.%n", System.currentTimeMillis() - start);
}
public static void main(String[] args) {
String z = "Allocator redistricts; strict allocator redistricts strictly.";
test(z);
test(z.toUpperCase());
}
}
在ideone.com中运行此命令将提供以下输出:
Took 1470 ms.
Took 58 ms.
所以我的问题是:
为了您的娱乐,这里的每一行都是一个散列为0的字符串:
pollinating sandboxes
amusement & hemophilias
schoolworks = perversive
electrolysissweeteners.net
constitutionalunstableness.net
grinnerslaphappier.org
BLEACHINGFEMININELY.NET
WWW.BUMRACEGOERS.ORG
WWW.RACCOONPRUDENTIALS.NET
Microcomputers: the unredeemed lollipop...
Incentively, my dear, I don't tessellate a derangement.
A person who never yodelled an apology, never preened vocalizing transsexuals.
Kev*_*ion 56
你什么都不担心.这是一种思考这个问题的方法.
假设你有一个应用程序除了可以全年使用哈希字符串之外什么都不做.让我们说它需要一千个字符串,全部在内存中,以循环方式重复调用hashCode(),一百万次,然后获得另外一千个新字符串并再次执行.
并且假设字符串的哈希码为零的可能性实际上远大于1/2 ^ 32.我敢肯定它有点大于1/2 ^ 32,但是让我们说它比那更糟糕,比如1/2 ^ 16(平方根!现在情况要糟糕得多!).
在这种情况下,您可以从Oracle工程师那里获益更多,从而改善这些字符串的哈希码的缓存方式.所以你写信给他们并要求他们解决它.并且他们发挥他们的魔力,以便每当s.hashCode()为零时,它立即返回(即使是第一次!100%改进!).让我们说他们这样做而不会降低任何其他情况下的性能.
万岁!现在你的应用程序是...让我们看看......快0.0015%!
过去需要一整天的时间现在只需要23小时57分48秒!
请记住,我们设定的方案是为了给出怀疑的每一个可能的好处,通常是一个荒谬的程度.
这看起来对你有价值吗？
编辑:自从几个小时前发布这篇文章以来,我让我的一个处理器疯狂地查找具有零哈希码的双字短语.到目前为止,它提出了:bequirtle zorillo,chronogrammic schtoff,contusive cloisterlike,creashaks organzine,drumwood boulderhead,electroanalytic exercisable,以及最好的不可理解.这超出了大约2 ^ 35种可能性,所以在完美分布的情况下,我们期望只看到8个.显然,到它完成的时候,我们会有很多次,但不会更加奇怪.更重要的是,我现在想出了一些有趣的乐队名称/专辑名称!没有公平的窃取!
Jon*_*eet 24
它使用0表示"我还没有编写哈希码".替代方案是使用单独的布尔标志,这将占用更多内存.(当然,根本不要缓存哈希码.)
我不希望很多字符串哈希到0; 可以说,散列例程故意避免0是有意义的(例如,将0到1的散列转换为缓存).这会增加碰撞,但避免重复.现在为时已晚,因为String hashCode算法已明确记录.
至于这是否是一个好主意:它是一个肯定有效的缓存机制,并且可能(见编辑)更好,改变以避免重新散列值最终为哈希值0.个人我会有兴趣看到导致Sun首先相信这一点值得做的数据 - 它为每个创建的字符串占用了额外的4个字节,但是经常或很少经常进行散列,唯一的好处是对于多次散列的字符串.
编辑:正如KevinB在其他地方的评论中指出的那样,上面的"避免0"建议可能会有一个净成本,因为它有助于一个非常罕见的情况,但需要对每个哈希计算进行额外的比较.
MB.*_*MB. 19
我认为到目前为止其他答案都缺失了一些重要的东西:零值存在,因此hashCode-caching机制在多线程环境中可靠地工作.
如果您有两个变量,比如cachedHashCode本身和一个isHashCodeCalculated布尔值来指示是否已经计算了cachedHashCode,那么您需要线程同步才能在多线程环境中工作.同步对性能有害,特别是因为Strings在多个线程中非常常用.
我对Java内存模型的理解有点粗略,但这里大概是发生了什么:
当多个线程访问变量(如缓存的hashCode)时,无法保证每个线程都会看到最新的值.如果变量从零开始,则A更新它(将其设置为非零值),然后线程B不久后读取它,线程B仍然可以看到零值.
从多个线程访问共享值还有另一个问题(没有同步) - 您最终可能会尝试使用仅部分初始化的对象(构造对象不是原子进程).64位原语(如long和double)的多线程读写也不一定是原子的,因此如果两个线程尝试读取并更改long或double的值,则一个线程最终会看到一些奇怪的并且部分设置.或者类似的东西.如果你试图一起使用两个变量,比如cachedHashCode和isHashCodeCalculated,就会出现类似的问题 - 一个线程很容易出现并看到其中一个变量的最新版本,但是另一个变量的旧版本.
解决这些多线程问题的常用方法是使用同步.例如,您可以将所有对缓存的hashCode的访问权限放在synchronized块中,或者您可以使用volatile关键字(尽管要小心,因为语义有点令人困惑).
但是,同步减慢了速度.像字符串hashCode这样的坏主意.字符串经常用作HashMaps中的键,因此您需要hashCode方法才能很好地执行,包括在多线程环境中.
32位或更少的Java原语(如int)是特殊的.与长(64位值)不同,您可以确定永远不会读取int的部分初始化值(32位).当你在没有同步的情况下读取一个int时,你不能确定你将获得最新的设置值,但是你可以确定你得到的值是一个在某个时候由你的线程明确设置的值或另一个线程.
java.lang.String中的hashCode缓存机制设置为依赖上面的第5点.您可以通过查看java.lang.String.hashCode()的源代码来更好地理解它.基本上,多个线程一次调用hashCode,hashCode最终可能会多次计算(如果计算的值为零,或者多个线程一次调用hashCode并且都看到零缓存值),但是您可以确定hashCode ()将始终返回相同的值.所以它很强大,而且性能也很高(因为在多线程环境中没有同步作为瓶颈).
就像我说的,我对Java内存模型的理解有点粗略,但我很确定我已经掌握了上述权利.最终,它是一个非常聪明的习惯用于缓存hashCode而没有同步的开销.
0未缓存,因为实现将缓存值0解释为"尚未初始化的缓存值".替代方法是使用a java.lang.Integer,即null表示该值尚未缓存.但是,这意味着额外的存储开销.
关于String的哈希码被计算为0的概率我会说概率非常低并且可能在以下情况下发生:
e.g. Integer.MAX_VALUE + h(c1) + h(c2) + ... h(cn) == 0).来自维基百科:
代码0(ASCII代码名称NUL)是一种特殊情况.在纸带中,没有孔时就是这种情况.将其视为填充字符是很方便的,没有其他意义.
十年后，情况发生了变化。老实说，我简直不敢相信这一点（但我内心的极客非常高兴）。
\n正如您所注意到的，有可能某些String::hashCode字符串的某些内容被缓存zero，并且没有被缓存（将得到这一点）。很多人争论（包括在这个问答中）为什么没有在 中添加一个字段java.lang.String，比如 :hashAlreadyComputed并简单地使用它。问题很明显：每个 String 实例都有额外的空间。顺便说一句，引入s是有原因的 ，因为一个简单的事实是，许多基准测试表明，在大多数应用程序中，这是一个相当（过度）使用的类。添加更多空间？决定是：不。特别是因为最小可能的添加将是, not （对于s，额外的空间将是：1 用于标志，7 用于对齐）。java-9compact String1 byte1 bit32 bit JMV8 bytes
所以，Compact Strings 出现在 中java-9，如果你仔细观察（或关心），他们确实java.lang.String在:中添加了一个字段coder。我刚才不是反对了吗？它不是那么容易。看起来紧凑字符串的重要性超过了“额外空间”的争论。同样重要的是，额外的空间32 bits VM只重要（因为对齐时没有间隙）。相比之下，在jdk-8布局中java.lang.String是：
java.lang.String object internals:\n OFFSET SIZE TYPE DESCRIPTION VALUE\n 0 12 (object header) N/A\n 12 4 char[] String.value N/A\n 16 4 int String.hash N/A\n 20 4 (loss due to the next object alignment)\n Instance size: 24 bytes\n Space losses: 0 bytes internal + 4 bytes external = 4 bytes total\n注意这里有一件重要的事情：
\nSpace losses : ... 4 bytes total.\n因为每个 java 对象都是对齐的（对齐的程度取决于 JVM 和一些启动标志，例如UseCompressedOops），因此存在, 未使用的String间隙。4 bytes因此，添加时coder，只需添加即可1 byte ，无需添加额外的空间。因此，添加 s后 Compact String，布局发生了变化：
java.lang.String object internals:\n OFFSET SIZE TYPE DESCRIPTION VALUE\n 0 12 (object header) N/A\n 12 4 byte[] String.value N/A\n 16 4 int String.hash N/A\n 20 1 byte String.coder N/A\n 21 3 (loss due to the next object alignment)\n Instance size: 24 bytes\n Space losses: 0 bytes internal + 3 bytes external = 3 bytes total\ncoder吃1 byte和差距缩小到3 bytes。所以“损害”已经造成了jdk-9。因为32 bits JVM有增加，并且8 bytes : 1 coder + 7 gap没有64 bit JVM增加，coder占据了间隙中的一些空间。
现在，jdk-13他们决定利用它gap，因为它无论如何都存在。我只是提醒您，哈希码为零的字符串的概率是 40 亿分之一；还是有人说：那又怎样？让我们解决这个问题！Voil\xc3\xa1：jdk-13布局java.lang.String：
java.lang.String object internals:\nOFFSET SIZE TYPE DESCRIPTION VALUE\n 0 12 (object header) N/A\n 12 4 byte[] String.value N/A\n 16 4 int String.hash N/A\n 20 1 byte String.coder N/A\n 21 1 boolean String.hashIsZero N/A\n 22 2 (loss due to the next object alignment)\n Instance size: 24 bytes\n Space losses: 0 bytes internal + 2 bytes external = 2 bytes total\n这是：boolean String.hashIsZero。它位于代码库中：
public int hashCode() {\n int h = hash;\n if (h == 0 && !hashIsZero) {\n h = isLatin1() ? StringLatin1.hashCode(value)\n : StringUTF16.hashCode(value);\n if (h == 0) {\n hashIsZero = true;\n } else {\n hash = h;\n }\n }\n return h;\n}\n等待！h == 0 和 hashIsZero场？难道不应该命名为：hashAlreadyComputed吗？为什么实施方式不类似于：
@Override\n public int hashCode(){\n if(!hashCodeComputed){\n // or any other sane computation\n hash = 42;\n hashCodeComputed = true;\n }\n\n return hash;\n }\n即使我读了源代码下的注释：
\n // The hash or hashIsZero fields are subject to a benign data race,\n // making it crucial to ensure that any observable result of the\n // calculation in this method stays correct under any possible read of\n // these fields. Necessary restrictions to allow this to be correct\n // without explicit memory fences or similar concurrency primitives is\n // that we can ever only write to one of these two fields for a given\n // String instance, and that the computation is idempotent and derived\n // from immutable state\n读完这篇文章后才有意义。相当棘手，但这一次只能写一个，上面的讨论中有更多细节。
\n| 归档时间： |
|
| 查看次数： |
10640 次 |
| 最近记录： |