It is well known that a HashMap is an unordered Map, because each time the key’s Hashcode is mapped to an array of entries, the order iterated is not the order written.

So the JDK introduced a HashMap-based but sequential LinkedHashMap to address scenarios where sorting is required.

The underlying layer is inherited from the HashMap implementation and consists of a bidirectional linked list.

LinkedHashMap can be sorted in two ways:

  • Sort by write order.
  • Sort by access order.

When sorting by access order, each GET will move the accessed value to the end of the list, so that the repeated operation can reach a linked list sorted by access order.

The data structure

	@Test
	public void test(a){
		Map<String, Integer> map = new LinkedHashMap<String, Integer>();
		map.put("1".1); map.put("2".2); map.put("3".3); map.put("4".4); map.put("5".5); System.out.println(map.toString()); }Copy the code

Debugging can see the composition of the map:

Open the source code to see:

    /** * The head of the doubly linked list. */
    private transient Entry<K,V> header;

    /**
     * The iteration ordering method for this linked hash map: <tt>true</tt>
     * for access-order, <tt>false</tt> for insertion-order.
     *
     * @serial* /
    private final boolean accessOrder;
    
    private static class Entry<K.V> extends HashMap.Entry<K.V> {
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;

        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next); }}Copy the code

Entry is inherited from Entry of HashMap, and Pointers to upper and lower nodes are added, thus forming a bidirectional linked list.

There is also a header member variable, which is the head of the bidirectional list.

The above demo is summarized as follows:

The first hashmap-like structure uses the next pointer in Entry for association.

Below is the key to how the LinkedHashMap is organized.

This uses the association between the head node and the rest of the nodes through the after and before Pointers in Entry.

There is also an accessOrder member variable, which defaults to false and sorts by insertion order by default, or by accessOrder when true, and can also be called:

    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
Copy the code

This constructor can display the incoming accessOrder.

A constructor

Constructor of LinkedHashMap:

    public LinkedHashMap(a) {
        super(a); accessOrder =false;
    }
Copy the code

This is the constructor of the called HashMap:

A HashMap implementation:

    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 <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        //HashMap just defines the change method, the implementation is handed over to LinkedHashMap
        init();
    }
Copy the code

You can see that there is an empty init(), which is implemented by LinkedHashMap:

    @Override
    void init(a) {
        header = new Entry<>(-1.null.null.null);
        header.before = header.after = header;
    }
Copy the code

It’s basically just initializing the header.

Put method

Before looking at the put() method of LinkedHashMap, let’s look at the put method of HashMap:

    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for(Entry<K,V> e = table[i]; e ! = null; e = e.next) { Object k;if (e.hash == hash&& ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; // Empty implementation, give LinkedHashMap its own implementation e.reordAccess (this);returnoldValue; } } modCount++; // LinkedHashMap overwrites addEntry(hash, key, value, i);
        returnnull; } // LinkedHashMap overwrites void addEntry(inthash, K key, V value, int bucketIndex) {
        if((size >= threshold) && (null ! = table[bucketIndex])) { resize(2 * table.length);hash= (null ! = key) ?hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex); } // LinkedHashMap overwrites void createEntry(inthash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }       
Copy the code

The main body is implemented using a HashMap, with recordAccess(), addEntry(), and createEntry() overwritten.

Implementation of LinkedHashMap:

        If so, move the current Entry to the end of the list
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if(lm.accessOrder) { lm.modCount++; remove(); addBefore(lm.header); }}// Call the implementation of HashMap and determine if the least used Entry needs to be removed (default not)
    void addEntry(int hash, K key, V value, int bucketIndex) {
        super.addEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed
        Entry<K,V> eldest = header.after;
        if(removeEldestEntry(eldest)) { removeEntryForKey(eldest.key); }}void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<>(hash, key, value, old);
        // Add the new Entry to the header bidirectional list
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
    }
    
        // Write to the bidirectional list
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }  
        
Copy the code

The get method

LinkedHashMap’s get() method has also been rewritten:

    public V get(Object key) {
        Entry<K,V> e = (Entry<K,V>)getEntry(key);
        if (e == null)
            return null;
            
        // If the list is sorted by access order, move the current Entry to the head of the list.
        e.recordAccess(this);
        return e.value;
    }
    
    void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        if (lm.accessOrder) {
            lm.modCount++;
            
            / / delete
            remove();
            // Add to the headeraddBefore(lm.header); }}Copy the code

Clearing () is simpler:

    // All you need to do is point the pointer to yourself. The original Entry is automatically reclaimed by the JVM when it is not referenced.
    public void clear(a) {
        super.clear();
        header.before = header.after = header;
    }
Copy the code

conclusion

In general, LinkedHashMap is an extension of HashMap, using bidirectional linked lists to ensure orderliness.

Because it inherits from HashMap, some of the problems of HashMap LinkedHashMap also exist, such as not supporting concurrency.

extra

Recently in the summary of some Java related knowledge points, interested friends can maintain together.

Address: github.com/crossoverJi…