Visualization of TreeMap and LinkedHashMap in Java

Question

I am trying to understand how these data structures actually are visualized. It is said that TreeMap puts the entries in natural order [of keys] and LinkedHashMap puts entries in the order in which they are inserted.

My question is, does the iteration over each of these data structures mean traversing over all the elements spread over all the buckets (or inner array)?

My understanding was that, for instance, in case of TreeMap, elements with an identical hashcode are placed in a Tree structure [of some sort]. Therefore, if a TreeMap has elements in 6 out of 16 indexes [in its bucket array], it would contain 6 Tree's -- one for each.

Similarly, in case of LinkedHashMap (which should have been called DoublyLinkedHashMap in reality), each bucket would have a doubly linked list of its own.

So, how does iteration actually take place? Does it happen over all the elements in all the buckets or only over elements of a single bucket? Am I wrong in my assumption?

P.S. And it seems like in Java 8, HashMap implementation uses a Tree or LinkedList depending on the number of elements for each bucket containing more than 8 or less than 6 elements, respectively!

Answer 1

The source code for the normal implementations is in the src.zip file that comes with the Oracle JDK installs.

TreeMap: As indicated in its documentation, it is a Red-Black tree. The critical code for simple forwards iteration over the keys is the method static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t). It recursively scans the tree, in the order left-parent-right. It depends for ordering on nodes being inserted in the tree according to their key order.

LinkedHashMap: It has a doubly linked list in arrival order imposed on top of a hash structure with buckets. The nested class Entry extends HashMap.Node to add before and after references. Normal forwards iteration follows the after chain.

Answer 2

To complement @patricia-shanahan's answer:

To add a visualization to LinkedHashMap (this is for Java 7 and older as Java 8 is different), assuming the elements were added in order of A, B, ..., E (and assuming A has a hashcode that makes it fall in bucket 0 or D has a hashcode that places in bucket 3), a HashMap with 4 bins would have the following layout ("|" represents next property variable in HashMap.Entry<K, V> in the bucket linked list):

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

In addition, each of the elements, A...E, would have two additional references (LinkedHashMap.Entry<K, V> of after and before):

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

So in total, each LinkedHashMap.Entry<K, V> would have 3 references: next, after, and before. Therefore, there is a single element, i.e. A (of type LinkedHashMap.Entry<K, V>), with three references. TreeMap has also three references but they reference other TreeMap.Entry<K, V>'s differently for different purpose: parent, left, and right.