Visualizing TreeMap and LinkedHashMap in Java
I am trying to understand how these data structures are actually rendered. It is said to TreeMap
put the records in natural [key] order and LinkedHashMap
put the records in the order in which they are inserted.
My question is, does iterating over each of these data structures mean traversing through all the elements spread across all the buckets (or the internal array)?
My understanding was that, for example, in the case, TreeMap
elements with the same hashcode are placed in a tree structure [kind of]. So if a TreeMap
has elements of 6 out of 16 indices [in its bucket array], it will contain 6 Tree
- one for each.
Likewise, in a case LinkedHashMap
(which really should have been named DoublyLinkedHashMap), each bucket would have a double linked list.
So how does iteration work? Does this happen on all items in all buckets, or only on items in one bucket? Am I wrong in my assumption?
PS And it looks like in Java 8 the implementation HashMap
uses Tree
or LinkedList
depending on the number of elements for each bucket containing more than 8 or less than 6 elements, respectively!
source to share
The source code for common implementations is in the src.zip file that ships with Oracle JDK installations.
TreeMap
: As stated in its documentation, this is a Red-Black tree. The critical code for a simple forward iteration over the keys is the static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t)
. It scans the tree recursively in left and right order. It depends on the ordering of the nodes inserted into the tree according to their key order.
LinkedHashMap
: it has a doubly linked list in order of arrival overlaid on top of a bucket hash structure. The nested class Entry
extends HashMap.Node
to add links before
and after
. Normal forward iteration follows the chain after
.
source to share
To complement @ patricia-shanahan's answer:
To add visualization LinkedHashMap
(this is for Java 7 and older as a Java 8 ), suggesting that elements were added in order A
, B
..., E
(and if A
a hashcode, which causes him to fall into a bucket, or 0 D
is the hash code, which fits in bucket 3), a HashMap
with 4 cells will have the following layout (" | " represents the following property variable in the HashMap.Entry<K, V>
bucket linked list):
║ 0 ║ 1 ║ 2 ║ 3 ║
╠═══╬═══╬═══╬═══╬
║ A ║ ║ B ║ D ║
╠═|═╬═══╬═|═╬═|═╬
║ E ║ ║ C ║nul║
╠═|═╬═══╬═|═╬═══╬
║nul║ ║nul║ ║
╠═══╬═══╬═══╬═══╬
Also, each of the elements A
... E
would have two additional links ( LinkedHashMap.Entry<K, V>
after and before):
A---->B---->C---->D---->E ^____|^____|^____|^____|
Thus, each LinkedHashMap.Entry<K, V>
will have three links: next
, after
and before
. Therefore, there is one element, i.e. A
(type LinkedHashMap.Entry<K, V>
), with three links. TreeMap
also has three links, but they refer to the other TreeMap.Entry<K, V>
in different ways for different purposes: parent
, left
and right
.
source to share