可变的hashmap键是危险的做法吗？

Question

将可变对象用作Hashmap键是不好的做法吗？当您尝试使用已修改足以更改其哈希码的密钥从Hashmap检索值时会发生什么？

例如,给定

class Key
{
    int a; //mutable field
    int b; //mutable field

    public int hashcode()
        return foo(a, b);
    // setters setA and setB omitted for brevity
}

用代码

HashMap<Key, Value> map = new HashMap<Key, Value>();

Key key1 = new Key(0, 0);
map.put(key1, value1); // value1 is an instance of Value

key1.setA(5);
key1.setB(10);

如果我们现在打电话map.get(key1)怎么办？这是安全的还是可取的？或者行为是否依赖于语言？

Answer 1

许多备受推崇的开发商如Brian Goetz和Josh Bloch都注意到:

如果对象的hashCode()值可以根据其状态进行更改,那么在使用这些对象作为基于散列的集合中的键时必须小心,以确保在将它们用作散列键时不允许它们的状态发生更改.所有基于散列的集合都假定对象的散列值在用作集合中的键时不会更改.如果密钥的哈希代码在集合中发生变化,则可能会出现一些不可预测且令人困惑的后果.这在实践中通常不是问题 - 通常的做法是使用像List这样的可变对象作为HashMap中的键.

Answer 2

这不安全或不可取.无法检索由key1映射的值.在进行检索时,大多数哈希映射都会执行类似的操作

Object get(Object key) {
    int hash = key.hashCode();
    //simplified, ignores hash collisions,
    Entry entry = getEntry(hash);
    if(entry != null && entry.getKey().equals(key)) {
        return entry.getValue();
    }
    return null;
}

在此示例中,key1.hashcode()现在指向散列表的错误存储桶,您将无法使用key1检索value1.

如果你做过类似的事情,

Key key1 = new Key(0, 0);
map.put(key1, value1);
key1.setA(5);
Key key2 = new Key(0, 0);
map.get(key2);

这也不会检索value1,因为key1和key2不再相等,所以这个检查

    if(entry != null && entry.getKey().equals(key)) 

将失败.

Answer 3

散列映射使用散列码和相等比较来识别具有给定键的某个键值对.如果has映射将键保留为对可变对象的引用,则在使用相同实例来检索值的情况下,它将起作用.但请考虑以下情况:

T keyOne = ...;
T keyTwo = ...;

// At this point keyOne and keyTwo are different instances and 
// keyOne.equals(keyTwo) is true.

HashMap myMap = new HashMap();

myMap.push(keyOne, "Hello");

String s1 = (String) myMap.get(keyOne); // s1 is "Hello"
String s2 = (String) myMap.get(keyTwo); // s2 is "Hello" 
                                        // because keyOne equals keyTwo

mutate(keyOne);

s1 = myMap.get(keyOne); // returns "Hello"
s2 = myMap.get(keyTwo); // not found

如果将密钥存储为引用,则上述情况属实.在Java中通常就是这种情况.例如,在.NET中,如果键是值类型(始终按值传递),则结果将不同:

T keyOne = ...;
T keyTwo = ...;

// At this point keyOne and keyTwo are different instances 
// and keyOne.equals(keyTwo) is true.

Dictionary myMap = new Dictionary();

myMap.Add(keyOne, "Hello");

String s1 = (String) myMap[keyOne]; // s1 is "Hello"
String s2 = (String) myMap[keyTwo]; // s2 is "Hello"
                                    // because keyOne equals keyTwo

mutate(keyOne);

s1 = myMap[keyOne]; // not found
s2 = myMap[keyTwo]; // returns "Hello"

其他技术可能有其他不同的行为.但是,几乎所有这些都会导致使用可变键的结果不确定,这在应用程序中是非常非常糟糕的情况 - 难以调试甚至更难理解.

Answer 4

这不行.您正在更改键值,因此您基本上将其丢弃.它就像创建一个真实的生活密钥并锁定,然后更改密钥并尝试将其放回锁中.

Answer 5

如果键值对（Entry）存储在HashMap中后，key的hash码发生变化，映射将无法检索到Entry。

如果键对象是可变的，则键的哈希码可以更改。HahsMap 中的可变键可能会导致数据丢失。