第十一章 HashMap

原文：Chapter 11 HashMap

譯者：飛龍

協(xié)議：CC BY-NC-SA 4.0

自豪地采用谷歌翻譯

上一章中，我們寫了一個使用哈希的Map接口的實現(xiàn)致讥。我們期望這個版本更快虫几，因為它搜索的列表較短，但增長順序仍然是線性的。

如果存在n個條目和k個子映射，則子映射的大小平均為n/k，這仍然與n成正比雌隅。但是，如果我們與n一起增加k，我們可以限制n/k的大小澄步。

例如冰蘑，假設(shè)每次n超過k的時候，我們都使k加倍村缸；在這種情況下祠肥，每個映射的條目的平均數(shù)量將小于1，并且?guī)缀蹩偸切∮?code>10梯皿，只要散列函數(shù)能夠很好地展開鍵仇箱。

如果每個子映射的條目數(shù)是不變的，我們可以在常數(shù)時間內(nèi)搜索一個子映射东羹。并且計算散列函數(shù)通常是常數(shù)時間（它可能取決于鍵的大小剂桥，但不取決于鍵的數(shù)量）。這使得Map的核心方法属提， put和get時間不變权逗。

在下一個練習中，您將看到細節(jié)冤议。

11.1 練習 9

在MyHashMap.java中斟薇，我提供了哈希表的大綱，它會按需增長恕酸。這里是定義的起始：

public class MyHashMap<K, V> extends MyBetterMap<K, V> implements Map<K, V> {

    // average number of entries per sub-map before we rehash
    private static final double FACTOR = 1.0;

    @Override
    public V put(K key, V value) {
        V oldValue = super.put(key, value);

        // check if the number of elements per sub-map exceeds the threshold
        if (size() > maps.size() * FACTOR) {
            rehash();
        }
        return oldValue;
    }
}

MyHashMap擴展了MyBetterMap堪滨，所以它繼承了那里定義的方法。它覆蓋的唯一方法是put蕊温，它調(diào)用了超類中的put -- 也就是說袱箱，它調(diào)用了MyBetterMap中的put版本 -- 然后它檢查它是否必須rehash。調(diào)用size返回總數(shù)量n义矛。調(diào)用maps.size返回內(nèi)嵌映射的數(shù)量k发笔。

常數(shù)FACTOR（稱為負載因子）確定每個子映射的平均最大條目數(shù)。如果n > k * FACTOR凉翻，這意味著n/k > FACTOR筐咧，意味著每個子映射的條目數(shù)超過閾值，所以我們調(diào)用rehash噪矛。

運行ant build來編譯源文件。然后運行ant MyHashMapTest铺罢。它應(yīng)該失敗艇挨，因為執(zhí)行rehash會拋出異常。你的工作是填充它韭赘。

填充rehash的主體缩滨，來收集表中的條目，調(diào)整表的大小，然后重新放入條目脉漏。我提供了兩種可能會派上用場的方法：MyBetterMap.makeMaps和MyLinearMap.getEntries苞冯。每次調(diào)用它時，您的解決方案應(yīng)該使映射數(shù)量加倍侧巨。

11.2 分析MyHashMap

如果最大子映射中的條目數(shù)與n/k成正比舅锄，并且k與n成正比，那么多個核心方法就是常數(shù)時間的：

    public boolean containsKey（Object target）{ 
        MyLinearMap <K司忱，V> map = chooseMap（target）; 
        return map.containsKey（target）; 
    } 

    public V get（Object key）{ 
        MyLinearMap <K皇忿，V> map = chooseMap（key）; return map.get（key）; 
    } 
    public V remove（Object key）{ 
        MyLinearMap <K，V> map = chooseMap（key）; 
        return map.remove（key）; 
    }

每個方法都計算鍵的哈希坦仍，這是常數(shù)時間鳍烁，然后在一個子映射上調(diào)用一個方法，這個方法是常數(shù)時間的繁扎。

到現(xiàn)在為止還挺好幔荒。但另一個核心方法，put有點難分析梳玫。當我們不需要rehash時爹梁，它是不變的時間，但是當我們這樣做時汽纠，它是線性的卫键。這樣，它與 3.2 節(jié)中我們分析的ArrayList.add類似虱朵。

出于同樣的原因莉炉，如果我們平攤一系列的調(diào)用，結(jié)果是常數(shù)時間碴犬。同樣絮宁，論證基于攤銷分析（見 3.2 節(jié)）。

假設(shè)子映射的初始數(shù)量k為2服协，負載因子為1∩馨海現(xiàn)在我們來看看put一系列的鍵需要多少工作量。作為基本的“工作單位”偿荷，我們將計算對密鑰哈希窘游，并將其添加到子映射中的次數(shù)。

我們第一次調(diào)用put時跳纳，它需要1個工作單位忍饰。第二次也需要1個單位。第三次我們需要rehash寺庄，所以需要2個單位重新填充現(xiàn)有的鍵艾蓝，和1個單位來對新鍵哈希力崇。

譯者注：可以單獨計算rehash中轉(zhuǎn)移元素的數(shù)量，然后將元素轉(zhuǎn)移的復(fù)雜度和計算哈希的復(fù)雜度相加赢织。

現(xiàn)在哈希表的大小是4亮靴，所以下次調(diào)用put時 ，需要1個工作單位于置。但是下一次我們必須rehash茧吊，需要4個單位來rehash現(xiàn)有的鍵，和1個單位來對新鍵哈希俱两。

圖 11.1 展示了規(guī)律饱狂，對新鍵哈希的正常工作量在底部展示，額外工作量展示為塔樓宪彩。

圖 11.1：向哈希表添加元素的工作量展示

如箭頭所示休讳，如果我們把塔樓推倒，每個積木都會在下一個塔樓之前填滿空間尿孔。結(jié)果似乎2個單位的均勻高度俊柔，這表明put的平均工作量約為2個單位。這意味著put平均是常數(shù)時間活合。

這個圖還顯示了雏婶，當我們rehash的時候，為什么加倍子映射數(shù)量k很重要白指。如果我們只是加上k而不是加倍留晚，那么這些塔樓會靠的太近，他們會開始堆積告嘲。這樣就不會是常數(shù)時間了错维。

11.3 權(quán)衡

我們已經(jīng)表明，containsKey橄唬，get和remove是常數(shù)時間赋焕，put平均為常數(shù)時間。我們應(yīng)該花一點時間來欣賞它有多么出色仰楚。無論哈希表有多大隆判，這些操作的性能幾乎相同。算是這樣吧僧界。

記住侨嘀，我們的分析基于一個簡單的計算模型，其中每個“工作單位”花費相同的時間量捂襟。真正的電腦比這更復(fù)雜飒炎。特別是，當處理足夠小笆豁，適應(yīng)高速緩存的數(shù)據(jù)結(jié)構(gòu)時郎汪，它們通常最快；如果結(jié)構(gòu)不適合高速緩存但仍適合內(nèi)存闯狱，則稍慢一點煞赢；如果結(jié)構(gòu)不適合在內(nèi)存中，則非常慢哄孤。

這個實現(xiàn)的另一個限制是照筑，如果我們得到了一個值而不是一個鍵時，那么散列是不會有幫助的：containsValue是線性的瘦陈，因為它必須搜索所有的子映射凝危。查找一個值并找到相應(yīng)的鍵（或可能的鍵），沒有特別有效的方式晨逝。

還有一個限制：MyLinearMap的一些常數(shù)時間的方法變成了線性的蛾默。例如：

    public void clear() {
        for (int i=0; i<maps.size(); i++) {
            maps.get(i).clear();
        }
    }

clear必須清除所有的子映射，子映射的數(shù)量與n成正比捉貌，所以它是線性的支鸡。幸運的是，這個操作并不常用趁窃，所以在大多數(shù)應(yīng)用中牧挣，這種權(quán)衡是可以接受的。

11.4 分析MyHashMap

在我們繼續(xù)之前醒陆，我們應(yīng)該檢查一下瀑构，MyHashMap.put是否真的是常數(shù)時間。

運行ant build來編譯源文件刨摩。然后運行ant ProfileMapPut寺晌。它使用一系列問題規(guī)模，測量 HashMap.put（由 Java 提供）的運行時間码邻，并在重對數(shù)比例尺上繪制運行時間與問題規(guī)模折剃。如果這個操作是常數(shù)時間，n個操作的總時間應(yīng)該是線性的像屋，所以結(jié)果應(yīng)該是斜率為1的直線怕犁。當我運行這個代碼時，估計的斜率接近1己莺，這與我們的分析一致奏甫。你應(yīng)該得到類似的東西。

修改ProfileMapPut.java凌受，來測量您的MyHashMap實現(xiàn)阵子，而不是 Java 的HashMap。再次運行分析器胜蛉，查看斜率是否接近1挠进。您可能需要調(diào)整startN和endMillis色乾，來找到一系列問題規(guī)模，其中運行時間多于幾毫秒领突，但不超過幾秒暖璧。

當我運行這個代碼時，我感到驚訝：斜率大約為1.7君旦，這表明這個實現(xiàn)不是一直都是常數(shù)的澎办。它包含一個“性能錯誤”。

在閱讀下一節(jié)之前金砍，您應(yīng)該跟蹤錯誤局蚀，修復(fù)錯誤，并確認現(xiàn)在put是常數(shù)時間恕稠，符合預(yù)期琅绅。

11.5 修復(fù)MyHashMap

MyHashMap的問題是size，它繼承自MyBetterMap：

    public int size() {
        int total = 0;
        for (MyLinearMap<K, V> map: maps) {
            total += map.size();
        }
        return total;
    }

為了累計整個大小谱俭，它必須迭代子映射奉件。由于我們增加了子映射的數(shù)量k，隨著條目數(shù)n增加昆著，所以k與n成正比县貌，所以size是線性的。

put也是線性的凑懂，因為它使用size：

    public V put(K key, V value) {
        V oldValue = super.put(key, value);

        if (size() > maps.size() * FACTOR) {
            rehash();
        }
        return oldValue;
    }

如果size是線性的煤痕，我們做的一切都浪費了。

幸運的是接谨，有一個簡單的解決方案摆碉，我們以前看過：我們必須維護實例變量中的條目數(shù)，并且每當我們調(diào)用一個改變它的方法時更新它脓豪。

你會在這本書的倉庫中找到我的解決方案MyFixedHashMap.java巷帝。這是類定義的起始：

public class MyFixedHashMap<K, V> extends MyHashMap<K, V> implements Map<K, V> {

    private int size = 0;

    public void clear() {
        super.clear();
        size = 0;
    }

我們不修改MyHashMap，我定義一個擴展它的新類扫夜。它添加一個新的實例變量size楞泼，它被初始化為零。

更新clear很簡單; 我們在超類中調(diào)用clear（清除子映射）笤闯，然后更新size堕阔。

更新remove和put有點困難，因為當我們調(diào)用超類的該方法颗味，我們不能得知子映射的大小是否改變超陆。這是我的解決方式：

    public V remove(Object key) {
        MyLinearMap<K, V> map = chooseMap(key);
        size -= map.size();
        V oldValue = map.remove(key);
        size += map.size();
        return oldValue;
    }

remove使用chooseMap找到正確的子映射，然后減去子映射的大小浦马。它會在子映射上調(diào)用remove时呀，根據(jù)是否找到了鍵脐区，它可以改變子映射的大小区岗，也可能不會改變它的大小膏孟。但是無論哪種方式窜醉，我們將子映射的新大小加到size，所以最終的size值是正確的瞧预。

重寫的put版本是類似的：

    public V put(K key, V value) {
        MyLinearMap<K, V> map = chooseMap(key);
        size -= map.size();
        V oldValue = map.put(key, value);
        size += map.size();

        if (size() > maps.size() * FACTOR) {
            size = 0;
            rehash();
        }
        return oldValue;
    }

我們在這里也有同樣的問題：當我們在子地圖上調(diào)用put時，我們不知道是否添加了一個新的條目仅政。所以我們使用相同的解決方案垢油，減去舊的大小，然后加上新的大小圆丹。

現(xiàn)在size方法的實現(xiàn)很簡單了：

    public int size() {
        return size;
    }

并且正好是常數(shù)時間滩愁。

當我測量這個解決方案時，我發(fā)現(xiàn)放入n個鍵的總時間正比于n辫封，也就是說硝枉，每個put是常數(shù)時間的，符合預(yù)期倦微。

11.6 UML 類圖

在本章中使用代碼的一個挑戰(zhàn)是妻味，我們有幾個互相依賴的類。以下是類之間的一些關(guān)系：

• MyLinearMap包含一個LinkedList并實現(xiàn)了Map欣福。
• MyBetterMap包含許多MyLinearMap對象并實現(xiàn)了Map责球。
• MyHashMap擴展了MyBetterMap，所以它也包含MyLinearMap對象拓劝，并實現(xiàn)了Map雏逾。
• MyFixedHashMap擴展了MyHashMap并實現(xiàn)了Map。

為了有助于跟蹤這些關(guān)系郑临，軟件工程師經(jīng)常使用 UML 類圖栖博。UML 代表統(tǒng)一建模語言（見 http://thinkdast.com/uml ）∠岫矗“類圖”是由 UML 定義的幾種圖形標準之一仇让。

在類圖中，每個類由一個框表示犀变，類之間的關(guān)系由箭頭表示妹孙。圖 11.2 顯示了使用在線工具 yUML（http://yuml.me/）生成的，上一個練習的 UML 類圖获枝。

圖11.2：本章中的 UML 類圖

不同的關(guān)系由不同的箭頭表示：

• 實心箭頭表示 HAS-A 關(guān)系蠢正。例如，每個MyBetterMap實例包含多個MyLinearMap實例省店，因此它們通過實線箭頭連接嚣崭。
• 空心和實線箭頭表示 IS-A 關(guān)系笨触。例如，MyHashMap擴展 了MyBetterMap雹舀，因此它們通過 IS-A 箭頭連接芦劣。
• 空心和虛線箭頭表示一個類實現(xiàn)了一個接口;在這個圖中，每個類都實現(xiàn) Map说榆。

UML 類圖提供了一種簡潔的方式虚吟，來表示大量類集合的信息。在設(shè)計階段中签财，它們用于交流備選設(shè)計串慰，在實施階段中，用于維護項目的共享思維導(dǎo)圖唱蒸，并在部署過程中記錄設(shè)計邦鲫。