Java中的64位HashMap

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java中的64位HashMap，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3181字，纯文字阅读大概需要5分钟。

内容图文

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

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

现在的问题是：

>我理解这个吗？ Java Hashmap只能用几千个条目吗？
>有没有计划在未来的Java版本中实现64位哈希？
>是否有一个由Guava或其他库提供的Map实现,它使用基于长的哈希而不是整数.

解决方法:

碰撞确实是一个问题,但仅仅增加表格大小并不是一个可行的解决方案.哈希表(在算法简介中定义)使用直接地址表来存储哈希桶.因为它是一个直接地址表,实际开始存储对象之前的大小是相对于“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和IdentityHashMap中实际上有两个HashMap实现,它们使用两种不同的方法来存储碰撞的对象. 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％加载因子,在Java HashMap考虑使用超过当前可用的哈希空间之前,您需要805306368个条目.
>在github上有一个cuckoo哈希映射的实现,还有一些其他的实现浮动.我从来没有见过它被用于愤怒.我认为你最好修复你的哈希,并调整地图的初始大小和加载因子.

内容总结

以上是互联网集市为您收集整理的Java中的64位HashMap全部内容，希望文章能够帮你解决Java中的64位HashMap所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端