可变的散列表键是一种危险的做法吗？

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

这既不安全也不明智。不能检索由 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 中通常是这种情况。进去。例如，如果键是一个值类型(总是通过值传递) ，结果将会不同:

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 字段显式地提供 hash (这样您就可以在它们的“标识”上而不是在它们的“状态”上进行 hash)。您甚至可以或多或少随机地初始化该哈希字段。

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

在所有情况下，您都必须放弃散列对象的变化状态。

布莱恩•戈茨(Brian Goetz)和乔希•布洛赫(Josh Bloch)等许多颇受尊敬的开发人员指出:

如果对象的 hashCode ()值可以根据其状态更改，那么我们 在基于散列的 集合，以确保我们不允许他们的状态改变时 所有基于散列的集合都假定 对象的哈希值在作为 如果一个密钥的哈希代码发生更改，而 是一个集合，一些不可预知的和令人困惑的结果 这在实践中通常不是一个问题ーー的确不是 使用诸如 List 之类的可变对象作为 HashMap.

如果键值对(Entry)存储在 HashMap 中之后，键的哈希代码发生了更改，那么映射将无法检索 Entry。

如果密钥对象是可变的，那么密钥的散列码可能会发生变化。

如果对象的值以影响等比较的方式更改，而 object (Mutable)是键，则不指定 Map 的行为。即使对于 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;


}


}

这里我们尝试将可变对象“ Employee”添加到映射中。如果添加的所有键都是不同的，那么它将很好地工作。这里我已经重写了针对雇员类的 equals 和 hashcode。

首先我加了“ e”，然后是“ e1”。对于它们两个，equals ()将为 true，hashcode 将为相同。因此 map 看起来好像添加了相同的键，所以它应该用 e1的值替换旧的值。然后我们添加了 e2，e3，e4，我们现在已经很好了。

但是，当我们将已经添加的键(即“ e2”)的值更改为 one 时，它就变成了与前面添加的键类似的键。现在，地图将表现有线。理想情况下，e2应该替换现有的相同密钥，即 e1，但是现在 map 也采用这种方法。你会得到这个 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

看这里两个键有一个显示相同的值也。真是出乎意料。现在通过改变 e2.setName("diffnt");再次运行同样的程序，也就是这里的 e2.setName("one");... 现在 o/p 是这样的:

 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

因此，不鼓励在映射中添加更改可变键的操作。

我不会重复别人说过的话。是的，这是不明智的。但在我看来，文件上哪里写的不是很清楚。

你可以在 用于 Map 接口的 JavaDoc上找到:

注意: 如果使用可变对象作为 map，必须非常小心 如果对象的值为 是否以影响等于比较的方式更改，而 对象是地图中的一个键

根据您对行为的预期，可变密钥可能会出现两个非常不同的问题。

第一个问题: (可能是最微不足道的——但它给我带来了我从未想过的问题!)

您试图通过更新和修改 一样键对象将键值对放入映射中。你可以像 Map<Integer, String>那样简单地说:

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

我正在重用“对象”key来创建一个映射。这在 Java 中可以很好地工作，因为在自动装箱中，key的每个新值都被自动装箱到一个新的 Integer 对象。如果我创建我自己的(可变的) Integer 对象，没有会怎样工作:

MyInteger {
int value;


plusOne(){
value++;
}
}

然后尝试了同样的方法:

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

例如，我的期望是映射 0 -> "a"和 1 -> "b"。在第一个示例中，如果我更改 int key = 0，映射将(正确地)给我 "a"。为了简单起见，我们假设 MyInteger总是返回相同的 hashCode()(如果您能够以某种方式为对象的所有可能状态创建惟一的 hashCode 值，那么这就不是问题，您应该得到一个奖励)。在本例中，我调用 0 -> "a"，因此现在映射保存我的 key并将其映射到 "a"，然后修改 key = 1并尝试放入 1 -> "b"。int key = 01 hashCode()是一样的，HashMap 中唯一的键是我的 1 -> "b"2对象，这个对象刚刚被修改为等于 1 -> "b"3，所以它覆盖了这个键的值，所以现在，不是使用 0 -> "a"和 1 -> "b"的映射，而是使用 1 -> "b" int key = 02。更糟糕的是，如果我变回 1 -> "b"7，hashCode 指向 1 -> "b"，但是由于 HashMap 中唯一的键 int key = 03 my key 对象，它满足了等式检查并返回 1 -> "b"9，而不是预期的 "a"。

如果，像我一样，你成为这种问题的牺牲品，这是难以置信的难以诊断。为什么？因为如果你有一个像样的 hashCode()函数，它将生成(大多数情况下)唯一的值。散列值在构造映射时会很好地解决不等式问题，但是如果你有足够的值，最终你会在散列值上产生冲突，然后你会得到意想不到的、难以解释的结果。由此产生的行为是它适用于小的运行，但失败的较大的。

建议:

为了发现这种类型的问题，修改 hashCode()方法，即使是很小的修改(比如 = 0——当这样做时，请记住两个相等的对象的哈希值应该是相同的 *) ，并且看看是否得到相同的结果——因为应该得到，如果没有得到，那么使用哈希表的实现可能会出现语义错误。

* 从 HashCode ()总是返回0应该没有危险(如果有——您有一个语义问题)(尽管这会破坏散列表的用途)。但这就是问题的关键: hashCode 是一种“快速而简单”的等式度量，它并不精确。所以两个非常不同的对象可以有相同的 HashCode ()但不相等。另一方面，两个相等的对象必须始终具有相同的 HashCode ()值。

附言。在 Java 中，根据我的理解，如果你做了这样一件可怕的事情(因为有很多 HashCode ()冲突) ，它将开始使用一个红黑树，而不是数组列表。所以当您期望 O (1)查找时，您将得到 O (log (n))——这比给出 O (n)的 ArrayList 要好。

第二个问题:

这似乎是大多数人关注的焦点，所以我会尽量简短。在这个用例中，我尝试映射一个键-值对，然后对键做一些工作，然后希望返回并得到我的值。

期望: key -> value被映射，然后我修改 key并尝试 get(key)。我 期待将给我 value。

对我来说，这似乎是显而易见的，这不会工作，但我并没有超过尝试使用像集合这样的东西作为一个关键之前(并很快意识到它不工作)。它不工作，因为很可能 key的 hash 值已经改变，所以您甚至不会在正确的桶中查找。

这就是为什么 非常不建议使用集合作为键的原因。我猜，如果你要这么做你是想建立一种多对一的关系。所以我有一个班级(在教学中) ，我希望两个小组做两个不同的项目。我想要的是，给一个团队，他们的项目是什么？很简单，我把类分成两部分，我有 group1 -> project1和 group2 -> project2。等等！一个新学生来了，所以我把他们放在 group1。问题是 group1现在已经被修改了，而且它的 hash 值可能已经更改，因此尝试执行 get(group1)很可能会失败，因为它将查找 HashMap 的一个错误的或不存在的桶。

对于上述问题，显而易见的解决方案是将事物链接起来——不使用组作为键，而是给它们指向组的标签(这些标签不会改变) ，从而指向项目: g1 -> group1和 g1 -> project1，等等。

附言。

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

代码示例:

下面这个类展示了两种不同的“问题”行为。在这种情况下，我尝试映射 0 -> "a"、 1 -> "b"和 2 -> "c"(在每种情况下)。在第一个问题中，我通过修改相同的对象来完成，在第二个问题中，我使用唯一的对象，在第二个问题“修复”中，我克隆了这些唯一的对象。之后，我采取其中一个“唯一”键(k0)和修改它，以尝试访问地图。我 期待这将给我 a, b, c和 null时，关键是 3。

然而，发生的情况如下:

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

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;
}
}