《Java源码解析》集合框架Map之LinkedHashMap

爱被打了一巴掌 2022-07-13 04:18 197阅读 0赞

> 2016-12-24 16:01  
> 以前都没有贴出来运行环境，今天加上OS和JDK版本，因为发现不同版本实现源码有些许差别：  
> OS : MacOS 10.11  
> JDK: jdk1.7-72

# LinkedHashMap #

## 1. 还是先看看LinkedHashMap类继承结构图 ##

![LinkedHashMap类继承图][LinkedHashMap]

首先说说我对这个类名的理解，其实我觉得就是LinkedList+HashMap特性的集合。LinkedHashMap使用HashMap操作数据结构，又使用LinkedList维护插入元素的先后顺序。

我们知道HashMap对于插入元素的顺序并没有维护，也就是说迭代HashMap的顺序并不是元素插入的顺序，有时候我们期待一个有序的Map集合，这时LinkedHashMap产生了。它虽然增加了时间和空间上的开销，但是通过维护一个运行于所有条目的双向链表，LinkedHashMap保证了元素迭代的顺序。

## 2.LinkedHashMap的基本结构 ##

LinkedHashMap继承自HashMap，首先我们应该很明确两点：  
1. LinkedHashMap可以认为是HashMap+LinkedList，即它使用HashMap操作数据结构，又使用LinkedList维护插入元素的先后顺序。  
2. LinkedHashMap的基本实现思想就是—-多态，LinkedHashMap重写了其父类HashMap的很多方法以实现双向链表的功能。可以说，理解多态，再去理解LinkedHashMap原理会事半功倍；反之也是，对于LinkedHashMap原理的学习，也可以促进和加深对于多态的理解。

## 3. 一些重要点在LinkedHashMap上面的答案 ##

**LinkedHashMap**

<table> 
 <thead> 
  <tr> 
   <th>关注点</th> 
   <th align="center">结论</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>集合底层实现的数据结构</td> 
   <td align="center">数组(HashMap)+双链表</td> 
  </tr> 
  <tr> 
   <td>集合中元素是否允许为空</td> 
   <td align="center">Key和Value都允许为空</td> 
  </tr> 
  <tr> 
   <td>是否允许重复的数据</td> 
   <td align="center">Key会被覆盖，但是Value 允许重复</td> 
  </tr> 
  <tr> 
   <td>是否有序</td> 
   <td align="center">有序(插入顺序与迭代顺序一致)</td> 
  </tr> 
  <tr> 
   <td>是否线程安全。</td> 
   <td align="center">非线程安全</td> 
  </tr> 
 </tbody> 
</table>

## 4.重要属性 ##

前面我们已经知道了LinkedHashMap是继承自HashMap的，所以HashMap的属性，LinkedhashMap直接继承过来了，此外还有一些LinkedHashMap为了实现双链表新加的属性：

//header指针，指向双链表的头部
    private transient Entry<K,V> header;
    //accessOrder为true: 表示按照访问的顺序来，也就是谁最先访问，就排在第一位 
    //accessOrder为false表示按照存放顺序来，就是你put元素的时候的顺序。
    private final boolean accessOrder;

此外，因为要实现双向链表的特性，所以LinkedHashMap的Entry类也必须增加属性，源码如下：

private static class Entry<K,V> extends HashMap.Entry<K,V> { 
        //双链表的前驱和后继
        Entry<K,V> before, after;
    
        //构造函数
        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }
    
        /** * 从双向链表中删除该结点 */
        private void remove() {
            before.after = after;
            after.before = before;
        }
    
        /** * Inserts this entry before the specified existing entry in the list. */
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }
    
        /** * This method is invoked by the superclass whenever the value * of a pre-existing entry is read by Map.get or modified by Map.set. * If the enclosing Map is access-ordered, it moves the entry * to the end of the list; otherwise, it does nothing. */
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }
    
        void recordRemoval(HashMap<K,V> m) {
            remove();
        }
    }

列一下Entry里面有的一些属性吧：  
1. K key  
2. V value  
3. Entry next;  
4. int hash  
5. Entry before//前驱  
6. Entry after//后继  
其中前面四个是从HashMap.Entry中继承过来的；后面两个是LinkedHashMap独有的。不要搞错了next和before、After：next是用于维护HashMap指定table\[i\]位置上连接的Entry的顺序的，before、After是用于维护Entry插入的先后顺序的。  
还是用图表示一下，列一下属性而已：  
![LinkedHashMap的Entry的数据结构][LinkedHashMap_Entry]

## LinkedHashMap的构造函数 ##

该类最后都会调用`LinkedHashMap(int initialCapacity, float loadFactor)` 该方法来实现构造Map。可知里面主要是调用了父类HashMap的构造函数，只是多加了一个`accessOrder = false;` 设置Map的迭代顺序是按照插入的顺序。

public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

## 重要的方法： ##

在LinkedHashMap中由于多态的特性重写了很多方法，下面主要分析以下方法：

void addEntry(int hash, K key, V value, int bucketIndex)
    
    void createEntry(int hash, K key, V value, int bucketIndex) 
    
    public V get(Object key)
    
    void init()
    
    void transfer(HashMap.Entry[] newTable, boolean rehash)

### init()方法 ###

该方法被HashMap构造器调用，在hashMap中该方法是空函数体，由于在LinkedHashMap中被override重写了，所以初始化LInkedHashMap时调用的是LinkedHashMap中的init()方法。这就是典型的多态的应用。具体源码如下：

void init() {
        header = new Entry<>(-1, null, null, null);
        header.before = header.after = header;
    }

里面也就做了一件事，初始化维护LinkedHashMap有序性的双向链表，即new了一个头结点，并让header指向这个头结点，这里这个头结点的key和value都是null，其next也是null。

### addEntry(int hash, K key, V value, int bucketIndex)方法 ###

我们发现在LinkedHashMap中并没有重写put()方法，说明LinkedHashMap的put()操作调用的HashMap中的put()方法，但是我们却发现，在HashMap中的put()方法中调用的addEntry(hash, key, value, i);方法在LinkedHashMap中被重写了，我们看看重写之后的源码：

void addEntry(int hash, K key, V value, int bucketIndex) {
        //先调用HashMap中的addEntry()函数
        super.addEntry(hash, key, value, bucketIndex);
    
        // Remove eldest entry if instructed
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }

调用HashMap中的addEntry()函数中又在LinkedHashMap中重写了createEntry(int hash, K key, V value, int bucketIndex) ，在LinkedHashMap中如下：

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);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
    }

函数中前三行和HashMap中没什么区别，区别在于多执行了一个  
`e.addBefore(header);` 这个函数，这个函数主要在双向链表中是在header结点前面插入e结点，其实也就是在双向链表的尾部插入了新节点e。

/** * 在链表中指定结点existingEntry前面插入该实体this。 */
    private void addBefore(Entry<K,V> existingEntry) {
        after  = existingEntry;
        before = existingEntry.before;
        before.after = this;
        after.before = this;
    }

### 2.get(Object key) ###

get()方法在LinkedHashMap中被重写了。

public V get(Object key) {
        //1. 根据key获取到实体
        Entry<K,V> e = (Entry<K,V>)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }

其实该方法和hashMap中的几乎一模一样，唯一的区别在于增加了这么一句：  
`e.recordAccess(this);`

void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        //将结点移动到双向链表的末尾
        if (lm.accessOrder) {
            lm.modCount++;
            remove();
            addBefore(lm.header);
        }
    }

在LinkedHashMap中，由于需要有顺序需要维护，因此，当accessOrder = true 时，则需要调用recordAccess(this)方法将此节点放到双向链表的末尾。而如果accessOrder = false.则完全与HashMap类中的get方法一模一样。

## 小结 ##

LinkedHashMap 和hashMap 功能基本一样，都是维护的键值对集合，连遍历 以及方法都类似，唯一的区别在于HashMap 里面的元素是根据hash值来决定存放位置的，是无序的，而LinkedHashMap 维护的是一个按顺序存放的双向链表，是有序的。

因此，记住，他们的区别在于：LinkedHashMap是“数组和双向链表”的结合体，而HashMap是“数组和单向链表”的结合体就够了。

# 测试 #

@Test
    public void testMap(){
        //无序
        Map<String, String> map = new HashMap<>();
        map.put("1","1");
        map.put("2","2");
        map.put("3","3");
        map.put("4","4");
        map.put("5","5");
    
        Set<Map.Entry<String,String>> set = map.entrySet();
        Iterator<Map.Entry<String,String>> it = set.iterator();
    
        while (it.hasNext()){
            System.out.println(it.next());
        }
    
    }
    
    @Test
    public void testMapLinked(){
        //有序
        Map<String, String> map = new LinkedHashMap<String,String>();
        map.put("1","1");
        map.put("2","2");
        map.put("3","3");
        map.put("4","4");
        map.put("5","5");
    
        Set<Map.Entry<String,String>> set = map.entrySet();
        Iterator<Map.Entry<String,String>> it = set.iterator();
    
        while (it.hasNext()){
            System.out.println(it.next());
        }
    
    }

结果：  
HashMap:  
![HashMap][]

LinkedHashMap  
![LinkedHashMap][LinkedHashMap 1]

[LinkedHashMap]: /images/20220713/b22fb720548b4f9c9a272b03c1b5adc2.png
[LinkedHashMap_Entry]: /images/20220713/2936cad0a0ec444b923358d31519590d.png
[HashMap]: /images/20220713/3576d6ea4c9e477f9c7a76d73e0094be.png
[LinkedHashMap 1]: /images/20220713/b76cf302c9be4591af7f55346a2948ed.png