LinkedHashMap source code analysis in Java

1. Basic principles and advantages and disadvantages

LinkedHashMap can record the order in which you insert elements. During traversal, it can traverse it for you in the order in which you insert it.

LinkedHashMap is a subclass of HashMap, so the basic operations are similar to hashmap. However, when inserting, deleting, and replacing key-value pairs, LinkedHashMap will maintain a linked list structure, which is specifically used to record the order of key-value pairs. When we traverse LinkedHashMap, we can traverse the key-value in order.

So, don't look at the name of LinkedHashMap with Linked, its underlying layer is still implemented by arrays.

When deleting an element, it will delete the node at the end of the bidirectional linked list. When querying the element, it is actually iterating over the bidirectional linked list and iterating from the beginning node. Used to maintain the order of two-way linked lists.

There is a very core parameter here: accessOrder.

2. Source code analysis

2.1 put(K key, V value) First insertion

Most of the code logic is exactly the same as hashmap, except that LinkedHashMap rewrites the newNode() method itself.

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
	<K,V> p = new <K,V>(hash, key, value, e);
	linkNodeLast(p);
	return p;
}

Encapsulate the node into an object, and then mount the node using linkNodeLast().

private void linkNodeLast(<K,V> p) {
	<K,V> last = tail;
	tail = p;
	if (last == null)
		head = p;
	else {
		 = last;
		 = p;
	}
}

As you can see here, LinkedHashMap maintains two pointers head and tail, pointing to the head and tail nodes of the sequential linked list.

Whenever we add a key-value to LinkedHashMap, we will mount a sequential node at the end of the sequential link list. The mount process is actually adding a new node to the bidirectional linked list.

2.2 put(K key, V value) Overwrites the existing key

If key1-value1 has been inserted into LinkedHashMap, what will happen if we insert key1-value2 at this time?

The answer is that the insertion order of key1 in LinkedHashMap remains the same, but the value is overwritten.

Regarding the override operation, since we are familiar with the source code of HashMap, we can immediately lock into the following code block in putVal() of hashmap:

if (e != null) { // existing mapping for key
	V oldValue = ;
	if (!onlyIfAbsent || oldValue == null)
		 = value;
	afterNodeAccess(e);
	return oldValue;
}

If the node corresponding to this key can be found before inserting, then the old value in this node is overwritten with the new value, and then afterNodeAccess(e) is executed.

Note that LinkedHashMap rewritten afterNodeAccess(e).

void afterNodeAccess(Node<K,V> e) { // move node to last
	<K,V> last;
	if (accessOrder && (last = tail) != e) {
		<K,V> p =
			(<K,V>)e, b = , a = ;
		 = null;
		if (b == null)
			head = a;
		else
			 = a;
		if (a != null)
			 = b;
		else
			last = b;
		if (last == null)
			head = p;
		else {
			 = last;
			 = p;
		}
		tail = p;
		++modCount;
	}
}

LinkedHashMap has a very important parameter, accessOrder, which can be passed into LinkedHashMap through the constructor through the constructor. accessOrder is equal to false by default, which means that if you override or query this key, the order in which the key is in the linked list will not be changed. When it equals true, it is the opposite. Whenever you override or query this key, LinkedHashMap will move this key to the end of the sequential link list.

2.3 remove

Most of the logic still follows hashmap's removeNode(), but LinkedHashMap rewrites afterNodeRemoval().

void afterNodeRemoval(Node<K,V> e) { // unlink
	<K,V> p =
		(<K,V>)e, b = , a = ;
	 =  = null;
	if (b == null)
		head = a;
	else
		 = a;
	if (a == null)
		tail = b;
	else
		 = b;
}

This is the end of this article about LinkedHashMap source code analysis in Java. For more related LinkedHashMap source code content, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!