java - Java中的64位HashMap

Question

我正在阅读有关计算哈希冲突概率的博客文章here。
根据公式1−(e^(−k(k−1)/2N))，其中k是条目数，N是max_entries，默认Java哈希图的哈希冲突概率应该是50%，只有7万个条目。

由于最大可能的输入范围很大(4294967296)，因此这似乎很不直观。但是，通过生日悖论可以理解这一点，其中只有70人的概率达到99.9％。

现在的问题:

我明白这个意思吗？ Java Hashmap是否仅可用于数千个条目？

是否有计划在Java的 future 版本中实现64位哈希？

是否存在由Guava或其他一些库提供的Map实现，该实现使用基于long的哈希而不是integers。

Answer 1

冲突确实是一个问题，但是仅增加表大小并不是可行的解决方案。哈希表(如算法介绍中所定义)使用直接地址表存储哈希桶。因为它是一个直接地址表，所以实际开始存储对象之前的大小与“Universe”中的哈希总数有关(就Universe而言，就哈希表而言，我是指Universe)。如果您实际上要使用所有可用的地址空间，则在将哈希表放入任何内容之前，其哈希表将为2^30 * memory_address_size，这很多(请注意，OpenJDK将哈希映射中的对象数限制设置为2^30 ，而不是2^32)。

实际上，默认情况下，Java HashMap实现实际上以16个哈希世界大小开始(我记得读过8个，但是OpenJDK 8 JVM实现是16个)。因此，当您放入一个对象时，Java从hashCode()获得整数结果，并通过除以16得到余数。这就是它使用的哈希。默认情况下，Java哈希图还使用0.75的加载因子。因此，它直到75％充满之前都不会尝试增加“哈希宇宙”的大小。到那时，将创建一个新的哈希表，以新的Universe大小重新计算该过程中的所有哈希，其大小是前一个表的两倍。这是一个昂贵的操作。因此，我的意思是，Java HashMap的目标是使地图保持75％的完整度，并期望发生冲突。正确设置哈希图可以提高性能。您可以实例化具有初始值的哈希映射，还可以选择负载因子。

Map<String, String> myMap = new HashMap(128, 0.5f);    

请注意，在OpenJDK实现中，您不能选择小于0.25或大于4的负载系数:

float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);

实际上，java中有两个HashMap实现， HashMap和 IdentityHashMap，它们使用两种不同的方法来存储碰撞的对象。 IdentityHashMap将一个对象(其哈希值与另一个对象冲突)放入下一个可用存储桶。每个存储桶仅包含一个对象。它还使用 ==进行比较，而不是 .equals()，因此您实际上只能对键使用原始数据类型。但是，它比HashMap快一点。

HashMap实现使用每个存储桶中的链接列表来存储具有相同哈希的对象。从Java 8开始，一旦任何链表获得8个或更多对象，链表将被重构为 tree。如果您的对象没有实现 Comparable，那么这将没有任何效果。因此，让您的对象实现 Comparable是值得的。但这意味着我们可以量化碰撞的成本。在最坏的情况下，它是链表的 O(n)，但是在树的情况下，最坏的情况下是 O(logn)。最坏的情况是，我的意思是当所有对象都放在同一个存储桶中时。

因此，当该博客讨论发生碰撞的可能性时，如果70,000个对象中的两个对象发生碰撞，则实际上并不重要。一千个也没关系。当对象 没有哈希的均匀分布时，冲突就很重要。从o表示的角度来看，必须循环通过大小为70k的哈希图中大小为2的链表仍然是O(1)。如果那数千个冲突发生在同一个哈希存储桶中，那么您确实有一个真正的问题。但这是哈希实现的 问题，而不是缺少64位寻址。

有一些完美的哈希方法。如dynamic perfect hashing和cuckoo hashing。它们使用多种哈希算法来尝试防止哈希冲突。动态散列使用两个表，其中一个表很大，旨在避免发生任何冲突。但这会导致严重的内存消耗，这是不容忽视的。

因此，回答您的问题:

不，HashMaps可以用于数千个条目。仅当散列分布不均的严重问题严重时，冲突才具有破坏性。如果无法修复不均匀的哈希，请在对象上实现Comparable。

不，没有必要。使用HashMap当前使用的75％的负载率，您需要805306368条目，然后Java HashMap才会考虑使用比当前可用的哈希空间更多的哈希空间。

在github上有一个布谷鸟哈希映射的实现，还有其他一些实现。我从来没有见过它被用在愤怒中。我认为您可以更好地解决哈希问题，并调整地图的初始大小和加载因子。