【Java集合】有序的Map实现——LinkedHashMap

梦里梦外; 2023-06-26 05:33 17阅读 0赞

###### 引言 ######

Map集合的特点是无序的，可重复的。而要想保证Map的有序，如何实现？Map结构下有多个实现类，HashMap是无序的，而LinkedHashMap继承了HashMap，实现了Map的有序存储和获取。下面就看一下LinkedHashMap是如何保证顺序的。

###### 使用 ######

下面是简单的使用，输出结果是按插入顺序排序的：

Map<String,String> map = new LinkedHashMap<>();
    map.put("一月","Jan.");
    map.put("二月","Feb.");
    map.put("三月","Mar.");
    map.put("四月","Apr.");
    map.put("五月","May.");
    Set<Map.Entry<String, String>> set = map.entrySet();
    Iterator<Map.Entry<String, String>> iterator = set.iterator();
    while(iterator.hasNext()) {
        Map.Entry entry = iterator.next();
        String key = (String) entry.getKey();
        String value = (String) entry.getValue();
        System.out.println("key:" + key + ",value:" + value);
    }

###### 实现原理 ######

LinkedHashMap的构造方法如下：

/**
      * 构造一个空的LinkedHashMap，默认按插入顺序排序
      * 初始大小16，负载因子0.75
      */
     public LinkedHashMap() {
     	// 调用HashMap的构造方法，其实就是初始化Entry[] table
         super();
         // 是否基于访问排序，默认为false
         accessOrder = false;
     }

其实HashMap的数据是存在table数组中的，它是一个Entry数组。Entry其实就是封装了key和value，也就是我们put方法参数的key和value会被封装成Entry，然后放到table这个Entry数组中。它有一个类型为Entry的next，它是用于指向下一个Entry的引用，所以table中存储的是Entry的单向链表。

static class Entry<K,V> implements Map.Entry<K,V> {
            final K key;
            V value;
            Entry<K,V> next;
            int hash;
    }

而LinkedHashMap有自己的静态内部类Entry，它继承了HashMap.Entry，定义如下:

static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

与HashMap的结构相比，多了before和after属性，提供了双向链表的功能，从而保证顺序。

LinkedHashMap存储数据是有序的，而且分为两种：插入顺序和访问顺序。accessOrder是指按访问顺序排序，默认为false，所以默认是按插入顺序排序的。

综上，LinkedHashMap构造函数，主要是调用HashMap的构造函数初始化了一个Entry\[\] table，然后调用了自身的init初始化了一个只有头节点的双向链表。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwMzQyMjM_size_16_color_FFFFFF_t_70]

###### 存储 ######

LinkedHashMap并未重写父类HashMap的put方法，而是重写了父类HashMap的put方法调用的子方法void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的双向链接列表的实现。

void addEntry(int hash, K key, V value, int bucketIndex) {  
        // 调用create方法，将新元素以双向链表的的形式加入到映射中。  
        createEntry(hash, key, value, bucketIndex);  
      
        // 删除最近最少使用元素的策略定义  
        Entry<K,V> eldest = header.after;  
        if (removeEldestEntry(eldest)) {  
            removeEntryForKey(eldest.key);  
        } else {  
            if (size >= threshold)  
                resize(2 * table.length);  
        }  
    }  
    
    void createEntry(int hash, K key, V value, int bucketIndex) {  
        HashMap.Entry<K,V> old = table[bucketIndex];  
        Entry<K,V> e = new Entry<K,V>(hash, key, value, old);  
        table[bucketIndex] = e;  
        // 调用元素的addBrefore方法，将元素加入到哈希、双向链接列表。  
        e.addBefore(header);  
        size++;  
    }  
    
    private void addBefore(Entry<K,V> existingEntry) {  
        after  = existingEntry;  
        before = existingEntry.before;  
        before.after = this;  
        after.before = this;  
    }

###### 读取 ######

LinkedHashMap重写了父类HashMap的get方法，实际在调用父类getEntry()方法取得查找的元素后，再判断当排序模式accessOrder为true时，记录访问顺序，将最新访问的元素添加到双向链表的表头，并从原来的位置删除。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。

public V get(Object key) {  
        // 调用父类HashMap的getEntry()方法，取得要查找的元素。  
        Entry<K,V> e = (Entry<K,V>)getEntry(key);  
        if (e == null)  
            return null;  
        // 记录访问顺序。  
        e.recordAccess(this);  
        return e.value;  
    }  
    
    void recordAccess(HashMap<K,V> m) {  
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;  
        // 如果定义了LinkedHashMap的迭代顺序为访问顺序，  
        // 则删除以前位置上的元素，并将最新访问的元素添加到链表表头。  
        if (lm.accessOrder) {  
            lm.modCount++;  
            remove();  
            addBefore(lm.header);  
        }  
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwMzQyMjM_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019123015044912.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwMzQyMjM=,size_16,color_FFFFFF,t_70