1. Overview
In Java, LinkedHashMap is a powerful tool for maintaining key-value pairs while preserving the order of insertion. One common requirement is to access the first or last entry in a LinkedHashMap.
In this tutorial, we’ll explore various approaches to achieving this.
2. Preparing a LinkedHashMap Example
Before diving into the implementation for accessing the first and last entries in a LinkedHashMap, let’s briefly review the characteristics of LinkedHashMap.
First, LinkedHashMap is a part of the Java Collections Framework and extends the HashMap class. Furthermore, unlike a regular HashMap, a LinkedHashMap maintains the order of elements in the order in which they were inserted.
Depending on the constructor we use, this order can be either the insertion order or the access order. Simply put, the insertion order means that the elements are ordered according to when they’re added to the LinkedHashMap, while the access order implies that the elements are ordered by the frequency of access, with the most recently accessed elements appearing last.
In this tutorial, we’ll take an insertion-order LinkedHashMap as an example to demonstrate how to obtain the first and the last entries. But, the solutions work for access-order LinkedHashMaps too.
So, next, let’s prepare a LinkedHashMap object example:
static final LinkedHashMap<String, String> THE_MAP = new LinkedHashMap<>();
static {
THE_MAP.put("key one", "a1 b1 c1");
THE_MAP.put("key two", "a2 b2 c2");
THE_MAP.put("key three", "a3 b3 c3");
THE_MAP.put("key four", "a4 b4 c4");
}
As the example above shows, we used a static block to initialize the THE_MAP object.
For simplicity, in this tutorial, we assume the LinkedHashMap object isn’t null or empty. Also, we’ll leverage unit test assertions to verify whether each approach produces the expected result.
3. Iterating Through Map Entries
We know that Map‘s entrySet() method returns all entries in a Set backed by the map. Furthermore, for a LinkedHashMap, the entries in the returned Set follow the entries order in the map object.
Therefore, we can easily access any entry in a LinkedHashMap by iterating *entrySet()*‘s result through an Iterator. For example, linkedHashMap.entrySet().iterator().next() returns the first element in the map:
Entry<String, String> firstEntry = THE_MAP.entrySet().iterator().next();
assertEquals("key one", firstEntry.getKey());
assertEquals("a1 b1 c1", firstEntry.getValue());
However, obtaining the last entry isn’t as simple as how we retrieve the first entry. We must iterate to the last element in the Set to get the last map entry:
Entry<String, String> lastEntry = null;
Iterator<Entry<String,String>> it = THE_MAP.entrySet().iterator();
while (it.hasNext()) {
lastEntry = it.next();
}
assertNotNull(lastEntry);
assertEquals("key four", lastEntry.getKey());
assertEquals("a4 b4 c4", lastEntry.getValue());
In this example, we iterate through the LinkedHashMap using an Iterator object and keep updating the lastEntry variable until we reach the last entry.
Our examples show this approach does the job for an insertion-order LinkedHashMaps. Some may ask if this approach works for access-order LinkedHashMap, too, since access entries in access-order LinkedHashMap may change their order.
Therefore, it’s worth noting that iterating over a view of the map won’t affect the order of iteration of the backing map. This is because only explicit access operations on the map will affect the order, such as map.get(key). So, this approach works for access-order LinkedHashMap as well.
4. Converting Map Entries to an Array
We know that arrays are pretty performant for random access. So, if we can convert the LinkedHashMap entries to an array, we can efficiently access the array’s first and last elements of the array.
We’ve learned we can get all map entries in a Set by calling entrySet(). Thus, Java Collection‘s toArray() method helps us to obtain an array from the Set:
Entry<String, String>[] theArray = new Entry[THE_MAP.size()];
THE_MAP.entrySet().toArray(theArray);
Then, accessing the first and the last elements from the array isn’t a challenge for us:
Entry<String, String> firstEntry = theArray[0];
assertEquals("key one", firstEntry.getKey());
assertEquals("a1 b1 c1", firstEntry.getValue());
Entry<String, String> lastEntry = theArray[THE_MAP.size() - 1];
assertEquals("key four", lastEntry.getKey());
assertEquals("a4 b4 c4", lastEntry.getValue());
5. Using Stream API
Stream API has been introduced since Java 8. It provides a series of convenient methods that allow us to handle collections easily.
Next, let’s see how to get the first entry from a LinkedHashMap using Java Streams:
Entry<String, String> firstEntry = THE_MAP.entrySet().stream().findFirst().get();
assertEquals("key one", firstEntry.getKey());
assertEquals("a1 b1 c1", firstEntry.getValue());
As we can see, we called the stream() method on the entrySet() result to get the map entries’ stream object. Then, findFirst() gives us the first element from the stream. It’s worth noting that the findFirst() method returns an Optional object. Since we knew the map wouldn’t be empty, we called the get() method directly to retrieve the map entry from the Optional object.
There are various ways to get the last element from a Stream instance. For example, we can use the skip() function to solve the problem:
Entry<String, String> lastEntry = THE_MAP.entrySet().stream().skip(THE_MAP.size() - 1).findFirst().get();
assertNotNull(lastEntry);
assertEquals("key four", lastEntry.getKey());
assertEquals("a4 b4 c4", lastEntry.getValue());
The skip() method accepts an int parameter. As its name implies, skip(n) returns a stream discarding the first n elements in the original stream. Therefore, we passed THE_MAP.size() – 1 to the skip() method to *obtain a stream only containing the last element, which is THE_MAP‘s last entry*.
6. Using Reflection API
Until now (Java 21), LinkedHashMap‘s implementation maintains a doubly linked list to hold key-value entries. Also, the head and the tail variables reference the map’s first and last entries:
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;
Therefore, we can simply read these two variables to get the required entries. However, head and tail aren’t public variables. So, we cannot directly access them outside the java.util package.
Fortunately, we have a powerful weapon: Java Reflection API, which allows us to read or write to runtime attributes of classes. For example, we can read the head and the tail fields using reflection to get the map’s first and last entries:
Field head = THE_MAP.getClass().getDeclaredField("head");
head.setAccessible(true);
Entry<String, String> firstEntry = (Entry<String, String>) head.get(THE_MAP);
assertEquals("key one", firstEntry.getKey());
assertEquals("a1 b1 c1", firstEntry.getValue());
Field tail = THE_MAP.getClass().getDeclaredField("tail");
tail.setAccessible(true);
Entry<String, String> lastEntry = (Entry<String, String>) tail.get(THE_MAP);
assertEquals("key four", lastEntry.getKey());
assertEquals("a4 b4 c4", lastEntry.getValue());
We should note that when we run the test above with Java version 9 or later, the test fails with the following error message:
java.lang.reflect.InaccessibleObjectException: Unable to make field transient java.util.LinkedHashMap$Entry
java.util.LinkedHashMap.head accessible: module java.base does not "opens java.util" to unnamed module ....
This is because, since version 9, Java has introduced the modular system, which limits the Reflection API reasonably.
To resolve the reflection illegal access problem, we can add “–add-opens java.base/java.util=ALL-UNNAMED” to the Java command line. As we use Apache Maven as the build tool, we can add this option to the surefire-plugin configuration to ensure the test using reflection runs smoothly with “mvn test“:
<build>
<plugins>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-surefire-plugin</artifactId>
<configuration>
<argLine>
--add-opens java.base/java.util=ALL-UNNAMED
</argLine>
</configuration>
</plugin>
</plugins>
</build>
Additionally, it’s essential to remember that this method hinges on the presence of the “head” and “tail” fields within the LinkedHashMap implementation. In case of potential alterations in Java’s future releases, such as removing or renaming these fields, this solution may no longer be effective.
7. Conclusion
In this article, we initiated our exploration by briefly understanding the key features of a LinkedHashMap. Then, we delved into practical examples to illustrate various methods for retrieving the first and last key-value pairs from a LinkedHashMap.
As always, the complete source code for the examples is available over on GitHub.