在哈希表中使用可变对象作为键是不好的做法吗？当你尝试使用已经被修改以改变其哈希码的键从哈希表中检索值时会发生什么？
例如，给定以下代码：
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)会发生什么？这样做是否安全或可行？或者这种行为是否取决于编程语言？
如果一个对象的hashCode()值会根据其状态变化，则在将这些对象用作哈希键时，我们必须小心，以确保在使用它们作为哈希键时不允许其状态发生更改。所有基于哈希的集合都假定一个对象的哈希值在其作为集合中的键使用期间不会更改。如果某个键的哈希码在其在集合中的使用过程中发生变化，则可能会导致一些不可预测和混乱的后果。这在实践中通常不是问题——不常见的做法是将像List这样的可变对象用作HashMap中的键。
java.util.Map：“注意：如果可变对象被用作映射键，则必须非常小心。如果在对象作为映射中的键时以一种影响 equals 比较的方式更改了对象的值，则映射的行为未指定。” - sleske这不安全也不可取。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;
}
Key key1 = new Key(0, 0);
map.put(key1, value1);
key1.setA(5);
Key key2 = new Key(0, 0);
map.get(key2);
if(entry != null && entry.getKey().equals(key))
会失败。
哈希映射使用哈希码和相等比较来识别具有给定键的特定键值对。如果哈希映射将键作为对可变对象的引用，则在使用相同实例检索值的情况下，它将起作用。但是请考虑以下情况：
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"
其他技术可能会有不同的行为。然而，几乎所有技术都会遇到使用可变键的结果不确定的情况，这是应用程序中非常糟糕的情况 - 很难调试，甚至更难理解。
如果键值对（Entry）存储在HashMap中后，键的哈希码发生改变，则该Map将无法检索到该Entry。
如果键对象是可变的，则键的哈希码可能会发生变化。在HashMap中使用可变键可能导致数据丢失。
这样做是不可行的。因为你改变了钥匙的值，相当于将其丢失。这就像制作一把实物的钥匙和锁，然后更换钥匙并试图将其放回锁中。
正如其他人所解释的，这是非常危险的。
避免这种情况的方法是在可变对象中使用const字段明确地给出哈希值（因此您将基于它们的“标识”而不是其“状态”进行哈希）。您甚至可以更或多或少地随机初始化该哈希字段。
另一个技巧是使用地址，例如 (intptr_t) reinterpret_cast<void*>(this) 作为哈希的基础。
在所有情况下，您必须放弃对对象的变化状态进行哈希。
对于可变键（mutable key），根据您的预期行为，可能会出现两个非常不同的问题。
第一个问题：（可能是最琐碎的问题，但它让我遇到了一些我没有考虑过的问题！）
您正在尝试通过更新和修改相同的键对象将键值对放入映射中。您可能会执行类似以下代码的操作：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)
}
如果像我一样陷入这种问题，它很难进行诊断。为什么？因为如果你有一个不错的hashCode()函数，它将生成（大多数）唯一值。哈希值在构造映射时很好地解决了不等式问题，但是如果你有足够的值，最终会在哈希值上发生碰撞，然后你将得到意外和主要无法解释的结果。 结果行为是它适用于小运行但对于大运行失败。
建议：
要查找此类问题，请修改hashCode()方法，甚至可以是微不足道的（即= 0 - 显然，在执行此操作时，请记住哈希值应该相同于两个相等对象*），并查看您是否获得相同的结果--因为您应该获得，如果您没有获得，则可能存在使用哈希表的实现的语义错误。
*如果总是从hashCode()返回0（尽管这会破坏哈希表的目的），则不应该有危险（如果有危险，那么您有语义问题）。 但这就是重点：hashCode是一种“快速简便”的相等性测量方法，而不是确切的方法。 因此，两个非常不同的对象可能具有相同的hashCode()，但却不相等。 另一方面，两个相等的对象必须始终具有相同的hashCode()值。
p.s. 据我了解，在Java中，如果您做出这样可怕的事情（例如有许多hashCode()冲突），它将开始使用红黑树而不是ArrayList。 所以当您期望O（1）查找时，您将得到O（log（n））-这比ArrayList更好，后者会给出O（n）。
第二个问题：
这似乎是大多数其他人关注的问题，所以我会尝试简要说明一下。 在此用例中，我尝试映射键值对，然后对键执行一些操作，然后想回来获取我的值。
期望：映射key -> value，然后我修改key并尝试get(key)。 我期望会给我value。
对我来说，这似乎很明显行不通，但我并不排除之前曾尝试过将集合作为键使用（并很快意识到它行不通）。 这并不起作用，因为key的哈希值很可能已经改变，因此您甚至都不会在正确的桶中查找。
这就是为什么不建议使用集合作为键的原因。 我会假设，如果您这样做，正在尝试建立多对一关系。 因此，我有一个类（如教学），我希望两个小组进行两个不同的项目。 我想要的是，给定一个小组，他们的项目是什么？ 简单，我把班级分成两部分，然后我有group1 -> project1和group2 -> project2。 但等等！ 一个新学生到达，所以我把他们放在group1中。 问题在于group1现在已被修改，而且很可能其哈希值已更改，因此尝试执行get(group1)可能会失败，因为它将在HashMap的错误或不存在的桶中查找。
上述问题的明显解决方案是链接事物-而不是使用小组作为键，给它们标签（不更改）指向小组，因此指向项目：g1 -> group1和g1 -> project1等。
p.s.
请确保为您希望用作键的任何对象定义hashCode()和equals(...)方法（Eclipse和我假设大多数IDE都可以为您完成此操作）。
代码示例：
这是一个展示两种不同“问题”行为的类。在这种情况下，我尝试将0 ->“a”，1 ->“b”和2 ->“c”映射到它们各自的对象中。在第一个问题中，我通过修改相同的对象来实现，而在第二个问题中，我使用唯一的对象，在第二个问题“已修复”的情况下，我克隆了这些唯一的对象。之后，我取其中一个“唯一”的键（k0）并修改它以尝试访问该映射。当键为3时，我期望会得到a，b，c和null。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
2，因此当k0 = 2时，它正确地返回"c"，但对于其他两个键则返回null（单个键不等于0或1）。第二个映射有两个错误：最明显的是，当我要求k0时，它返回"b"（因为它已被修改-这是“第二个问题”，当你做这样的事情时似乎很明显）。它第二次失败是在修改k0 = 2后返回"a"（我希望它是"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;
}
}
一些注意事项：
需要注意的是，上面的例子中map1只保存了两个值，这是由于我设置了hashCode()函数来区分奇数和偶数。因此，k = 0和k = 2具有相同的hashCode值0。因此，当我修改k = 2并尝试将k -> "c"映射到k -> "a"时，映射k -> "b"仍然存在，因为它存在于另一个桶中。
此外，在上面的代码中，有许多不同的方法可以检查映射表，我鼓励那些好奇心强的人做一些事情，例如打印出映射表的值，然后打印键值映射（你可能会惊讶于得到的结果）。尝试更改不同的“唯一”键（即k0、k1和k2），尝试更改单个键k。您还可以看看即使secondProblemFixed已经被“修复”，实际上它也没有真正解决，因为您还可以通过Map::keySet获得访问键，并对它们进行修改。
clone()方法和Cloneable接口。并非在所有情况下都有帮助，因为还有其他方法可以突变存储的键（例如，keySet()或entrySet()）。 - Clockwork-Museget()，则不能保证会返回任何一个值。添加具有此类键的操作只是调用get()的特殊情况，因为地图本质上在内部执行此操作以查找是否需要替换。从地图的角度来看，它不知道您是将相同（变异）引用用作地图中的键，还是使用具有值相等性的单独键。 - Clockwork-Muse注意：如果使用可变对象作为map的键，则必须非常小心。如果更改对象的值以影响equals比较，而该对象是map中的键，则map的行为未指定。
HashMap 只计算一次用户键对象的哈希码并将其存储在内部以供自己使用。HashMap.keySet() 观察到它并查看更改后的哈希码）。HashMap 的内部哈希码当然不会被重新计算，它将是旧的存储值，地图将无法通过提供的突变键对象新哈希码定位您的数据（例如，通过 HashMap.get() 或 HashMap.containsKey()）。HashMap.keySet() 中直接获取的突变键对象获取数据。如果更改对象的值以影响等于比较，而对象（可变）是键，则未指定 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方法将返回相同的值。因此，映射会认为正在添加相同的键，因此应该使用e1的值替换旧值。然后，我们添加了e2、e3、e4，目前为止一切正常。
但是，当我们更改已添加键的值，即“e2”的值为1时，它变成了与之前添加的某个键相似的键。现在，映射将表现出奇怪的行为。理想情况下，e2应该替换现有的相同键，即e1。但现在映射也会接受它。您将在输出中看到这一点：
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");再次运行相同的程序...现在输出将会是这样：
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
因此，不鼓励在映射中更改可变键。