Java之LinkedHashMap

本是古典何须时尚 2024-04-19 13:13 78阅读 0赞

### 文章目录 ###

*   *   *  一、底层数据结构
         *  二、部分方法源码
         *   *  1.构造方法
             *  2.put方法
             *   *  2.1 recordAccess——集合元素位置变化
                 *  2.2 addEntry & createEntry
             *  3.Iterator
             *  4. containsValue(Object value)
         *  三、遍历
         *  四、总结

### 一、底层数据结构 ###

根据类名定义`public class LinkedHashMap<K,V> extends HashMap<K,V>`, **LinkedHashMap是继承自HashMap,**  
它实现了**元素插入顺序与访问顺序一致**

### 二、部分方法源码 ###

#### 1.构造方法 ####

public LinkedHashMap() {
            super();
            accessOrder = false; // 默认情况下为false
    }

可以看到构造方法调用的是父类HashMap的方法, 但多了一个参数`accessOrder`.

/**
         * 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;

该属性与集合存储的**元素顺序**有关.  
**false**：访问顺序与插入顺序一致  
**true**：集合元素可能会因为插入(put)、访问(get)修改在集合中的位置

#### 2.put方法 ####

`LinkedHashMap`调用父类的put方法, 并且**重写了`recordAcces`、`addEntry`、`createEntry`方法,** 这些方法在put方法中会被调用.

##### 2.1 recordAccess——集合元素位置变化 #####

何时会调用?

(1) **accessOrder == true**  
(2) **插入元素时存在相同的key** or **调用get方法**

2.1.1 **key已经存在**

//  HashMap put方法部分源码
    ...
    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;
                    e.recordAccess(this); <—— 在这里
                    return oldValue;
                }
            }
    ...

recordAccess——

// recordAccess源码
    
    void recordAccess(HashMap<K,V> m) {
                LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
                if (lm.accessOrder) {
                    lm.modCount++;
                    remove(); // 删除当前节点(修改引用)
                    addBefore(lm.header); // 添加元素到末尾
                }
            }

**例子**——

默认状态下, `accessOrder = false`

// 栗子1
    Map<String, String> map = new LinkedHashMap<>(16, 0.75f); // 不设置accessOrder
    map.put("ah", "f");
    map.put("1", "a");
    map.put("ah", "g");
    
    遍历打印:
    ah=g
    1=a

当`accessOrder`为**true**时, 会删除节点, 并修改元素的位置到**当前列表**的**末尾**。

// 栗子2
    Map<String, String> map = new LinkedHashMap<>(16, 0.75f, true); // 显式设置accessOrder
    map.put("ah", "f");
    map.put("1", "a");
    map.put("ah", "g");
    
    遍历打印:
    1=a
    ah=g

2.1.2 **当调用get方法**

public V get(Object key) {
            Entry<K,V> e = (Entry<K,V>)getEntry(key); // 调用父类方法
            if (e == null)
                return null;
            e.recordAccess(this); // 修改元素顺序
            return e.value;
        }

// 栗子1
     Map<String, String> map = new LinkedHashMap<>(16, 0.75f, true);
     
    map.put("ah", "f");
    map.put("1", "a");
    map.put("2", "b");
    map.get("ah");
    
    遍历打印:
    1=a
    2=b
    ah=f

##### 2.2 addEntry & createEntry #####

**addEntry ——**

void addEntry(int hash, K key, V value, int bucketIndex) {
            super.addEntry(hash, key, value, bucketIndex); // 调用父类addEntry
    
            // Remove eldest entry if instructed
            Entry<K,V> eldest = header.after;
            if (removeEldestEntry(eldest)) { // 只会返回false
                removeEntryForKey(eldest.key);
            }
        }

**createEntry**——

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并没有什么差别.

// 典型的双向链表插入代码
     private void addBefore(Entry<K,V> existingEntry) {
                after  = existingEntry;
                before = existingEntry.before;
                before.after = this;
                after.before = this;
            }

#### 3.Iterator ####

直接看看Iterator是如何取数据的。

public Map.Entry<K,V> next() { return nextEntry(); }

**nextEntry()**——

Entry<K,V> nextEntry() {
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                if (nextEntry == header)
                    throw new NoSuchElementException();
    
                Entry<K,V> e = lastReturned = nextEntry;<——关键属性
                nextEntry = e.after;
                return e;
            }

nextEntry属性在何时被初始化？

在调用`Iterator()`时已经初始化

private abstract class LinkedHashIterator<T> implements Iterator<T> {
            Entry<K,V> nextEntry    = header.after; <——得到第一个元素
            Entry<K,V> lastReturned = null;
    ...

header在何时被初始化？

// 构造方法调用
    void init() {
            header = new Entry<>(-1, null, null, null);
            header.before = header.after = header;
        }

**为什么header.after会指向第一个元素?**

**First**, 构造方法调用**init方法**后链表的结构:  
![在这里插入图片描述][20190918203442180.PNG]

**Second**, 添加第一个元素(看上面提到的插入链表的代码)  
![在这里插入图片描述][201909182047111.PNG]  
**Next**, 添加第二个元素  
![在这里插入图片描述][20190918204812597.PNG]

#### 4. containsValue(Object value) ####

public boolean containsValue(Object value) {
            // Overridden to take advantage of faster iterator
            if (value==null) {
                for (Entry e = header.after; e != header; e = e.after)
                    if (e.value==null)
                        return true;
            } else {
                for (Entry e = header.after; e != header; e = e.after)
                    if (value.equals(e.value))
                        return true;
            }
            return false;
        }

对照上图看.

### 三、遍历 ###

通常情况下有2个方案:  
1.根据`keySet()`方法获取key集合, 遍历key, 根据`get(Object key)`方法获取key-value值  
2.根据`entrySet()`获取集合, 直接遍历

**But**, 当`accessOrder=true`时, 调用`get()`方法会引发集合元素顺序的修改, 引发异常`ConcurrentModificationException`

### 四、总结 ###

1.LinkedHashMap通过**链表**来保证插入顺序与访问顺序一致  
2.当`accessOrder=true`时, 可能会造成元素顺序的修改, 只影响当前元素在集合中的顺序.

[20190918203442180.PNG]: https://img-blog.csdnimg.cn/20190918203442180.PNG
[201909182047111.PNG]: https://img-blog.csdnimg.cn/201909182047111.PNG
[20190918204812597.PNG]: https://img-blog.csdnimg.cn/20190918204812597.PNG