首页 > 代码库 > 一个关于自定义类型作为HashMap的key的问题
一个关于自定义类型作为HashMap的key的问题
在之前的项目需要用到以自定义类型作为HashMap
的key,遇到一个问题:如果修改了已经存储在HashMap
中的实例,会发生什么情况呢?用一段代码来试验:
import java.util.HashMap;import java.util.Map;public class TestHashMap { public static void main(String[] args) { testObjAsKey(); } private static void testObjAsKey() { class Person { public String familyName; public String givenName; public Person(String familyName, String givenName) { this.familyName = familyName; this.givenName = givenName; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((familyName == null) ? 0 : familyName.hashCode()); result = prime * result + ((givenName == null) ? 0 : givenName.hashCode()); return result; } @Override public boolean equals(Object obj) { if (this == obj) { return true; } if (obj == null) { return false; } if (!(obj instanceof Person)) { return false; } Person other = (Person) obj; if (familyName == null) { if (other.familyName != null) { return false; } } else if (!familyName.equals(other.familyName)) { return false; } if (givenName == null) { if (other.givenName != null) { return false; } } else if (!givenName.equals(other.givenName)) { return false; } return true; } @Override public String toString() { return "Person(" + familyName + ", " + givenName + ")"; } } Map<Person, Integer> map = new HashMap<Person, Integer>(); Person person1 = new Person("zhang", "san"); map.put(person1, 1); System.out.println("Value of " + person1 + " is " + map.get(person1)); person1.givenName = "si"; System.out.println("‘zhang san‘ is changed to ‘zhang si‘"); System.out.println("Value of ‘zhang san‘ is " + map.get(new Person("zhang", "san"))); System.out.println("Value of ‘zhang si‘ is " + map.get(new Person("zhang", "si"))); System.out.println("Value of `person1` is " + map.get(person1)); }}
程序的输出是什么?答案见下
Value of Person(zhang, san) is 1‘zhang san‘ is changed to ‘zhang si‘Value of ‘zhang san‘ is nullValue of ‘zhang si‘ is nullValue of `person1` is null
为什么这样呢?这要从HashMap
的实现进行分析。HashMap
使用一个Entry
数组保存内部的元素(Entry
是用来保存<key, value="">对的类型)。数组的每个slot保存一个链表的头指针,这个链表内的元素都是hashCode相同的entry
Entry[] tables +---+ | 0 | -> entry_0_0 -> entry_0_1 -> null +---+ | 1 | -> null +---+ | | ... |n-1| -> entry_n-1_0 -> null +---+
HashMap
的put()
和get()
方法基本原理如下: - put一个元素的时候,根据key的hashCode()
方法计算出hash值,进而算出相应的数组下标,然后将这个新的entry加入到链表中。 - get一个key的时候,根据key的hash值找到相应的数组下标,然后遍历这个链表,并查找和当前key相等的entry。判断两个元素是否相等时使用使用equals()
方法
上面的例子中,在put
操作之后,map
内部的存储是这样的(假设这个元素被存储在了第i个slot):
| | -> null +---+ | i | -> entry<person1("zhang", "san"), 1> -> null +---+ | | -> null
注意,当我们修改了person1
的时候,并没有修改它存储在map
中的位置。也就是说,修改之后的map
的内部存储是这样的:
| | -> null +---+ | i | -> entry<person1("zhang", "si"), 1> -> null +---+ | | -> null
person1
仍然存储在第i个slot里。
当get(new Person("zhang", "si"))
的时候,HashMap
将先根据hash值计算它应该位于第几个slot,比如是j。由于根据Person("zhang", "san")
计算出来的下标是i,i和j很可能是不相同的,那么第j个slot是空的(因为之前只put
了一个元素且位于第i个slot),因此get()
方法将返回null
。
当get(new Person("zhang", "san"))
的时候,HashMap
将计算它应该位于第i个slot,然后在这个链表中查找。这个链表中存储了一个元素,但是当前的key是("zhang", "si")
,使用equals()
方法判断这两个key是否相等时将返回false
,也就是说,HashMap
在第i个slot所维护的链表中没有找到和当前key相等的元素,因此get()
方法将返回null
。
当get(person1)
的时候,因为person1
现在的值是("zhang", "si")
,所以和get(new Person("zhang", "si"))
的情况是完全一样的。
总结一下,上面的分析说明,如果不小心改变了已经存储在HashMap
中的key值,那么将引起潜在的错误。显然,避免这个问题比较好的方法是,如果打算将自己定义的一种数据类型作为key,那么将这个类型设计成不可变的(immutable)。比如Integer
,String
等都是不可变的。