Java 中 TreeMap 和 LinkedHashMap 的可视化

Question

我试图了解这些数据结构实际上是如何可视化的。据说 TreeMap 将条目按 自然顺序 [键] 和 LinkedHashMap 将条目放在顺序它们被插入其中。

我的问题是，对这些数据结构中的每一个的迭代是否意味着遍历所有分布在所有桶中的元素（或内部数组)?

我的理解是，例如，在 TreeMap 的情况下，具有相同 hashcode 的元素被放置在 Tree[=44] 中=]结构[某种]。因此，如果 TreeMap 在 6 中的 16 个索引 [在其桶数组中] 中有元素，它将包含 6 Tree的 -- 每人一个。

类似地，在 LinkedHashMap 的情况下（实际上应该称为 DoublyLinkedHashMap），每个桶都会有一个自己的双向链表。

那么，迭代实际上是如何发生的？它是发生在 all 所有桶中的元素上还是仅发生在单个桶中的元素上？我的假设错了吗？

P.S。似乎在 Java 8、HashMap 实现中使用了 Tree 或 LinkedList，具体取决于每个桶的元素数量分别包含多于8个或少于6个元素！

Answer 1

正常实施的源代码在 Oracle JDK 安装附带的 src.zip 文件中。

TreeMap：如其文档中所示，它是一棵红黑树。对键进行简单前向迭代的关键代码是方法 static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t)。它以左-父-右的顺序递归地扫描树。这取决于根据键顺序插入树中的节点的排序。

LinkedHashMap：它有一个按到达顺序强加在带桶的哈希结构顶部的双向链表。嵌套的 class Entry 扩展 HashMap.Node 以添加 before 和 after 引用。正常的前向迭代遵循 after 链。

Answer 2

补充的答案：

向 LinkedHashMap 添加可视化（这适用于 Java 7 和 Java 8 是不同的），假设元素是按 A、B、...、E 的顺序添加的（并假设 A 的哈希码使得它落在桶 0 中或 D 有一个哈希码放在桶 3 中），具有 4 个箱的 HashMap 将具有以下布局（“|” 表示next 属性 variable in HashMap.Entry<K, V> in the bucket linked list):

║ 0 ║ 1 ║ 2 ║ 3 ║ 
╠═══╬═══╬═══╬═══╬
║ A ║   ║ B ║ D ║
╠═|═╬═══╬═|═╬═|═╬
║ E ║   ║ C ║nul║
╠═|═╬═══╬═|═╬═══╬
║nul║   ║nul║   ║    
╠═══╬═══╬═══╬═══╬

此外，每个元素 A...E 将有两个额外的引用（LinkedHashMap.Entry<K, V> 之后和之前）：

A---->B---->C---->D---->E      
^____|^____|^____|^____|

因此，每个 LinkedHashMap.Entry<K, V> 总共有 3 个引用：next、after 和 before。因此，只有一个元素，即 A（LinkedHashMap.Entry<K, V> 类型），具有三个引用。 TreeMap 也有三个引用，但它们出于不同目的引用了其他 TreeMap.Entry<K, V>：parent、left 和 right.

Java 中 TreeMap 和 LinkedHashMap 的可视化

Visualization of TreeMap and LinkedHashMap in Java

java

treemap

linkedhashmap

data-structures