A Guide To Linked Hash Map In Java Baeldung

User Manual:

Open the PDF directly: View PDF .
Page Count: 12

Download
Open PDF In Browser	View PDF

16/07/2018

A Guide to LinkedHashMap in Java | Baeldung

(/)

A Guide to LinkedHashMap in Java
Last modi ed: April 29, 2018

by baeldung (/author/baeldung/)
Java (/category/java/)

I just announced the new Spring 5 modules in REST With Spring:
>> CHECK OUT THE COURSE (/rest-with-spring-course#new-modules)

1. Overview

http://www.baeldung.com/java-linked-hashmap

1/12

16/07/2018

A Guide to LinkedHashMap in Java | Baeldung

In this article, we are going to explore the internal implementation of LinkedHashMap class. LinkedHashMap is a common
implementation of Map interface.
This particular implementation is a subclass of HashMap and therefore shares the core building blocks of the HashMap
implementation (/java-hashmap). As a result, it’s highly recommended to brush up on that before proceeding with this article.

2. LinkedHashMap vs HashMap
The LinkedHashMap class is very similar to HashMap in most aspects. However, the linked hash map is based on both hash table and
linked list to enhance the functionality of hash map.
It maintains a doubly-linked list running through all its entries in addition to an underlying array of default size 16.
To maintain the order of elements, the linked hashmap modi es the Map.Entry class of HashMap by adding pointers to the next and
previous entries:
1
2
3
4
5
6

static class Entry extends HashMap.Node {
Entry before, after;
Entry(int hash, K key, V value, Node next) {
super(hash, key, value, next);
}
}

Notice that the Entry class simply adds two pointers; before and after which enable it to hook itself to the linked list. Aside from that, it
uses the Entry class implementation of a the HashMap.
Finally, remember that this linked list de nes the order of iteration, which by default is the order of insertion of elements (insertionorder).

http://www.baeldung.com/java-linked-hashmap

2/12

16/07/2018

A Guide to LinkedHashMap in Java | Baeldung

3. Insertion-Order LinkedHashMap
Let’s have a look at a linked hash map instance which orders its entries according to how they’re inserted into the map. It also
guarantees that this order will be maintained throughout the life cycle of the map:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

@Test
public void givenLinkedHashMap_whenGetsOrderedKeyset_thenCorrect() {
LinkedHashMap map = new LinkedHashMap<>();
map.put(1, null);
map.put(2, null);
map.put(3, null);
map.put(4, null);
map.put(5, null);
Set keys = map.keySet();
Integer[] arr = keys.toArray(new Integer[0]);
for (int i = 0; i < arr.length; i++) {
assertEquals(new Integer(i + 1), arr[i]);
}
}

Here, we’re simply making a rudimentary, non-conclusive test on the ordering of entries in the linked hash map.
We can guarantee that this test will always pass as the insertion order will always be maintained. We cannot make the same
guarantee for a HashMap.
This attribute can be of great advantage in an API that receives any map, makes a copy to manipulate and returns it to the calling code.
If the client needs the returned map to be ordered the same way before calling the API, then a linked hashmap is the way to go.
Insertion order is not a ected if a key is re-inserted into the map.

http://www.baeldung.com/java-linked-hashmap

3/12

16/07/2018

A Guide to LinkedHashMap in Java | Baeldung

4. Access-Order LinkedHashMap
LinkedHashMap provides a special constructor which enables us to specify, among custom load factor (LF) and initial capacity, a
di erent ordering mechanism/strategy called access-order:
1

LinkedHashMap map = new LinkedHashMap<>(16, .75f, true);

The rst parameter is the initial capacity, followed by the load factor and the last param is the ordering mode. So, by passing in true,
we turned out access-order, whereas the default was insertion-order.
This mechanism ensures that the order of iteration of elements is the order in which the elements were last accessed, from leastrecently accessed to most-recently accessed.
And so, building a Least Recently Used (LRU) cache is quite easy and practical with kind of a map. A successful put or get operation
results in an access for the entry:

http://www.baeldung.com/java-linked-hashmap

4/12

16/07/2018

A Guide to LinkedHashMap in Java | Baeldung

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

@Test
public void givenLinkedHashMap_whenAccessOrderWorks_thenCorrect() {
LinkedHashMap map
= new LinkedHashMap<>(16, .75f, true);
map.put(1, null);
map.put(2, null);
map.put(3, null);
map.put(4, null);
map.put(5, null);
Set keys = map.keySet();
assertEquals("[1, 2, 3, 4, 5]", keys.toString());
map.get(4);
assertEquals("[1, 2, 3, 5, 4]", keys.toString());
map.get(1);
assertEquals("[2, 3, 5, 4, 1]", keys.toString());
map.get(3);
assertEquals("[2, 5, 4, 1, 3]", keys.toString());
}

Notice how the order of elements in the key set is transformed as we perform access operations on the map.
Simply put, any access operation on the map results in an order such that the element that was accessed would appear last if an
iteration were to be carried out right away.
After the above examples, it should be obvious that a putAll operation generates one entry access for each of the mappings in the
speci ed map.
Naturally, iteration over a view of the map does’t a ect the order of iteration of the backing map; only explicit access operations on
the map will a ect the order.

LinkedHashMap also provides a mechanism for maintaining a xed number of mappings and to keep dropping o the oldest entries in
case a new one needs to be added.
http://www.baeldung.com/java-linked-hashmap

5/12

16/07/2018

A Guide to LinkedHashMap in Java | Baeldung

The removeEldestEntry method may be overridden to enforce this policy for removing stale mappings automatically.
To see this in practice, let us create our own linked hash map class, for the sole purpose of enforcing the removal of stale mappings by
extending LinkedHashMap:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class MyLinkedHashMap extends LinkedHashMap {
private static final int MAX_ENTRIES = 5;
public MyLinkedHashMap(
int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor, accessOrder);
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}
}

Our override above will allow the map to grow to a maximum size of 5 entries. When the size exceeds that, each new entry will be
inserted at the cost of losing the eldest entry in the map i.e. the entry whose last-access time precedes all the other entries:

http://www.baeldung.com/java-linked-hashmap

6/12

16/07/2018

A Guide to LinkedHashMap in Java | Baeldung

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

@Test
public void givenLinkedHashMap_whenRemovesEldestEntry_thenCorrect() {
LinkedHashMap map
= new MyLinkedHashMap<>(16, .75f, true);
map.put(1, null);
map.put(2, null);
map.put(3, null);
map.put(4, null);
map.put(5, null);
Set keys = map.keySet();
assertEquals("[1, 2, 3, 4, 5]", keys.toString());
map.put(6, null);
assertEquals("[2, 3, 4, 5, 6]", keys.toString());
map.put(7, null);
assertEquals("[3, 4, 5, 6, 7]", keys.toString());
map.put(8, null);
assertEquals("[4, 5, 6, 7, 8]", keys.toString());
}

Notice how oldest entries at the start of the key set keep dropping o as we add new ones to the map.

5. Performance Considerations
Just like HashMap, LinkedHashMap performs the basic Map operations of add, remove and contains in constant-time, as long as the
hash function is well-dimensioned. It also accepts a null key as well as null values.
However, this constant-time performance of LinkedHashMap is likely to be a little worse than the constant-time of HashMap due
to the added overhead of maintaining a doubly-linked list.
http://www.baeldung.com/java-linked-hashmap

7/12

16/07/2018

A Guide to LinkedHashMap in Java | Baeldung

Iteration over collection views of LinkedHashMap also takes linear time O(n) similar to that of HashMap. On the ip side,
LinkedHashMap‘s linear time performance during iteration is better than HashMap‘s linear time.
This is because, for LinkedHashMap, n in O(n) is only the number of entries in the map regardless of the capacity. Whereas, for
HashMap, n is capacity and the size summed up, O(size+capacity).
Load Factor and Initial Capacity are de ned precisely as for HashMap. Note, however, that the penalty for choosing an excessively
high value for initial capacity is less severe for LinkedHashMap than for HashMap, as iteration times for this class are una ected by
capacity.

6. Concurrency
Just like HashMap, LinkedHashMap implementation is not synchronized. So if you are going to access it from multiple threads and at
least one of these threads is likely to change it structurally, then it must be externally synchronized.
It’s best to do this at creation:
1

Map m = Collections.synchronizedMap(new LinkedHashMap());

The di erence with HashMap lies in what entails a structural modi cation. In access-ordered linked hash maps, merely calling the
get API results in a structural modi cation. Alongside this, are operations like put and remove.

7. Conclusion
In this article, we have explored Java LinkedHashMap class as one of the foremost implementations of Map interface in terms of usage.
We have also explored its internal workings in terms of the di erence from HashMap which is its superclass.

http://www.baeldung.com/java-linked-hashmap

8/12

16/07/2018

A Guide to LinkedHashMap in Java | Baeldung

Hopefully, after having read this post, you can make more informed and e ective decisions as to which Map implementation to employ
in your use case.
The full source code for all the examples used in this article can be found in the GitHub project
(https://github.com/eugenp/tutorials/tree/master/core-java-collections).

I just announced the new Spring 5 modules in REST With Spring:
>> CHECK OUT THE LESSONS (/rest-with-spring-course#new-modules)

(/wp-content/uploads/2016/05/baeldung-rest-post-footer-main-1.2.0.jpg)
http://www.baeldung.com/java-linked-hashmap

9/12

16/07/2018

A Guide to LinkedHashMap in Java | Baeldung

(/wpcontent/up
loads/2016
/05/baeld
ung-restpostfooter-icn1.0.0.png)

Learning to "Build your API
with Spring"?

Enter your Email Address

>> Get the eBook

CATEGORIES
SPRING (/CATEGORY/SPRING/)
REST (/CATEGORY/REST/)
JAVA (/CATEGORY/JAVA/)
SECURITY (/CATEGORY/SECURITY-2/)
http://www.baeldung.com/java-linked-hashmap

10/12

16/07/2018

A Guide to LinkedHashMap in Java | Baeldung

PERSISTENCE (/CATEGORY/PERSISTENCE/)
JACKSON (/CATEGORY/JACKSON/)
HTTPCLIENT (/CATEGORY/HTTP/)
KOTLIN (/CATEGORY/KOTLIN/)

SERIES
JAVA “BACK TO BASICS” TUTORIAL (/JAVA-TUTORIAL)
JACKSON JSON TUTORIAL (/JACKSON)
HTTPCLIENT 4 TUTORIAL (/HTTPCLIENT-GUIDE)
REST WITH SPRING TUTORIAL (/REST-WITH-SPRING-SERIES/)
SPRING PERSISTENCE TUTORIAL (/PERSISTENCE-WITH-SPRING-SERIES/)
SECURITY WITH SPRING (/SECURITY-SPRING)

ABOUT
ABOUT BAELDUNG (/ABOUT/)
THE COURSES (HTTP://COURSES.BAELDUNG.COM)
CONSULTING WORK (/CONSULTING)
META BAELDUNG (HTTP://META.BAELDUNG.COM/)
THE FULL ARCHIVE (/FULL_ARCHIVE)
WRITE FOR BAELDUNG (/CONTRIBUTION-GUIDELINES)
CONTACT (/CONTACT)
EDITORS (/EDITORS)
MEDIA KIT (PDF) (HTTPS://S3.AMAZONAWS.COM/BAELDUNG.COM/BAELDUNG+-+MEDIA+KIT.PDF)

TERMS OF SERVICE (/TERMS-OF-SERVICE)
PRIVACY POLICY (/PRIVACY-POLICY)

http://www.baeldung.com/java-linked-hashmap

11/12

16/07/2018

A Guide to LinkedHashMap in Java | Baeldung

COMPANY INFO (/BAELDUNG-COMPANY-INFO)

http://www.baeldung.com/java-linked-hashmap

12/12



---

Source Exif Data:

File Type                       : PDF
File Type Extension             : pdf
MIME Type                       : application/pdf
PDF Version                     : 1.4
Linearized                      : No
Page Count                      : 12
Creator                         : Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_5) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/67.0.3396.99 Safari/537.36
Producer                        : Skia/PDF m67
Create Date                     : 2018:07:16 15:54:55+00:00
Modify Date                     : 2018:07:16 15:54:55+00:00

EXIF Metadata provided by EXIF.tools