可变哈希图密钥是一种危险的做法吗？

这是行不通的。您正在更改键值，因此您基本上将其丢弃。这就像在现实生活中创建一把钥匙和锁，然后更换钥匙并试图将其放回锁中。

这是不安全或不可取的。永远无法检索 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)) 

会失败。

哈希映射使用哈希码和相等性比较来识别具有给定键的某个键值对。如果 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"

其他技术可能具有其他不同的行为。然而，几乎所有的人都会遇到使用可变键的结果不是确定性的情况，这在应用程序中是非常非常糟糕的情况 - 很难调试，甚至更难理解。

正如其他人所解释的那样，这很危险。

避免这种情况的一种方法是让 const 字段显式给出可变对象中的哈希值（这样你就可以对它们的“身份”进行哈希处理，而不是对它们的“状态”进行哈希处理）。您甚至可以或多或少地随机初始化该哈希字段。

另一个技巧是使用地址，例如 作为哈希的基础。(intptr_t) reinterpret_cast<void*>(this)

在所有情况下，您都必须放弃对对象不断变化的状态进行哈希处理。

许多受人尊敬的开发人员（如 Brian Goetz 和 Josh Bloch）都指出：

如果一个对象的 hashCode（） 值可以根据其状态而变化，那么我们 在基于哈希的键中使用此类对象时必须小心 集合，以确保我们不允许其状态在以下情况下更改 它们被用作哈希键。所有基于哈希的集合都假定 对象的哈希值在用作 集合中的键。如果密钥的哈希代码在 在一个集合中，一些不可预测和令人困惑的后果 可以跟随。这在实践中通常不是问题——事实并非如此 使用可变对象（如 List）作为 哈希图。

如果键值对（Entry）存储在HashMap中后密钥的哈希代码发生更改，则映射将无法检索该条目。

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

如果对象的值以影响比较的方式更改，则不指定 Map 的行为，而 object（Mutable） 是一个键。即使对于 Set，使用可变对象作为键也不是一个好主意。

让我们在这里看一个例子：

public class MapKeyShouldntBeMutable {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    Map<Employee,Integer> map=new HashMap<Employee,Integer>();

    Employee e=new Employee();
    Employee e1=new Employee();
    Employee e2=new Employee();
    Employee e3=new Employee();
    Employee e4=new Employee();
    e.setName("one");
    e1.setName("one");
    e2.setName("three");
    e3.setName("four");
    e4.setName("five");
    map.put(e, 24);
    map.put(e1, 25);
    map.put(e2, 26);
    map.put(e3, 27);
    map.put(e4, 28);
    e2.setName("one");
    System.out.println(" is e equals e1 "+e.equals(e1));
    System.out.println(map);
    for(Employee s:map.keySet())
    {
        System.out.println("key : "+s.getName()+":value : "+map.get(s));
    }
}

  }
 class Employee{
String name;

public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}

@Override
public boolean equals(Object o){
    Employee e=(Employee)o;
    if(this.name.equalsIgnoreCase(e.getName()))
            {
        return true;
            }
    return false;

}

public int hashCode() {
    int sum=0;
    if(this.name!=null)
    {
    for(int i=0;i<this.name.toCharArray().length;i++)
    {
        sum=sum+(int)this.name.toCharArray()[i];
    }
    /*System.out.println("name :"+this.name+" code : "+sum);*/
    }
    return sum;

}

}

Here we are trying to add mutable object "Employee" to a map. It will work good if all keys added are distinct.Here I have overridden equals and hashcode for employee class.

See first I have added "e" and then "e1". For both of them equals() will be true and hashcode will be same. So map sees as if the same key is getting added so it should replace the old value with e1's value. Then we have added e2,e3,e4 we are fine as of now.

But when we are changing the value of an already added key i.e "e2" as one ,it becomes a key similar to one added earlier. Now the map will behave wired. Ideally e2 should replace the existing same key i.e e1.But now map takes this as well. And you will get this in o/p :

 is e equals e1 true
{Employee@1aa=28, Employee@1bc=27, Employee@142=25, Employee@142=26}
key : five:value : 28
key : four:value : 27
key : one:value : 25
key : one:value : 25

See here both keys having one showing same value also. So its unexpected.Now run the same programme again by changing which is here ...Now the o/p will be this :e2.setName("diffnt");e2.setName("one");

 is e equals e1 true
{Employee@1aa=28, Employee@1bc=27, Employee@142=25, Employee@27b=26}
key : five:value : 28
key : four:value : 27
key : one:value : 25
key : diffnt:value : null

So by adding changing the mutable key in a map is not encouraged.

我不会重复别人说过的话。是的，这是不可取的。但在我看来，文档说明这一点并不太明显。

您可以在 JavaDoc for the Map 界面上找到它：

注意：如果使用可变对象作为映射，则必须格外小心 钥匙。如果对象的值为 以影响等于比较的方式进行更改，而 object 是映射中的键

可变密钥可能会出现两个截然不同的问题，具体取决于您对行为的期望。

第一个问题：（可能是最微不足道的——但见鬼，它给了我一些我没有想到的问题！

您正在尝试通过更新和修改相同的键对象将键值对放置到映射中。你可以做这样的事情，简单地说：Map<Integer, String>

int key = 0;
loop {
    map.put(key++, newString);
}

我正在重用“对象”来创建地图。这在 Java 中工作正常，因为自动装箱，其中每个新值 都会自动装箱到一个新的 Integer 对象。如果我创建了自己的（可变的）Integer 对象，则不起作用：keykey

MyInteger {
   int value;

   plusOne(){
      value++;
   }
}

然后尝试了相同的方法：

MyInteger key = new MyInteger(0);
loop{
   map.put(key.plusOne(), newString)
}

例如，我的期望是，我映射 和 .在第一个示例中，如果我更改 ，地图将（正确地）给我 .为简单起见，我们假设 just 总是返回相同的值（如果您能以某种方式设法为对象的所有可能状态创建唯一的 hashCode 值，这将不是问题，您应该得到奖励）。在本例中，我调用 ，所以现在地图保存 my 并将其映射到 ，然后我修改并尝试将 .我们有一个问题！是一样的，HashMap 中唯一的键是我的对象，它刚刚被修改为等于 ，所以它覆盖了该键的值，所以现在，而不是带有 和 的映射，我只有！更糟糕的是，如果我改回 ，hashCode 指向 ，但由于 HashMap 的唯一键是我的键对象，它满足相等性检查并返回 ，不如预期。0 -> "a"1 -> "b"int key = 0"a"MyIntegerhashCode()0 -> "a"key"a"key = 11 -> "b"hashCode()MyInteger key10 -> "a"1 -> "b"1 -> "b"key = 01 -> "b""b""a"

如果你像我一样，成为这类问题的牺牲品，那就很难诊断了。为什么？因为如果你有一个像样的功能，它将产生（大部分）唯一的值。在构建地图时，哈希值将在很大程度上解决不等式问题，但如果你有足够的值，最终你会在哈希值上发生冲突，然后你会得到意想不到的、在很大程度上是莫名其妙的结果。由此产生的行为是，它适用于小规模运行，但对大型运行失败。hashCode()

建议：

要找到这种类型的问题，请修改方法，即使是微不足道的（即 -- 显然，在这样做时，请记住，对于两个相等的对象，哈希值应该是相同的*），并查看你是否得到相同的结果 - 因为你应该这样做，如果你不这样做，你的实现可能存在语义错误，使用哈希表。hashCode()= 0

*总是从 hashCode（） 返回 0 应该没有危险（如果有 - 你有语义问题）（尽管这会破坏哈希表的目的）。但这就是重点：hashCode 是一种“快速简便”的平等度量，但并不准确。因此，两个截然不同的对象可能具有相同的 hashCode（） 但不相等。另一方面，两个相等的对象必须始终具有相同的 hashCode（） 值。

p.s. 在 Java 中，根据我的理解，如果你做了这么可怕的事情（就像许多 hashCode（） 冲突一样），它将开始使用红黑树而不是 ArrayList。因此，当您期望 O（1） 查找时，您将得到 O（log（n）） - 这比 ArrayList 更好，后者会给出 O（n）。

第二个问题：

这是大多数其他人似乎都在关注的问题，所以我会尽量简短。在这个用例中，我尝试映射一个键值对，然后在键上做一些工作，然后想回来获取我的值。

期望：被映射，然后我修改并尝试.我希望这会给我.key -> valuekeyget(key)value

对我来说，这似乎很明显是行不通的，但我之前并没有尝试过使用像 Collections 这样的东西作为密钥（并且很快意识到它不起作用）。它不起作用，因为哈希值很可能已经改变，所以你甚至不会在正确的桶中寻找。key

这就是为什么不建议将集合用作密钥的原因。我假设，如果你这样做，你是在试图建立一种多对一的关系。所以我有一个班级（就像在教学中一样），我想让两个小组做两个不同的项目。我想要的是，给定一个小组，他们的项目是什么？很简单，我把类一分为二，我有 和 .但是等等！一个新学生来了，所以我把他们安排在.问题是它现在已被修改，并且其哈希值可能已经更改，因此尝试执行可能会失败，因为它会查看 HashMap 的错误或不存在的存储桶。group1 -> project1group2 -> project2group1group1get(group1)

上述问题的明显解决方案是将事物链接起来——而不是将组用作键，而是给它们一些标签（不会改变），这些标签指向组，从而指向项目：和，等等。g1 -> group1g1 -> project1

附言

请确保为您希望用作键的任何对象定义一个 and 方法（eclipse，我假设大多数 IDE 都可以为您做到这一点）。hashCode()equals(...)

代码示例：

这是一个展示两种不同“问题”行为的类。在本例中，我尝试映射 、 和 （在每种情况下）。在第一个问题中，我通过修改相同的对象来做到这一点，在第二个问题中，我使用唯一的对象，在第二个问题“固定”中，我克隆了这些独特的对象。之后，我获取其中一个“唯一”键（）并对其进行修改以尝试访问地图。我希望这会给我，当关键是.0 -> "a"1 -> "b"2 -> "c"k0a, b, cnull3

但是，发生的情况如下：

map.get(0) map1: 0 -> null, map2: 0 -> a, map3: 0 -> a
map.get(1) map1: 1 -> null, map2: 1 -> b, map3: 1 -> b
map.get(2) map1: 2 -> c, map2: 2 -> a, map3: 2 -> c
map.get(3) map1: 3 -> null, map2: 3 -> null, map3: 3 -> null

第一个映射（“第一个问题”）失败，因为它只保存一个键，该键上次更新并放置为相等，因此它正确返回 when 但返回其他两个（单个键不等于 0 或 1）。第二张地图失败了两次：最明显的是它在我要求时返回（因为它已经被修改了——这是“第二个问题”，当你做这样的事情时，这似乎是显而易见的）。修改后返回时第二次失败（我希望是）。这更多是由于“第一个问题”：存在哈希代码冲突，并且决胜局是相等检查 - 但地图持有，它（显然对我来说 - 理论上对其他人来说可能不同）首先检查并因此返回第一个值，即使它继续检查，也会是匹配的。最后，第 3 张贴图运行良好，因为我强制要求贴图保存唯一键，无论我做什么（通过在插入过程中克隆对象）。2"c"k0 = 2null"b"k0"a"k0 = 2"c"k0"a""c"

我想明确表示我同意，克隆不是解决方案！我只是简单地添加了一个示例，说明为什么地图需要唯一键，以及强制执行唯一键如何“解决”问题。

public class HashMapProblems {

   private int value = 0;

   public HashMapProblems() {
       this(0);
   }

   public HashMapProblems(final int value) {
       super();
       this.value = value;
   }

   public void setValue(final int i) {
       this.value = i;
   }

   @Override
   public int hashCode() {
       return value % 2;
   }

   @Override
   public boolean equals(final Object o) {
       return o instanceof HashMapProblems
            && value == ((HashMapProblems) o).value;
   }

   @Override
   public Object clone() {
       return new HashMapProblems(value);
   }

   public void reset() {
       this.value = 0;
   }

   public static void main(String[] args) {
       final HashMapProblems k0 = new HashMapProblems(0);
       final HashMapProblems k1 = new HashMapProblems(1);
       final HashMapProblems k2 = new HashMapProblems(2);
       final HashMapProblems k = new HashMapProblems();
       final HashMap<HashMapProblems, String> map1 = firstProblem(k);
       final HashMap<HashMapProblems, String> map2 = secondProblem(k0, k1, k2);
       final HashMap<HashMapProblems, String> map3 = secondProblemFixed(k0, k1, k2);

       for (int i = 0; i < 4; ++i) {
           k0.setValue(i);
           System.out.printf(
                "map.get(%d) map1: %d -> %s, map2: %d -> %s, map3: %d -> %s",
                i, i, map1.get(k0), i, map2.get(k0), i, map3.get(k0));
           System.out.println();
       }
   }

   private static HashMap<HashMapProblems, String> firstProblem(
        final HashMapProblems start) {
       start.reset();
       final HashMap<HashMapProblems, String> map = new HashMap<>();

       map.put(start, "a");
       start.setValue(1);
       map.put(start, "b");
       start.setValue(2);
       map.put(start, "c");
       return map;
   }

   private static HashMap<HashMapProblems, String> secondProblem(
        final HashMapProblems... keys) {
       final HashMap<HashMapProblems, String> map = new HashMap<>();

       IntStream.range(0, keys.length).forEach(
            index -> map.put(keys[index], "" + (char) ('a' + index)));
       return map;
   }

   private static HashMap<HashMapProblems, String> secondProblemFixed(
        final HashMapProblems... keys) {
       final HashMap<HashMapProblems, String> map = new HashMap<>();

       IntStream.range(0, keys.length)
            .forEach(index -> map.put((HashMapProblems) keys[index].clone(),
                    "" + (char) ('a' + index)));
       return map;
   }
}

一些注意事项：

在上面应该注意的是，由于我设置函数来拆分奇数和偶数的方式，它只包含两个值。 因此具有相同的 .因此，当我修改并尝试映射被覆盖时 - 仍然存在，因为它存在于不同的存储桶中。map1hashCode()k = 0k = 2hashCode0k = 2k -> "c"k -> "a"k -> "b"

此外，在上面的代码中，有很多不同的方法来检查地图，我鼓励那些好奇的人做一些事情，比如打印出地图的值，然后是值映射的关键（你可能会对你得到的结果感到惊讶）。做一些事情，比如玩改变不同的“唯一”键（即，，和），尝试改变单个键。您还可以看到实际上甚至没有修复，因为您还可以访问密钥（例如通过 ）并修改它们。k0k1k2ksecondProblemFixedMap::keySet

为了使答案紧凑： 根本原因是只计算一次用户密钥对象哈希码的内部哈希值，并将其存储在内部以满足自己的需要。HashMap

地图内数据导航的所有其他操作都由此预先计算的内部哈希值执行。

因此，如果您更改了密钥对象的哈希码（mutate），它仍然会与更改后的密钥对象的哈希码一起很好地存储在地图中（您甚至可以通过观察它并查看更改的哈希代码）。HashMap.keySet()

但是内部哈希当然不会被重新计算，它将是旧的存储哈希，并且地图将无法通过提供的突变键对象新哈希码来定位您的数据。（例如，by 或 ）。HashMapHashMap.get()HashMap.containsKey()

键值对仍将位于映射中，但要取回它，您将需要将数据放入映射时给出的旧哈希代码值。

请注意，您也无法通过直接从 .HashMap.keySet()