I read about LinkedHashMap and from the description (although very interesting) I couldn't understand how it actually does its job under the hood. As a side note, I know how a HashMap
works underneath in Java.
So I review the source and still can not figure out how it works. Perhaps I am not grasping something fundamental in OOP in this case so bear with me.
To summarize the part that is confusing to me is the following:
The LinkedHashMap
delegates all the calls to its parent HashMap
.
Internally it overrides the HashMap.Entry
to implement the various recordAccess
and recordRemoval
methods which seem to implement the logic of the LinkedHashMap
But the actual Entries
are inside the table of the base class i.e. the HashMap
which instantiates a table of HashMap.Entry
and not of LinkedHashMap.Entry
.
So I can't figure out how the various recordAccess
and recordRemove
etc are actually being called.
So can anyone help me understand what's going on here?
Am I correct to think that somehow the LinkedHashedMap.Entry
is the type of table created by the HashMap
? But how?
UPDATE:
My question is how do the recordAccess
are being called. My experiment on this using a derived version of HashMap
failed for the reason of Shengyuan Lu (+1) - My bad there
UPDATE:
The following which I tried is the same (I think) as what the LinkedHashMap
is doing:
package delete;
public class Base<T> {
Entry<T>[] table;
int idx = 0;
@SuppressWarnings("unchecked")
public Base(){
System.out.println("In base");
table = new Entry[10];
}
public void add(T x){
table[idx] = new Entry(x);
table[idx].doSomething();
}
static class Entry<T>{
T value;
Entry(T x){
this.value = x;
System.out.println("Entry::Base");
}
void doSomething(){
System.out.println("In Entry base, doing something");
}
}
}
public class Derived<T> extends Base<T> {
static class Entry<T> extends Base.Entry<T>{
Entry(T x) {
super(x);
System.out.println("In Entry derived");
}
int val;
@Override
void doSomething() {
System.out.println("In Entry derived doing something really smart!");
}
}
/**
* @param args
*/
public static void main(String[] args) {
Base<String> b = new Derived<String>();
b.add("Test string");
}
}
But it prints:
In base
Entry::Base
In Entry base, doing something
So the derived Entry
is never called.
Is my example different somehow? I can't understand how this works for LinkedHashMap
Simply put, the HashMap stores values by key and provides APIs for adding, retrieving and manipulating stored data in various ways. The implementation is based on the the principles of a hashtable, which sounds a little complex at first but is actually very easy to understand.
How LinkedHashMap Work Internally? Hash: All the input keys are converted into a hash which is a shorter form of the key so that the search and insertion are faster. Key: Since this class extends HashMap, the data is stored in the form of a key-value pair. Therefore, this parameter is the key to the data.
It maintains a linkedlist of the entries in the map in the order in which they were inserted. This helps to maintain iteration order and elements will be returned in the order they were first added in.
LinkedHashMap is the data structure used to store the key-value pairs like HashMap but it guarantees the order of insertion(unlike the HashMap). So the elements are stored in the order of their insertion.
If you define MyLinkedHashMap
under package java.util
, it will compile;)
Because HashMap.HashEntry
is package visibility.
PLUS:
I think the major thing puzzled you is LinkedHashMap.Entry vs HashMap.Entry. The point is LinkedHashMap.Entry is-a HashMap.Entry. Actually HashMap.table stores LinkedHashMap.Entry in LinkedHashMap.
Regarding to recordAccess
and recordRemoval
, they both override HashMap.Entry versions. You could find out the references both in LinkedHashMap and HashMap.
Merge comments here: You sample code is not same as LinkedHashMap
implementation. See LinkedHashMap.addEntry()
instead.
Ctrl+F is your friend here, especially when it allows you to search multiple files at once. recordAccess
is called on the accessed/created entry by the put
and get
methods of the map. (The calls are in HashMap.put
, HashMap.putForNullKey
and LinkedHashMap.get
.) It is only relevant if you use the constructor of the LinkedHashMap that takes a boolean parameter and passed true
to that. The effect of that is, that whenever you touch the map, the touched entry will be moved to the front of the internal linked list.
Quoting the documentation:
A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches. Invoking the put or get method results in an access to the corresponding entry (assuming it exists after the invocation completes). The putAll method generates one entry access for each mapping in the specified map, in the order that key-value mappings are provided by the specified map's entry set iterator. No other methods generate entry accesses. In particular, operations on collection-views do not affect the order of iteration of the backing map.
The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.
Similarly recordRemoval
is called from HashMap.removeEntryForKey
and HashMap.removeMapping
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With