Shulou(Shulou.com)06/01 Report--

1. Overview of LinkedHashMap:

LinkedHashMap, a subclass of HashMap, retains the order in which it is inserted, and if you need to output in the same order as you did at input, choose LinkedHashMap.

LinkedHashMap is a hash table and link list implementation of the Map interface with a predictable iteration sequence. This implementation provides all optional mapping operations and allows the use of null values and null keys. This class does not guarantee the order of the mapping, especially it does not guarantee that the order is permanent.

The LinkedHashMap implementation differs from HashMap in that the latter maintains a doubly linked list that runs on all entries. This link list defines the iteration order, which can be the insertion order or the access order.

Note that this implementation is not synchronous. If multiple threads access the hash mapping of a link at the same time, and at least one of them modifies the mapping structurally, it must maintain external synchronization.

According to the order of the elements in the linked list, it can be divided into: the linked list in the insertion order, and the linked list in the access order (calling the get method).

The default is to sort by insertion order. If you specify to sort by access order, after calling the get method, the accessed elements will be moved to the end of the linked list, and continuous access can form a linked list sorted by access order. You can override the removeEldestEntry method to return the true value to specify that the oldest element is removed when the element is inserted.

2. Implementation of LinkedHashMap:

For LinkedHashMap, it inherits from HashMap, and the underlying layer uses a hash table and a two-way linked list to hold all elements. Its basic operation is similar to that of the parent class HashMap, which implements its linked list feature by overriding methods related to the parent class. Let's analyze the source code of LinkedHashMap:

Class structure:

Public class LinkedHashMap extends HashMap implements Map

1) member variables:

LinkedHashMap uses the same hash algorithm as HashMap, but it redefines the element Entry saved in the array. The Entry not only saves the reference of the current object, but also saves the reference of the previous element before and the next element after, thus forming a two-way linked list on the basis of the hash table. Look at the source code:

/ / true means to iterate according to the access order, and false means to iterate according to the insertion order

Private final boolean accessOrder

/ * *

* header element of a two-way linked list.

, /

Private transient Entry header

/ * *

* Entry element of LinkedHashMap.

* inherits the Entry element of HashMap and saves the references to the previous element before and the next element after.

, /

Private static class Entry extends HashMap.Entry {

Entry before, after

……

}

HashMap.Entry:

Static class Entry implements Map.Entry {

Final K key

V value

Entry next

Final int hash

Entry (int h, K k, V v, Entry n) {

Value = v

Next = n

Key = k

Hash = h

}

}

2) initialize:

As can be seen from the source code, in the constructor of LinkedHashMap, the relevant constructor of the parent class HashMap is actually called to construct an underlying stored table array. Such as:

Public LinkedHashMap (int initialCapacity, float loadFactor) {

Super (initialCapacity, loadFactor)

AccessOrder = false

}

Related construction methods in HashMap:

Public HashMap (int initialCapacity, float loadFactor) {

If (initialCapacity

< 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity >

MAXIMUM_CAPACITY)

InitialCapacity = MAXIMUM_CAPACITY

If (loadFactor = initialCapacity

Int capacity = 1

While (capacity

< initialCapacity) capacity = threshold) resize(2 * table.length); } } /** * This override differs from addEntry in that it doesn't resize the * table or remove the eldest entry. */ 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++; } protected boolean removeEldestEntry(Map.Entry eldest) { return false; } 此方法通常不以任何方式修改映射，相反允许映射在其返回值的指引下进行自我修改。如果用此映射构建LRU缓存，则非常方便，它允许映射通过删除旧条目来减少内存损耗。 例如：重写此方法，维持此映射只保存100个条目的稳定状态，在每次添加新条目时删除最旧的条目。 private static final int MAX_ENTRIES = 100; protected boolean removeEldestEntry(Map.Entry eldest) { return size() >

MAX_ENTRIES

}

In fact, LinkedHashMap is almost the same as HashMap, except that it defines an Entry header, this header is not placed in the Table, it is extra independent. LinkedHashMap implements sorting by insertion order or access order by inheriting Entry in hashMap and adding two attributes Entry before,after, which are combined with header to form a two-way linked list.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.