2014-10-11 84 views
4

我很努力地理解這一點。爲什麼在LinkedHashMap中迭代通過桶比HashMap快?

谷歌搜索,我發現

「HashMap的迭代器遍歷所有的桶,包括 空水桶迭代」 中的LinkedHashMap

」的所有條目倍加鏈接」。

如果這是爲什麼唯一的HashMap必須遍歷空桶而不是LinkedHashMap,儘管兩者都是使用相同的桶概念實現的?所有條目在意義上雙重鏈接「所有的桶和元素雙重鏈接」或只有「元素雙重鏈接」。

請爲我提供一個解釋LinkedHashMap中的雙鏈接實現的圖。

非常感謝提前。

回答

3

整個LinkedHashMap是有節點的單獨的鏈接列表(只;本身是沒有關係的桶),以遍歷,這樣你可以有一個預知的迭代順序。所以是的,LinkedHashMap可以更快地迭代。

要回答你的問題關於「但兩者都使用相同的桶概念實現」:HashMap只有一個哈希表,而LinkedHashMap具有哈希表鏈表;按鍵查找使用散列表,迭代使用鏈表。

LinkedHashMap的權衡是,您必須保留一個額外的鏈接列表(除了散列表,HashMapLinkedHashMap都有),這是額外的空間使用情況。

11

LinkedHashMap存儲桶節點(入口)保存額外的兩個指針(before,after)用於維護順序。

這是創建時的結構。

Map<Integer, String> linkedHashMap = new LinkedHashMap<Integer, String>(); 

LinkedHashMap with no data

現在,讓我們一個元素添加進去。

linkedHashMap.put(1, "obj1"); 

linkedHashMap.put(1, "obj1");linkedHashMap頭之前 這裏,之後指向條目對象。

讓我們添加另一個元素。

linkedHashMap.put(15, "obj15"); 

linkedHashMap.put(15, "obj15");

檢查出紅色與以前的狀態,指針變爲

讓我們添加更多的元素。

linkedHashMap.put(4, "obj4"); 

linkedHashMap.put(4, "obj4");

next指針中的每個entry形成SingleLikedList當另一個條目插入具有相同散列。

相關問題