我注意到在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.
所以我的问题是:
为什么String的hashCode()没有缓存0？
Java字符串哈希值为0的概率是多少？
对于散列为0的字符串,每次重新计算哈希值的性能损失的最佳方法是什么？
这是缓存值的最佳实践方式吗？(即缓存除一个以外的所有？)
为了您的娱乐,这里的每一行都是一个散列为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.
Kevin Bourri.. 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个.显然,到它完成的时候,我们会有很多次,但不会更加奇怪.更重要的是,我现在想出了一些有趣的乐队名称/专辑名称!没有公平的窃取!
你什么都不担心.这是一种思考这个问题的方法.
假设你有一个应用程序除了可以全年使用哈希字符串之外什么都不做.让我们说它需要一千个字符串,全部在内存中,以循环方式重复调用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个.显然,到它完成的时候,我们会有很多次,但不会更加奇怪.更重要的是,我现在想出了一些有趣的乐队名称/专辑名称!没有公平的窃取!
它使用0表示"我还没有编写哈希码".替代方案是使用单独的布尔标志,这将占用更多内存.(当然,根本不要缓存哈希码.)
我不希望很多字符串哈希到0; 可以说,散列例程故意避免0是有意义的(例如,将0到1的散列转换为缓存).这会增加碰撞,但避免重复.现在为时已晚,因为String hashCode算法已明确记录.
至于这是否是一个好主意:它是一个肯定有效的缓存机制,并且可能(见编辑)更好,改变以避免重新散列值最终为哈希值0.个人我会有兴趣看到导致Sun首先相信这一点值得做的数据 - 它为每个创建的字符串占用了额外的4个字节,但是经常或很少经常进行散列,唯一的好处是对于多次散列的字符串.
编辑:正如KevinB在其他地方的评论中指出的那样,上面的"避免0"建议可能会有一个净成本,因为它有助于一个非常罕见的情况,但需要对每个哈希计算进行额外的比较.
我认为到目前为止其他答案都缺失了一些重要的东西:零值存在,因此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的概率我会说概率非常低并且可能在以下情况下发生:
String为空(尽管每次重新计算此哈希码实际上是O(1)).
发生溢出,最终计算的哈希码为0(e.g. Integer.MAX_VALUE + h(c1) + h(c2) + ... h(cn) == 0).
字符串仅包含Unicode字符0.非常不可能,因为这是一个控制字符,除了"纸带世界"(!)之外没有任何意义:
来自维基百科:
代码0(ASCII代码名称NUL)是一种特殊情况.在纸带中,没有孔时就是这种情况.将其视为填充字符是很方便的,没有其他意义.
事实证明,这是一个与安全漏洞相关的好问题.
"当散列字符串时,Java也会在散列属性中缓存散列值,但前提是结果不等于零.因此,目标值零对攻击者来说特别有意义,因为它可以防止缓存并强制重新散列."
京公网安备 11010802040832号 | 京ICP备19059560号-6 