java哈希表如何根据哈希代码计算元素的放置位置?

vc6uscn9  于 2021-07-08  发布在  Java
关注(0)|答案(3)|浏览(401)

这个问题在这里已经有答案了

哈希表是如何工作的(15个答案)
上个月关门了。
在java中,hashtable有数量等于其容量的bucket。现在,它如何确定必须将对象存储在特定的bucket中?我知道它使用对象的hashcode,但是hashcode是一个奇怪的长字符串,hashtable对hashcode做了什么来确定条目的位置?

q1qsirdb

q1qsirdb1#

我知道它使用对象的hashcode,但是hashcode是一个奇怪的长字符串,hashtable对hashcode做了什么来确定条目的位置?
哈希代码不是“奇怪的长字符串”。它是一个32位有符号整数。
(我认为您混淆了hashcode和调用时得到的内容 Object::toString ... 它是一个由哈希代码和java内部类型名组成的字符串。)
那又怎么样 HashMap 以及 HashTable (和 HashSet 以及 LinkedHashMap )实际上你要做的是:
呼叫 hashCode() 要得到32位整数,
对整数执行特定于实现的mangling1,
通过删除符号位将损坏的整数转换为非负整数,
计算数组索引(对于bucket)如下 value % array.length 哪里 array 是哈希表的哈希链(或树)的当前数组。
1-的一些实现 HashMap / HashTable 执行一些简单/廉价的按位损坏。其目的是在hashcode值的低位分布不均匀的情况下减少聚类。

7bsow1i6

7bsow1i62#

依赖于实现(例如,如果您依赖它以这种方式工作,那么您的代码将被破坏;hashmap保证的内容在其javadoc中有详细说明,我要键入的内容都不在其中):
散列只是一个数字。大约在-20亿到+20亿之间。你看到的那个“奇怪的长串”只是一个更方便的展示方式。
首先,该数字的高位被混合到低位(实际上,高位被异或到低位):12340005变为12341239。
然后,这个数字除以当前有多少桶,但结果被抛出,这是我们感兴趣的余数。这个余数必须是0或更高,并且永远不会超过#个桶,所以总是精确地指向其中一个桶。
那是物体进入的桶。
如果桶太大,则需要调整大小。
更详细地说,hashmap是开源的,hashset也是开源的——看看吧。

wbrvyc0a

wbrvyc0a3#

有关jdk7的行为,请参见:
https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/hashtable.java#l358

int index = (hash & 0x7FFFFFFF) % tab.length;

这是哈希表的常用技术。丢弃第一位(使值为正数)。索引是除以表大小所得的余数。

相关问题