使用Map
我们知道,List是一种顺序列表,如果有一个存储学生Student实例的List,要在List中根据name查找某个指定的Student的分数,应该怎么办?
最简单的方法是遍历List并判断name是否相等,然后返回指定元素:
1 | List<Student> list = ... |
这种需求其实非常常见,即通过一个键去查询对应的值。使用List来实现存在效率非常低的问题,因为平均需要扫描一半的元素才能确定,而Map这种键值(key-value)映射表的数据结构,作用就是能高效通过key快速查找value(元素)。
Map是一种键-值映射表,当我们调用put(K key, V value)方法时,就把key和value做了映射并放入Map。当我们调用V get(K key)时,就可以通过key获取到对应的value。如果key不存在,则返回null。和List类似,Map也是一个接口,最常用的实现类是HashMap。
如果只是想查询某个key是否存在,可以调用boolean containsKey(K key)方法。
如果我们在存储Map映射关系的时候,对同一个key调用两次put()方法,分别放入不同的value,会有什么问题呢?
重复放入key-value并不会有任何问题,但是一个key只能关联一个value。put()方法的签名是V put(K key, V value),如果放入的key已经存在,put()方法会返回被删除的旧的value,否则,返回null。
始终牢记:Map中不存在重复的key,因为放入相同的key,只会把原有的key-value对应的value给替换掉。
此外,在一个Map中,虽然key不能重复,但value是可以重复的:
1 | Map<String, Integer> map = new HashMap<>(); |
遍历Map
对Map来说,要遍历key可以使用for each循环遍历Map实例的keySet()方法返回的Set集合,它包含不重复的key的集合:
1 | public class Main { |
同时遍历key和value可以使用for each循环遍历Map对象的entrySet()集合,它包含每一个key-value映射:
1 | public class Main { |
Map存储的是key-value的映射关系,并且,它不保证顺序。在遍历的时候,遍历的顺序既不一定是put()时放入的key的顺序,也不一定是key的排序顺序。使用Map时,任何依赖顺序的逻辑都是不可靠的。以HashMap为例,假设我们放入"A","B","C"这3个key,遍历的时候,每个key会保证被遍历一次且仅遍历一次,但顺序完全没有保证,甚至对于不同的JDK版本,相同的代码遍历的输出顺序都是不同的!
小结
Map是一种映射表,可以通过key快速查找value。
可以通过for each遍历keySet(),也可以通过for each遍历entrySet(),直接获取key-value。
最常用的一种Map实现是HashMap。
编写equals和hashCode
我们知道Map是一种键-值(key-value)映射表,可以通过key快速查找对应的value。
以HashMap为例,观察下面的代码:
1 | Map<String, Person> map = new HashMap<>(); |
HashMap之所以能根据key直接拿到value,原因是它内部通过空间换时间的方法,用一个大数组存储所有value,并根据key直接计算出value应该存储在哪个索引:
1 | ┌───┐ |
如果key的值为"a",计算得到的索引总是1,因此返回value为Person("Xiao Ming"),如果key的值为"b",计算得到的索引总是5,因此返回value为Person("Xiao Hong"),这样,就不必遍历整个数组,即可直接读取key对应的value。
当我们使用key存取value的时候,就会引出一个问题:
我们放入Map的key是字符串"a",但是,当我们获取Map的value时,传入的变量不一定就是放入的那个key对象。
换句话讲,两个key应该是内容相同,但不一定是同一个对象。测试代码如下:
1 | public class Main { |
因为在Map的内部,对key做比较是通过equals()实现的,这一点和List查找元素需要正确覆写equals()是一样的,即正确使用Map必须保证:作为key的对象必须正确覆写equals()方法。
我们经常使用String作为key,因为String已经正确覆写了equals()方法。但如果我们放入的key是一个自己写的类,就必须保证正确覆写了equals()方法。
我们再思考一下HashMap为什么能通过key直接计算出value存储的索引。相同的key对象(使用equals()判断时返回true)必须要计算出相同的索引,否则,相同的key每次取出的value就不一定对。
通过key计算索引的方式就是调用key对象的hashCode()方法,它返回一个int整数。HashMap正是通过这个方法直接定位key对应的value的索引,继而直接返回value。
因此,正确使用Map必须保证:
- 作为
key的对象必须正确覆写equals()方法,相等的两个key实例调用equals()必须返回true; - 作为
key的对象还必须正确覆写hashCode()方法,且hashCode()方法要严格遵循以下规范:
- 如果两个对象相等,则两个对象的
hashCode()必须相等; - 如果两个对象不相等,则两个对象的
hashCode()尽量不要相等。(减少hash碰撞)
即对应两个实例a和b:
- 如果
a和b相等,那么a.equals(b)一定为true,则a.hashCode()必须等于b.hashCode(); - 如果
a和b不相等,那么a.equals(b)一定为false,则a.hashCode()和b.hashCode()尽量不要相等。
上述第一条规范是正确性,必须保证实现,否则HashMap不能正常工作。
而第二条如果尽量满足,则可以保证查询效率,因为不同的对象,如果返回相同的hashCode(),会造成Map内部存储冲突,使存取的效率下降。
正确编写equals()的方法我们已经在编写equals方法一节中讲过了,以Person类为例:
1 | public class Person { |
把需要比较的字段找出来:
- firstName
- lastName
- age
然后,引用类型使用Objects.equals()比较,基本类型使用==比较。
在正确实现equals()的基础上,我们还需要正确实现hashCode(),即上述3个字段分别相同的实例,hashCode()返回的int必须相同:
1 | public class Person { |
注意到String类已经正确实现了hashCode()方法,我们在计算Person的hashCode()时,反复使用31*h,这样做的目的是为了尽量把不同的Person实例的hashCode()均匀分布到整个int范围。
和实现equals()方法遇到的问题类似,如果firstName或lastName为null,上述代码工作起来就会抛NullPointerException。为了解决这个问题,我们在计算hashCode()的时候,经常借助Objects.hash()来计算:
1 | int hashCode() { |
所以,编写equals()和hashCode()遵循的原则是:
equals()用到的用于比较的每一个字段,都必须在hashCode()中用于计算;equals()中没有使用到的字段,绝不可放在hashCode()中计算。
另外注意,对于放入HashMap的value对象,没有任何要求。
延伸阅读
既然HashMap内部使用了数组,通过计算key的hashCode()直接定位value所在的索引,那么第一个问题来了:hashCode()返回的int范围高达±21亿,先不考虑负数,HashMap内部使用的数组得有多大?
实际上HashMap初始化时默认的数组大小只有16,任何key,无论它的hashCode()有多大,都可以简单地通过:
1 | int index = key.hashCode() & 0xf; // 0xf = 15 |
把索引确定在0~15,即永远不会超出数组范围,上述算法只是一种最简单的实现。
第二个问题:如果添加超过16个key-value到HashMap,数组不够用了怎么办?
添加超过一定数量的key-value时,HashMap会在内部自动扩容,每次扩容一倍,即长度为16的数组扩展为长度32,相应地,需要重新确定hashCode()计算的索引位置。例如,对长度为32的数组计算hashCode()对应的索引,计算方式要改为:
1 | int index = key.hashCode() & 0x1f; // 0x1f = 31 |
由于扩容会导致重新分布已有的key-value,所以,频繁扩容对HashMap的性能影响很大。如果我们确定要使用一个容量为10000个key-value的HashMap,更好的方式是创建HashMap时就指定容量:
1 | Map<String, Integer> map = new HashMap<>(10000); |
虽然指定容量是10000,但HashMap内部的数组长度总是2n,因此,实际数组长度被初始化为比10000大的16384(214)。
在HashMap内部,可能存在不同的key,映射到相同的hashCode(),即相同的数组索引上,肿么办?
我们就假设"a"和"b"这两个key最终计算出的索引都是5,那么,在HashMap的数组中,实际存储的不是一个Person实例,而是一个List,它包含两个Entry,一个是"a"的映射,一个是"b"的映射:
1 | ┌───┐ |
在查找的时候,例如:
1 | Person p = map.get("a"); |
HashMap内部通过"a"找到的实际上是List>,它还需要遍历这个List,并找到一个Entry,它的key字段是"a",才能返回对应的Person实例。
我们把不同的key具有相同的hashCode()的情况称之为哈希冲突。在冲突的时候,一种最简单的解决办法是用List存储hashCode()相同的key-value。显然,如果冲突的概率越大,这个List就越长,Map的get()方法效率就越低,这就是为什么要尽量满足条件二:
如果两个对象不相等,则两个对象的hashCode()尽量不要相等。
hashCode()方法编写得越好,HashMap工作的效率就越高。
小结
要正确使用HashMap,作为key的类必须正确覆写equals()和hashCode()方法;
一个类如果覆写了equals(),就必须覆写hashCode(),并且覆写规则是:
- 如果
equals()返回true,则hashCode()返回值必须相等; - 如果
equals()返回false,则hashCode()返回值尽量不要相等。
实现hashCode()方法可以通过Objects.hashCode()辅助方法实现。
使用EnumMap
因为HashMap是一种通过对key计算hashCode(),通过空间换时间的方式,直接定位到value所在的内部数组的索引,因此,查找效率非常高。
如果作为key的对象是enum类型,那么,还可以使用Java集合库提供的一种EnumMap,它在内部以一个非常紧凑的数组存储value,并且根据enum类型的key直接定位到内部数组的索引,并不需要计算hashCode(),不但效率最高,而且没有额外的空间浪费。
我们以DayOfWeek这个枚举类型为例,为它做一个“翻译”功能:
1 | public class Main { |
使用EnumMap的时候,我们总是用Map接口来引用它,因此,实际上把HashMap和EnumMap互换,在客户端看来没有任何区别。
小结
如果Map的key是enum类型,推荐使用EnumMap,既保证速度,也不浪费空间。
使用EnumMap的时候,根据面向抽象编程的原则,应持有Map接口。
使用TreeMap
我们已经知道,HashMap是一种以空间换时间的映射表,它的实现原理决定了内部的Key是无序的,即遍历HashMap的Key时,其顺序是不可预测的(但每个Key都会遍历一次且仅遍历一次)。
还有一种Map,它在内部会对Key进行排序,这种Map就是SortedMap。注意到SortedMap是接口,它的实现类是TreeMap。
1 | ┌───┐ |
SortedMap保证遍历时以Key的顺序来进行排序。例如,放入的Key是"apple"、"pear"、"orange",遍历的顺序一定是"apple"、"orange"、"pear",因为String默认按字母排序.
使用TreeMap时,放入的Key必须实现Comparable接口。String、Integer这些类已经实现了Comparable接口,因此可以直接作为Key使用。作为Value的对象则没有任何要求。
如果作为Key的class没有实现Comparable接口,那么,必须在创建TreeMap时同时指定一个自定义排序算法:
1 | public class Main { |
注意到Comparator接口要求实现一个比较方法,它负责比较传入的两个元素a和b,如果a<b,则返回负数,通常是-1,如果a==b,则返回0,如果a>b,则返回正数,通常是1。TreeMap内部根据比较结果对Key进行排序。
从上述代码执行结果可知,打印的Key确实是按照Comparator定义的顺序排序的。如果要根据Key查找Value,我们可以传入一个new Person("Bob")作为Key,它会返回对应的Integer值2。
另外,注意到Person类并未覆写equals()和hashCode(),因为TreeMap不使用equals()和hashCode()。
我们来看一个稍微复杂的例子:这次我们定义了Student类,并用分数score进行排序,高分在前:
1 | public class Main { |
在for循环中,我们确实得到了正确的顺序。但是,且慢!根据相同的Key:new Student("Bob", 66)进行查找时,结果为null!
这是怎么肥四?难道TreeMap有问题?遇到TreeMap工作不正常时,我们首先回顾Java编程基本规则:出现问题,不要怀疑Java标准库,要从自身代码找原因。
在这个例子中,TreeMap出现问题,原因其实出在这个Comparator上:
1 | public int compare(Student p1, Student p2) { |
在p1.score和p2.score不相等的时候,它的返回值是正确的,但是,在p1.score和p2.score相等的时候,它并没有返回0!这就是为什么TreeMap工作不正常的原因:TreeMap在比较两个Key是否相等时,依赖Key的compareTo()方法或者Comparator.compare()方法。在两个Key相等时,必须返回0。因此,修改代码如下:
1 | public int compare(Student p1, Student p2) { |
或者直接借助Integer.compare(int, int)也可以返回正确的比较结果。
小结
SortedMap在遍历时严格按照Key的顺序遍历,最常用的实现类是TreeMap;
作为SortedMap的Key必须实现Comparable接口,或者传入Comparator;
要严格按照compare()规范实现比较逻辑,否则,TreeMap将不能正常工作。
本文整理自
仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!





















