java.util.HashMap和HashSet的内部实现

Question

我一直在试图了解内部实现的java.util.HashMap和java.util.HashSet.

以下是我脑海中浮现的疑惑:

1. 什么是@Override public int hashcode()HashMap/HashSet中的重要性？这个哈希码在内部使用在哪里？
2. 我一般都看到HashMap的关键是String这样的myMap<String,Object>.我可以映射值someObject(而不是字符串)myMap<someObject, Object>吗？我需要遵守的所有合同成功发生了什么？

提前致谢 !

编辑:

1. 我们是说密钥的哈希码(check!)是在哈希表中映射值的实际内容吗？当我们执行myMap.get(someKey);java时,内部调用someKey.hashCode()以获取哈希表中的数字以查找结果值？

答:是的.

编辑2:

2. 在a中java.util.HashSet,从哪里为Hash表生成密钥？它来自我们正在添加的对象,例如.mySet.add(myObject);然后myObject.hashCode()将决定它在哈希表中的位置？(因为我们不在HashSet中给出键).

答:添加的对象成为关键.价值是假的!

Answer 1

问题2的答案很简单 - 是的,你可以使用任何你喜欢的对象.具有String类型键的映射被广泛使用,因为它们是命名服务的典型数据结构.但一般来说,你可以映射任何两种类型,如Map<Car,Vendor>或Map<Student,Course>.

对于hashcode()方法,它就像之前一样回答 - 每当你重写equals()时,你必须覆盖hashcode()来服从契约.另一方面,如果您对equals()的标准实现感到满意,那么您不应该触及hashcode()(因为这可能会破坏契约并导致不等对象的相同哈希码).

实用的旁注:eclipse(以及可能还有其他IDE)可以为您的类自动生成一对equals()和hashcode()实现,只基于类成员.

编辑

对于您的其他问题:是的,确切地说.查看HashMap.get(Object key)的源代码; 它调用key.hashcode来计算内部哈希表中的位置(bin)并返回该位置的值(如果有的话).

但要注意"手工制作"的hashcode/equals方法 - 如果使用对象作为键,请确保哈希码之后不会更改,否则您将无法再找到映射的值.换句话说,用于计算equals和hashcode的字段应该是final(或者在创建对象后" 不可更改").

假设,我们与String nameand 有联系,并且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<E,Object> map;

public boolean add(E e) {
  return map.put(e, PRESENT)==null;
}

Answer 2

什么是HashMap/HashSet中@Override public int hashcode()的重要性？

这允许地图实例根据地图的内容生成有用的哈希码.具有相同内容的两个映射将生成相同的哈希码.如果内容不同,则哈希码将不同.

这个哈希码在内部使用在哪里？

决不.此代码仅存在,因此您可以将地图用作另一个地图中的关键字.

我可以映射值someObject(而不是String)myMap<someObject, Object>吗？

是,但someObject必须是一个类,而不是一个对象(你的名字暗示你想要传入对象;它应该是SomeObject明确你指的是类型).

我需要遵守的所有合同成功发生了什么？

该类必须实现hashCode()和equals().

[编辑]

我们是说密钥的哈希码(check!)是在哈希表中映射值的实际内容吗？

是.

Answer 3

是.您可以使用任何对象作为HashMap中的键.为了做到这一点,您必须遵循以下步骤.

1. 覆盖等于.

2. 覆盖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<K,V> 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的性能有关

Answer 4

散列容器喜欢HashMap并HashSet通过拆分其内容为"桶"提供存储在其中的元素的快速访问.

例如,数字列表:1, 2, 3, 4, 5, 6, 7, 8存储在一个List将在内存中(概念上)看起来像:[1, 2, 3, 4, 5, 6, 7, 8].

在a中存储相同的数字集Set看起来更像是:[1, 2] [3, 4] [5, 6] [7, 8].在此示例中,列表已拆分为4个存储桶.

现在想象一下,你要查找的值6了两者的List和Set.使用列表,您必须从列表的开头开始并检查每个值,直到达到6,这将需要6个步骤.使用set,您可以找到正确的存储桶,检查该存储桶中的每个项目(在我们的示例中仅为2个),使其成为一个3步骤的过程.这种方法的价值会随着您拥有的数据量的增加而显着增加.

但是等一下,我们怎么知道要看哪个桶？这就是hashCode方法的用武之地.要确定查找Java哈希容器调用项的存储区,hashCode然后将一些函数应用于结果.此函数尝试平衡存储桶的数量和项目数,以便尽可能快地查找.

在查找过程中,一旦找到正确的存储桶,就会在列表中逐个比较该存储桶中的每个项目.这就是为什么当你覆盖hashCode你也必须覆盖equals.因此,如果任何类型的对象同时具有equalsa和hashCode方法,则它可以用作a中的键Map或a中的键Set.有一个必须遵循的合同才能正确实现这些方法.规范性文本来自Josh Bloch的伟大着作Effective Java:第8项:当你重写equals时总是覆盖hashCode