Data structures in pictures. LinkedHashMap

Hi Habracheloveki!

After a long pause, I will try to continue to visualize data structures in Java. In previous articles were noticed: ArrayList , LinkedList , HashMap . Today, take a look inside LinkedHashMap.



From the name you can guess that this structure is a symbiosis of linked lists and hash maps. Indeed, LinkedHashMap extends the HashMap class and implements the Map interface, but what is it about linked lists? Let's get it right.

Object Creation

Map linkedHashMap = new LinkedHashMap();

Footprint{Objects=3, References=26, Primitives=[int x 4, float, boolean]}
size: 160 bytes

The newly created linkedHashMap object , in addition to properties inherited from HashMap (such as table, loadFactor, threshold, size, entrySet, etc.), also contains two additional. properties:

• header - the "head" of a doubly linked list. At initialization, it indicates itself;
• accessOrder - indicates how access to the elements will be performed when using an iterator. If true , in the order of the last access (more on this at the end of the article). If false, access is in the order in which the elements were inserted.

The constructors of the LinkedHashMap class are quite boring; all their work is reduced to calling the constructor of the parent class and setting the value of the accessOrder property . But the initialization of the header property occurs in the overridden init () method ( now it becomes clear why in the constructors of the HashMap class there is a call to this nothing-doing function ).

void init()
{
    header = new Entry(-1, null, null, null);
    header.before = header.after = header;
}

A new object is created, properties are initialized, you can proceed to adding elements.

Adding Items

linkedHashMap.put(1, "obj1");

Footprint{Objects=7, References=32, Primitives=[char x 4, int x 9, float, boolean]}
size: 256 bytes

When adding an item, the createEntry method (hash, key, value, bucketIndex) is called first (by the chain put () -> addEntry () -> createEntry () )

void createEntry(int hash, K key, V value, int bucketIndex)
{
    HashMap.Entry old = table[bucketIndex];
    Entry e = new Entry(hash, key, value, old);
    table[bucketIndex] = e;
    e.addBefore(header);
    size++;
}

the first three lines add an element (in case of collisions, the addition will occur at the beginning of the chain, we will see later) the fourth line redefines the links of the doubly linked list. Everything that happens next in the addEntry () method either does not represent “functional interest” ¹ or repeats the functionality of the parent class. Add a couple more elements.

linkedHashMap.put(15, "obj15");

Footprint{Objects=11, References=38, Primitives=[float, boolean, char x 9, int x 14]}
size: 352 bytes

linkedHashMap.put(4, "obj4");

Footprint{Objects=11, References=38, Primitives=[float, boolean, char x 9, int x 14]}
size: 448 bytes




When the next element is added, a collision occurs, and the elements with keys 4 and 38 form a chain

linkedHashMap.put(38, "obj38");

Footprint{Objects=20, References=51, Primitives=[float, boolean, char x 18, int x 24]}
size: 560 bytes




I draw your attention that in case of repeated insertion of an element (an element with the same key already exists), the order of access to the elements will not change.

accessOrder == true

Now let's look at an example when the accessOrder property is true . In such a situation, the behavior of LinkedHashMap changes and when you call the get () and put () methods, the order of the elements will be changed - the element to which we refer will be placed at the end.

Map linkedHashMap = new LinkedHashMap(15, 0.75f, true) {{
    put(1, "obj1");
    put(15, "obj15");
    put(4, "obj4");
    put(38, "obj38");
}};
// {1=obj1, 15=obj15, 4=obj4, 38=obj38}
linkedHashMap.get(1); // or linkedHashMap.put(1, "Object1");
// {15=obj15, 4=obj4, 38=obj38, 1=obj1}

Iterators

Everything is pretty banal:

// 1.
Iterator> itr1 = linkedHashMap.entrySet().iterator();
while (itr1.hasNext()) {
    Entry entry = itr1.next();
    System.out.println(entry.getKey() + " = " + entry.getValue());
}
// 2.
Iterator itr2 = linkedHashMap.keySet().iterator();
while(itr2.hasNext())
    System.out.println(itr2.next());
// 3.
Iterator itr3 = linkedHashMap.values().iterator();
while (itr3.hasNext())
    System.out.println(itr3.next());

Well, do not forget about fail-fast. If you have already begun enumerating elements - do not change the contents or take care of synchronization in advance.

Instead of totals

This structure may be slightly inferior in performance to the parent HashMap , while the execution time of the add (), contains (), remove () operations remains constant - O (1). It will take a little more space in memory to store elements and their connections, but this is a very small fee for additional chips.

In general, due to the parent class taking over the main work, there are not many serious differences in the implementation of HashMap and LinkedHashMap . You can mention a couple of small ones:

• The transfer () and containsValue () methods are a little simpler due to the presence of bidirectional communication between elements;
• The LinkedHashMap.Entry class implements the recordRemoval () and recordAccess () methods (the one that puts an element at the end with accessOrder = true ). In HashMap, both of these methods are empty.

References

Source LinkedHashMap
Sources the JDK the OpenJDK 6 & TRADE Source Release - Build b23
Tools for measurements - memory-measurer and the Guava (the Google Core the Libraries).

---

¹ - Calling the removeEldestEntry method (Map.Entry eldest) always returns false . It is assumed that this method can be overridden for any needs, for example, to implement cache structures based on Map (see ExpiringCache ). After removeEldestEntry () returns true , the oldest item will be deleted when max is exceeded. number of items.