第九章 Map接口

原文:Chapter 9 The Map interface

译者:飞龙

协议:CC BY-NC-SA 4.0

自豪地采用谷歌翻译

在接下来的几个练习中,我介绍了Map接口的几个实现。其中一个基于哈希表,这可以说是所发明的最神奇的数据结构。另一个是类似的TreeMap,不是很神奇,但它有附加功能,它可以按顺序迭代元素。

你将有机会实现这些数据结构,然后我们将分析其性能。

但是在我们可以解释哈希表之前,我们将从一个Map开始,它使用键值对的List来简单实现。

9.1 实现MyLinearMap

像往常一样,我提供启动代码,你将填写缺少的方法。这是MyLinearMap类定义的起始:

  1. publicclassMyLinearMap<K, V>implementsMap<K, V>{
  2. privateList<Entry> entries =newArrayList<Entry>();

该类使用两个类型参数,K是键的类型,V是值的类型。MyLinearMap实现Map,这意味着它必须提供Map接口中的方法。

MyLinearMap对象具有单个实例变量,entries,这是一个EntryArrayList对象。每个Entry都包含一个键值对。这里是定义:

  1. publicclassEntryimplementsMap.Entry<K, V>{
  2. private K key;
  3. private V value;
  4. publicEntry(K key, V value){
  5. this.key = key;
  6. this.value = value;
  7. }
  8. @Override
  9. public K getKey(){
  10. return key;
  11. }
  12. @Override
  13. public V getValue(){
  14. return value;
  15. }
  16. }

Entry没有什么,只是一个键和一个值的容器。该定义内嵌在MyLinearList中,因此它使用相同类型的参数,KV

这就是你做这个练习所需的所有东西,所以让我们开始吧。

9.2 练习 7

在本书的仓库中,你将找到此练习的源文件:

  • MyLinearMap.java包含练习的第一部分的起始代码。
  • MyLinearMapTest.java包含MyLinearMap的单元测试。

你还会找到 Ant 构建文件build.xml

运行ant build来编译源文件。然后运行ant MyLinearMapTest;几个测试应该失败,因为你有一些任务要做。

首先,填写findEntry的主体。这是一个辅助方法,不是Map接口的一部分,但是一旦你让它工作,你可以在几种方法中使用它。给定一个目标键(Key),它应该搜索条目(Entry)并返回包含目标的条目(按照键,而不是值),或者如果不存在则返回null。请注意,我提供了equals,正确比较两个键并处理null

你可以再次运行ant MyLinearMapTest,但即使你的findEntry是正确的,测试也不会通过,因为put不完整。

填充put。你应该阅读Map.put的文档,http://thinkdast.com/listput ,以便你知道应该做什么。你可能希望从一个版本开始,其中put始终添加新条目,并且不会修改现有条目;这样你可以先测试简单的情况。或者如果你更加自信,你可以一次写出整个东西。

一旦你put正常工作,测试containsKey应该通过。

阅读Map.get的文档,http://thinkdast.com/listget ,然后填充方法。再次运行测试。

最后,阅读Map.remove的文档,http://thinkdast.com/maprem 并填充方法。

到了这里,所有的测试都应该通过。恭喜!

9.3 分析MyLinearMap

这一节中,我展示了上一个练习的答案,并分析核心方法的性能。这里是findEntryequals

  1. privateEntry findEntry(Object target){
  2. for(Entry entry: entries){
  3. if(equals(target, entry.getKey())){
  4. return entry;
  5. }
  6. }
  7. returnnull;
  8. }
  9. privateboolean equals(Object target,Object obj){
  10. if(target ==null){
  11. return obj ==null;
  12. }
  13. return target.equals(obj);
  14. }

equals的运行时间可能取决于target键和键的大小 ,但通常不取决于条目的数量,n。那么equals是常数时间。

findEntry中,我们可能会很幸运,并在一开始就找到我们要找的键,但是我们不能指望它。一般来说,我们要搜索的条目数量与n成正比,所以findEntry是线性的。

大部分的MyLinearMap核心方法使用findEntry,包括putget,和remove。这就是他们的样子:

  1. public V put(K key, V value){
  2. Entry entry = findEntry(key);
  3. if(entry ==null){
  4. entries.add(newEntry(key, value));
  5. returnnull;
  6. }else{
  7. V oldValue = entry.getValue();
  8. entry.setValue(value);
  9. return oldValue;
  10. }
  11. }
  12. public V get(Object key){
  13. Entry entry = findEntry(key);
  14. if(entry ==null){
  15. returnnull;
  16. }
  17. return entry.getValue();
  18. }
  19. public V remove(Object key){
  20. Entry entry = findEntry(key);
  21. if(entry ==null){
  22. returnnull;
  23. }else{
  24. V value = entry.getValue();
  25. entries.remove(entry);
  26. return value;
  27. }
  28. }

put调用findEntry之后,其他一切都是常数时间。记住这个entries是一个ArrayList,所以降魔为添加元素平均是常数时间。如果键已经在映射中,我们不需要添加条目,但我们必须调用entry.getValueentry.setValue,而这些都是常数时间。把它们放在一起,put是线性的。

同样,get也是线性的。

remove稍微复杂一些,因为entries.remove可能需要从一开始或中间删除ArrayList的一个元素,并且需要线性时间。但是没关系:两个线性运算仍然是线性的。

总而言之,核心方法都是线性的,这就是为什么我们将这个实现称为MyLinearMap(嗒嗒!)。

如果我们知道输入的数量很少,这个实现可能会很好,但是我们可以做得更好。实际上,Map所有的核心方法都是常数时间的实现。当你第一次听到这个消息时,可能似乎觉得不可能。实际上我们所说的是,你可以在常数时间内大海捞针,不管海有多大。这是魔法。

我们不是将条目存储在一个大的List中,而是把它们分解成许多短的列表。对于每个键,我们将使用哈希码(在下一节中进行说明)来确定要使用的列表。
使用大量的简短列表比仅仅使用一个更快,但正如我将解释的,它不会改变增长级别;核心功能仍然是线性的。但还有一个技巧:如果我们增加列表的数量来限制每个列表的条目数,就会得到一个恒定时间的映射。你会在下一个练习中看到细节,但是首先要了解哈希!

在下一章中,我将介绍一种解决方案,分析Map核心方法的性能,并引入更有效的实现。