16

在 Hashmap 中，提供的键的哈希码用于将值放置在哈希表中。在哈希集中，对象哈希码用于将值放置在底层哈希表中。也就是说，hashmap 的优点是你可以灵活地决定你想要什么作为键，这样你就可以做这样的好事。

Map<String,Player> players = new HashMap<String,Player>();

这可以将诸如玩家姓名之类的字符串映射到玩家本身。

我的问题是当键的哈希码发生变化时查找会发生什么。

我希望这对于 Hashmap 来说并不是一个主要问题，因为我不希望也不希望密钥改变。在前面的例子中，如果球员的名字改变了，他就不再是那个球员了。但是，我可以使用键更改其他不是名称的字段来查找玩家，并且将来的查找将起作用。

但是，在 Hashset 中，如果有人稍微更改对象，则使用整个对象的哈希码来放置项目，该对象的未来查找将不再解析到 Hashtable 中的相同位置，因为它依赖于整个对象的哈希码。这是否意味着一旦数据在 Hashset 中就不应更改。还是需要重新散列？还是自动完成等？到底是怎么回事？

4

4 回答 4

20

在您的示例中， String 是不可变的，因此其哈希码无法更改。但是假设，如果一个对象的哈希码在哈希表中作为键时确实发生了变化，那么就哈希表查找而言，它可能会消失。我在对相关问题的回答中更详细地介绍了： https ://stackoverflow.com/a/13114376/139985 。（最初的问题是关于 a HashSet，但 aHashSet实际上是 aHashMap在幕后，所以答案也涵盖了这种情况。）

可以肯定地说，如果 HashMap 或 TreeMap 的键以影响它们各自hashcode()/equals(Object)或合同的方式发生突变compare(...)，compareTo(...)那么数据结构将“破坏”。

这是否意味着一旦数据在 Hashset 中就不应更改。

是的。

还是需要重新散列？还是自动完成等？

它不会自动重新散列。HashMap不会注意到密钥的哈希码已更改。事实上，在调整大小时，您甚至不会重新计算哈希HashMap码。数据结构会记住原始哈希码值，以避免在哈希表调整大小时重新计算所有哈希码。

如果您知道密钥的哈希码将要更改，则需要在更改密钥之前从表中删除该条目，然后再将其添加回来。（如果您在更改密钥后尝试remove/它，则很有可能无法找到该条目。）putremove

到底是怎么回事？

发生的事情是你违反了合同。不要那样做！

合同由两部分组成：

  1. 标准哈希码 / 等于 .javadoc 中指定的合约Object。

  2. 当对象的哈希码是哈希表中的键时，它不能更改的附加约束。

后一个约束没有在HashMap javadoc中具体说明，但javadoc forMap说：

注意：如果将可变对象用作映射键，则必须非常小心。equals如果对象的值以影响比较的方式更改，而对象是映射中的键，则不指定映射的行为。

影响相等性（通常）的更改也会影响哈希码。在实现级别，如果条目的键的哈希码发生更改，则该条目现在HashMap通常位于错误的哈希桶中，并且对于执行查找的方法是不可见的。HashMap

于 2012-11-01T12:52:06.820 回答
3

在您的示例中，键是不可变的字符串。所以键的哈希码不会改变。当键的哈希码更改未定义并导致“奇怪”行为时会发生什么。请参见下面的示例，它打印 1、false 和 2。对象保留在集合中，但集合看起来像是损坏了（包含返回 false）。

从Set 的 javadoc中提取：

注意：如果将可变对象用作集合元素，则必须非常小心。如果对象的值以影响等于比较的方式更改，而对象是集合中的一个元素，则不指定集合的​​行为。此禁令的一个特殊情况是不允许集合包含自身作为元素。

public static void main(String args[]) {
    Set<MyObject> set = new HashSet<>();
    MyObject o1 = new MyObject(1);
    set.add(o1);
    o1.i = 2;
    System.out.println(set.size());       //1
    System.out.println(set.contains(o1)); //false
    for (MyObject o : set) {
        System.out.println(o.i);          //2
    }
}

private static class MyObject {
    private int i;

    public MyObject(int i) {
        this.i = i;
    }

    @Override
    public int hashCode() {
        return i;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        final MyObject other = (MyObject) obj;
        if (this.i != other.i) return false;
        return true;
    }
}
于 2012-11-01T12:42:46.457 回答
0

HashSet由HashMap. _

来自javadocs。

该类实现了由哈希表（实际上是 HashMap 实例）支持的 Set 接口。

因此，如果您更改哈希码，我怀疑您是否可以访问该对象。

内部实施细节

的add实现HashSet是

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

关键是元素，值只是一个名为 PRESENT 的虚拟对象

并且contains实现是

public boolean contains(Object o) {
        return map.containsKey(o);
}
于 2012-11-01T12:36:49.860 回答
0

使用 Java 的哈希，根本找不到原始引用。在当前hashcode对应的bucket中查找，没有找到。

contains为了事后恢复，必须迭代Hash keySet，并且必须通过迭代器删除任何方法找不到的key 。最好是从映射中删除键，然后用新键存储值。

于 2012-11-01T12:43:42.167 回答