java - Java中TreeMap和LinkedHashMap的可视化

Question

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

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

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

类似地，对于 LinkedHashMap(实际上应该称为 DoublyLinkedHashMap)，每个桶都有一个自己的双向链表。

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

附言似乎在 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 :它有一个双向链表，按到达顺序强加在带桶的哈希结构之上。嵌套类 Entry延伸HashMap.Node添加before和 after引用。正常的转发迭代遵循 after链。