这个问题在这里已经有答案了:
哈希表是如何工作的(15个答案)上个月关门了。在java中,hashtable有数量等于其容量的bucket。现在,它如何确定必须将对象存储在特定的bucket中?我知道它使用对象的hashcode,但是hashcode是一个奇怪的长字符串,hashtable对hashcode做了什么来确定条目的位置?
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值的低位分布不均匀的情况下减少聚类。
Object::toString
HashMap
HashTable
HashSet
LinkedHashMap
hashCode()
value % array.length
array
7bsow1i62#
依赖于实现(例如,如果您依赖它以这种方式工作,那么您的代码将被破坏;hashmap保证的内容在其javadoc中有详细说明,我要键入的内容都不在其中):散列只是一个数字。大约在-20亿到+20亿之间。你看到的那个“奇怪的长串”只是一个更方便的展示方式。首先,该数字的高位被混合到低位(实际上,高位被异或到低位):12340005变为12341239。然后,这个数字除以当前有多少桶,但结果被抛出,这是我们感兴趣的余数。这个余数必须是0或更高,并且永远不会超过#个桶,所以总是精确地指向其中一个桶。那是物体进入的桶。如果桶太大,则需要调整大小。更详细地说,hashmap是开源的,hashset也是开源的——看看吧。
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;
这是哈希表的常用技术。丢弃第一位(使值为正数)。索引是除以表大小所得的余数。
3条答案
按热度按时间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值的低位分布不均匀的情况下减少聚类。7bsow1i62#
依赖于实现(例如,如果您依赖它以这种方式工作,那么您的代码将被破坏;hashmap保证的内容在其javadoc中有详细说明,我要键入的内容都不在其中):
散列只是一个数字。大约在-20亿到+20亿之间。你看到的那个“奇怪的长串”只是一个更方便的展示方式。
首先,该数字的高位被混合到低位(实际上,高位被异或到低位):12340005变为12341239。
然后,这个数字除以当前有多少桶,但结果被抛出,这是我们感兴趣的余数。这个余数必须是0或更高,并且永远不会超过#个桶,所以总是精确地指向其中一个桶。
那是物体进入的桶。
如果桶太大,则需要调整大小。
更详细地说,hashmap是开源的,hashset也是开源的——看看吧。
wbrvyc0a3#
有关jdk7的行为,请参见:
https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/hashtable.java#l358
这是哈希表的常用技术。丢弃第一位(使值为正数)。索引是除以表大小所得的余数。