Java中的64位HashMap

Question

我正在读这篇博客在这里有关计算哈希冲突的概率.根据公式1?(e^(?k(k?1)/2N)),其中k是条目数并且N是max_entries,默认Java hashmap的哈希冲突概率应该50%只有7万个条目.

这似乎是违反直觉的,因为最大可能的进入范围非常大(4294967296).但是,生日悖论可以理解,只有70人,概率达到99.9%.

现在的问题是:

1. 我明白了吗？Java Hashmap只能用几千个条目吗？
2. 有没有计划在未来的Java版本中实现64位哈希？
3. 是否有由Guava其他库提供的Map实现,long而不是使用基于哈希的库integers.

Answer 1

碰撞确实是一个问题,但仅仅增加表格大小并不是一个可行的解决方案.哈希表(在算法简介中定义)使用直接地址表来存储哈希桶.因为它是一个直接地址表,实际开始存储对象之前的大小是相对于"Universe"中可能的哈希总数(通过Universe,我的意思是就哈希表而言是宇宙).如果您实际使用了所有可用的地址空间,那么在您放入任何内容之前,您的哈希表就会2^30 * memory_address_size很多(注意OpenJDK设置哈希映射中对象数量的限制2^30,而不是2^32).

默认情况下,Java HashMap实现的哈希Universe大小为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个或更多对象,链表将被重构为树.如果您的对象没有Comparable实现,那么这将没有任何效果.因此,实现对象是值得的Comparable.但这意味着我们可以量化碰撞的成本.在最坏的情况下,它是O(n)一个链表,但对于一棵树,它是最糟糕的情况O(logn).在最糟糕的情况下,我的意思是当你的所有物体都在同一个桶中时.

因此,当该博客谈论碰撞的可能性时,如果70,000中的两个物体发生碰撞真的无关紧要.如果其中有数千人这样做并不重要.当对象没有均匀的散列分布时,碰撞很重要.从o符号的角度来看,必须在大小为70k的哈希映射中循环遍历大小为2的链表仍然是O(1).如果这些千次冲突发生在同一个哈希桶中,那么你确实遇到了真正的问题.但这是您的哈希实现的问题,而不是缺少64位寻址.

有完美的散列方式.如动态完美哈希和布谷鸟哈希.它们使用多个散列算法来尝试防止散列冲突.动态哈希使用两个表,其中一个表非常大,以避免任何冲突.但这会产生严重的记忆成本,这是不容忽视的.

那么,回答你的问题:

1. 不,HashMaps可用于超过几千个条目.如果你遇到分布不均匀的哈希问题,那么碰撞只会是破坏性的.Comparable如果无法修复不均匀的散列,请在对象上实现.

2. 不,没有必要.使用HashMap当前使用的75%加载因子,在Java HashMap考虑使用超过当前可用的哈希空间之前,您需要805306368个条目.

3. 在github上有一个cuckoo散列映射的实现,还有一些其他实现浮动.我从来没有见过它被用于愤怒.我认为你最好修复你的哈希,并调整地图的初始大小和加载因子.