# 第九章 `Map`接口
> 原文：[Chapter 9 The Map interface](http://greenteapress.com/thinkdast/html/thinkdast010.html)
> 譯者：[飛龍](https://github.com/wizardforcel)
> 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/)
> 自豪地采用[谷歌翻譯](https://translate.google.cn/)
在接下來的幾個練習中，我介紹了`Map`接口的幾個實現。其中一個基于哈希表，這可以說是所發明的最神奇的數據結構。另一個是類似的`TreeMap`，不是很神奇，但它有附加功能，它可以按順序迭代元素。
你將有機會實現這些數據結構，然后我們將分析其性能。
但是在我們可以解釋哈希表之前，我們將從一個`Map`開始，它使用鍵值對的`List`來簡單實現。
## 9.1 實現`MyLinearMap`
像往常一樣，我提供啟動代碼，你將填寫缺少的方法。這是`MyLinearMap`類定義的起始：
```java
public class MyLinearMap<K, V> implements Map<K, V> {
private List<Entry> entries = new ArrayList<Entry>();
```
該類使用兩個類型參數，`K`是鍵的類型，`V`是值的類型。`MyLinearMap`實現`Map`，這意味著它必須提供`Map`接口中的方法。
`MyLinearMap`對象具有單個實例變量，`entries`，這是一個`Entry`的`ArrayList`對象。每個`Entry`都包含一個鍵值對。這里是定義：
```java
public class Entry implements Map.Entry<K, V> {
private K key;
private V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
}
```
`Entry`沒有什么，只是一個鍵和一個值的容器。該定義內嵌在`MyLinearList`中，因此它使用相同類型的參數，`K`和`V`。
這就是你做這個練習所需的所有東西，所以讓我們開始吧。
## 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`
這一節中，我展示了上一個練習的答案，并分析核心方法的性能。這里是`findEntry`和`equals`。
```java
private Entry findEntry(Object target) {
for (Entry entry: entries) {
if (equals(target, entry.getKey())) {
return entry;
}
}
return null;
}
private boolean equals(Object target, Object obj) {
if (target == null) {
return obj == null;
}
return target.equals(obj);
}
```
`equals`的運行時間可能取決于`target`鍵和鍵的大小 ，但通常不取決于條目的數量，`n`。那么`equals`是常數時間。
在`findEntry`中，我們可能會很幸運，并在一開始就找到我們要找的鍵，但是我們不能指望它。一般來說，我們要搜索的條目數量與`n`成正比，所以`findEntry`是線性的。
大部分的`MyLinearMap`核心方法使用`findEntry`，包括`put`，`get`，和`remove`。這就是他們的樣子：
```java
public V put(K key, V value) {
Entry entry = findEntry(key);
if (entry == null) {
entries.add(new Entry(key, value));
return null;
} else {
V oldValue = entry.getValue();
entry.setValue(value);
return oldValue;
}
}
public V get(Object key) {
Entry entry = findEntry(key);
if (entry == null) {
return null;
}
return entry.getValue();
}
public V remove(Object key) {
Entry entry = findEntry(key);
if (entry == null) {
return null;
} else {
V value = entry.getValue();
entries.remove(entry);
return value;
}
}
```
`put`調用`findEntry`之后，其他一切都是常數時間。記住這個`entries`是一個`ArrayList`，所以向末尾添加元素平均是常數時間。如果鍵已經在映射中，我們不需要添加條目，但我們必須調用`entry.getValue`和`entry.setValue`，而這些都是常數時間。把它們放在一起，`put`是線性的。
同樣，`get`也是線性的。
`remove`稍微復雜一些，因為`entries.remove`可能需要從一開始或中間刪除`ArrayList`的一個元素，并且需要線性時間。但是沒關系：兩個線性運算仍然是線性的。
總而言之，核心方法都是線性的，這就是為什么我們將這個實現稱為`MyLinearMap`（嗒嗒！）。
如果我們知道輸入的數量很少，這個實現可能會很好，但是我們可以做得更好。實際上，`Map`所有的核心方法都是常數時間的實現。當你第一次聽到這個消息時，可能似乎覺得不可能。實際上我們所說的是，你可以在常數時間內大海撈針，不管海有多大。這是魔法。
我們不是將條目存儲在一個大的`List`中，而是把它們分解成許多短的列表。對于每個鍵，我們將使用哈希碼（在下一節中進行說明）來確定要使用的列表。
使用大量的簡短列表比僅僅使用一個更快，但正如我將解釋的，它不會改變增長級別；核心功能仍然是線性的。但還有一個技巧：如果我們增加列表的數量來限制每個列表的條目數，就會得到一個恒定時間的映射。你會在下一個練習中看到細節，但是首先要了解哈希！
在下一章中，我將介紹一種解決方案，分析`Map`核心方法的性能，并引入更有效的實現。
