java.util.HashMap和HashSet的内部实现
我一直在尝试理解java.util.HashMap
和java.util.HashSet
的内部实现。
以下是我脑海中浮现的疑惑:
- 什么是HashMap / HashSet中
@Override public int hashcode()
的重要性? 这个哈希码在内部使用在哪里? - 我一般看到HashMap的键是一个像
myMap
这样的myMap
。 我可以将值映射到someObject
(而不是String),如myMap
吗? 我需要遵守的所有合同成功实现了什么?
提前致谢 !
编辑:
- 我们是说密钥的哈希码(check!)是在哈希表中映射值的实际内容吗? 当我们做
myMap.get(someKey);
java在内部调用someKey.hashCode()
来获取哈希表中要查找结果值的数字?
答:是的。
编辑2:
- 在
java.util.HashSet
,从哪里为Hash表生成密钥? 它来自我们正在添加的对象,例如。mySet.add(myObject);
那么myObject.hashCode()
将决定它在哈希表中的位置? (因为我们不在HashSet中给出键)。
答:添加的对象成为关键。 价值是假的!
问题2的答案很简单 – 是的,你可以使用任何你喜欢的对象。 具有String类型键的映射被广泛使用,因为它们是命名服务的典型数据结构。 但一般来说,您可以映射任何两种类型,如Map
或Map
。
对于hashcode()方法,它就像以前一样回答 – 每当你重写equals()时,你必须覆盖hashcode()来服从契约。 另一方面,如果您对equals()的标准实现感到满意,那么您不应该触及hashcode()(因为这可能会破坏契约并导致不相等对象的相同哈希码)。
实用的旁注:eclipse(以及可能还有其他IDE)可以为您的类自动生成一对equals()和hashcode()实现,仅基于类成员。
编辑
对于您的其他问题:是的,确切地说。 查看HashMap.get(Object key)的源代码; 它调用key.hashcode来计算内部哈希表中的位置(bin)并返回该位置的值(如果有的话)。
但要小心’手工’哈希码/等于方法 – 如果你使用一个对象作为键,请确保哈希码之后不会改变,否则你将不再找到映射的值。 换句话说,用于计算equals和hashcode的字段应该是final (或者在创建对象后“ 不可更改”)。
假设,我们有一个String name
和String phonenumber
的联系人,我们使用这两个字段来计算equals()和hashcode()。 现在我们用他的手机号码创建“John Doe”并将他映射到他最喜欢的甜甜圈店。 hashcode()用于计算哈希表中的索引(bin)以及存储甜甜圈店的位置。
现在我们了解到他有一个新的电话号码,我们更改了John Doe对象的电话号码字段。 这导致新的哈希码。 并且这个哈希码解析为一个新的哈希表索引 – 这通常不是John Do’最喜欢的甜甜圈商店的存储位置。
问题很明显:在这种情况下,我们想要将“John Doe”映射到Donut商店,而不是“带有特定电话号码的John Doe”。 所以,我们必须小心自动生成的equals / hashcode以确保它们是我们真正想要的,因为它们可能会使用不需要的字段,从而给HashMaps和HashSets带来麻烦。
编辑2
如果将对象添加到HashSet,则Object是内部哈希表的键,该值已设置但未使用(只是Object的静态实例)。 这是openjdk 6(b17)的实现:
// Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); private transient HashMap map; public boolean add(E e) { return map.put(e, PRESENT)==null; }
什么是HashMap / HashSet中@Override public int hashcode()的重要性?
这允许地图实例根据地图的内容生成有用的哈希码。 具有相同内容的两个映射将生成相同的哈希码。 如果内容不同,则哈希码将不同。
这个哈希码在内部使用在哪里?
决不。 此代码仅存在,因此您可以将地图用作另一个地图中的键。
我可以将值映射到
someObject
(而不是String
),如myMap
吗?
是的,但someObject
必须是一个类,而不是一个对象(你的名字暗示你要传入对象;它应该是SomeObject
,以明确你指的是类型)。
我需要遵守的所有合同成功实现了什么?
该类必须实现hashCode()
和equals()
。
[编辑]
我们是说密钥的哈希码(check!)是在哈希表中映射值的实际内容吗?
是。
是。 您可以使用任何对象作为HashMap中的键。 为了做到这一点,您必须遵循以下步骤。
-
覆盖等于。
-
覆盖hashCode。
在java.lang.Object的文档中非常清楚地提到了这两种方法的合同。 http://java.sun.com/javase/6/docs/api/java/lang/Object.html
是的hashCode()方法由HashMap内部使用,因此返回适当的值对性能很重要。
这是HashMap的hashCode()方法
public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; }
从上面的代码可以清楚地看出,每个键的hashCode不仅用于地图的hashCode(),而且还用于查找存储键以放置键,值对。 这就是hashCode()与HashMap的性能相关的原因
散列容器(如HashMap
和HashSet
可以通过将其内容拆分为“存储桶”来快速访问存储在其中的元素。
例如1, 2, 3, 4, 5, 6, 7, 8
存储在List
中的数字列表: 1, 2, 3, 4, 5, 6, 7, 8
将在内存中(概念上)看起来像: [1, 2, 3, 4, 5, 6, 7, 8]
。
在Set
存储相同的数字Set
看起来更像是: [1, 2] [3, 4] [5, 6] [7, 8]
。 在此示例中,列表已拆分为4个存储桶。
现在假设你想要找到List
和Set
的值6
。 使用列表,您必须从列表的开头开始并检查每个值,直到达到6,这将需要6个步骤。 使用set,您可以找到正确的存储桶,检查该存储桶中的每个项目(在我们的示例中只有2个),这使得这是一个3步骤的过程。 这种方法的价值会随着您拥有的数据越多而显着增加。
但是等一下我们怎么知道要看哪个桶? 这就是hashCode
方法的用武之地。要确定查找项目的存储桶,Java哈希容器调用hashCode
然后将一些函数应用于结果。 此函数尝试平衡存储桶的数量和项目数,以便尽可能快地查找。
在查找过程中,一旦找到正确的存储桶,就会在列表中逐个比较该存储桶中的每个项目。 这就是为什么当你覆盖hashCode
时你也必须覆盖equals
。 因此,如果任何类型的对象同时具有equals
和hashCode
方法,则它可以用作Map
的键或Set
的条目。 必须遵循一个合同才能正确实现这些方法。规范性文本来自Josh Bloch的好书有效Java: 第8项:当你重写equals时总是覆盖hashCode
- Java中的任何
Object
都必须具有hashCode()
方法;HashMap
和HashSet
不是例外。 如果将哈希映射/集插入另一个哈希映射/集中,则使用此哈希码。 - 任何类类型都可以用作
HashMap
/HashSet
的键。 这要求hashCode()
方法返回相等对象的相等值,并且equals()
方法是根据契约(自反,传递,对称)实现的。Object
的默认实现已经遵循这些契约,但如果您希望值相等而不是引用相等,则可能需要覆盖它们。
在Java(以及.NET)中,equals(), hashcode()
和哈希表之间存在复杂的关系。 引用文档:
public int hashCode()
返回对象的哈希码值。 支持此方法是为了哈希表的好处,例如
java.util.Hashtable
提供的哈希表。hashCode的一般契约是:
- 每当在执行Java应用程序期间多次在同一对象上调用它时,hashCode方法必须始终返回相同的整数,前提是不修改对象上的equals比较中使用的信息。 从应用程序的一次执行到同一应用程序的另一次执行,该整数不需要保持一致。
- 如果两个对象根据equals(Object)方法相等,则对两个对象中的每一个调用hashCode方法必须生成相同的整数结果。
- 如果两个对象根据equals(
java.lang.Object
)方法不相等,则不需要在两个对象中的每一个上调用hashCode
方法必须生成不同的整数结果。 但是,程序员应该知道为不等对象生成不同的整数结果可能会提高哈希表的性能。尽可能合理,
Object
类定义的hashCode
方法确实为不同的对象返回不同的整数。 (这通常通过将对象的内部地址转换为整数来实现,但Java™编程语言不需要此实现技术。)
这条线
@Overrides public int hashCode()
只是告诉我们覆盖了hashCode()
方法。 这通常表示在HashMap
使用类型作为键是安全的。
是的,你可以在HashMap中使用任何服从equals()
和hashCode()
的契约的对象作为键。
在回答问题2时,虽然您可以使用任何可用作Hashmap中键的类,但最佳做法是使用不可变类作为HashMap的键。 或者至少如果你的“hashCode”和“equals”实现依赖于你的类的某些属性,那么你应该注意不要提供改变这些属性的方法。
Aaron Digulla是完全正确的。 人们似乎没有意识到的另一个有趣的补充说明是密钥对象的hashCode()方法不是逐字使用的。 事实上,它是由HashMap重新调用的,即它调用hash(someKey.hashCode))
,其中hash()
是一个内部散列方法。
要查看此内容,请查看源代码: http : //kickjava.com/src/java/util/HashMap.java.htm
原因是有些人很难实现hashCode(),而hash()函数提供了更好的散列分布。 它基本上是出于性能原因而完成的。
集合类的HashCode方法,如HashSet,HashTable,HashMap等 – 散列代码返回为散列目的而支持的对象的整数。 它是通过将对象的内部地址转换为整数来实现的。 应该在覆盖equals方法的每个类中重写散列码方法。 HashCode方法的三个常规联系人
-
对于两个相同的对象acc。 为了等于方法,然后为两个对象调用HashCode它应该产生相同的整数值。
-
如果为单个对象多次调用它,则它应返回常量整数值。
-
对于两个不相等的对象acc。 为了等于方法,然后为两个对象调用HashCode方法,它不应该强制它产生不同的值。