为什么在LinkedHashMap中迭代桶的速度比HashMap快？

Question

我很难理解这一点.

谷歌搜索,我发现

"HashMap迭代器必须迭代所有桶,包括空桶"

和

"在LinkedHashMap中,所有条目都是双重链接的".

如果是这种情况,为什么唯一的HashMap必须迭代空桶,而不是LinkedHashMap,尽管两者都使用相同的桶概念实现？所有条目都是双重联系的,意思是" 所有的桶和元素都是双重联系的 ",或者只是" 元素是双重联系的 ".

请给我一个解释LinkedHashMap中双向链接桶实现的图表.

提前谢谢了.

Answer 1

LinkedHashMap存储桶节点(条目)保存额外的两个指针(before,after)以维持顺序.

这是创建时的结构.

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

现在让我们添加一个元素.

linkedHashMap.put(1, "obj1");

这里是linkedHashMap标题之前,之后是指向入口对象.

让我们添加另一个元素.

linkedHashMap.put(15, "obj15");

检查指针随红色前一状态的变化

让我们再添加一个元素.

linkedHashMap.put(4, "obj4");

当另一个条目插入相同的哈希时next,每个entry表单中的指针和形式SingleLikedList.

Answer 2

整个要点是有一个单独LinkedHashMap的节点链接列表（仅；存储桶本身没有链接）进行迭代，以便您可以拥有可预测的迭代顺序。所以是的，LinkedHashMap可以更快地迭代。

回答关于“尽管两者都是使用相同的存储桶概念实现的”的问题：只有一个HashMap哈希表，而 a既有哈希表又有链表；按键查找使用哈希表，迭代使用链表。LinkedHashMap

代价LinkedHashMap是你必须保留一个额外的链表（除了哈希表，两者HashMap都有LinkedHashMap），这是额外的空间使用。