資料結構思維 第九章 `Map`接口第九章 Map接口

第九章

Map

接口

原文： Chapter 9 The Map interface 譯者： 飛龍 協定： CC BY-NC-SA 4.0 自豪地采用 谷歌翻譯

在接下來的幾個練習中，我介紹了

Map

接口的幾個實作。其中一個基于哈希表，這可以說是所發明的最神奇的資料結構。另一個是類似的

TreeMap

，不是很神奇，但它有附加功能，它可以按順序疊代元素。

你将有機會實作這些資料結構，然後我們将分析其性能。

但是在我們可以解釋哈希表之前，我們将從一個

Map

開始，它使用鍵值對的

List

來簡單實作。

9.1 實作

MyLinearMap

像往常一樣，我提供啟動代碼，你将填寫缺少的方法。這是

MyLinearMap

類定義的起始：

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

都包含一個鍵值對。這裡是定義：

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

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

。這就是他們的樣子：

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

核心方法的性能，并引入更有效的實作。