文档章节

0006--jcf(jdk1.7)-LinkedHashMap源码

c
 cengy
发布于 2016/04/03 20:49
字数 1424
阅读 20
收藏 0

1.    LinkedHashMap的定义

从API的介绍中了解到,LinkedHashMap与HashMap的不同在于LinkedHashMap维护了每个Entry的一个双链表(所以LinkedHashMap是有序的)。这个双链表可以按照插入元素的顺序进行迭代。LinkedHashMap有个构造方法LinkedHashMap(int, float, boolean)提供了可以按照LRU(最近最少使用)算法进行迭代元素。类定义如下:

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

LinkedHashMap继承了HashMap。

2.    LinkedHashMap的实现

LinkedHashMap的属性:

// 双链表的头节点
private transient Entry<K,V> header;
// true: access-order(采用LRU), false: insertion-order
private final boolean accessOrder;

LinkedHashMap的构造函数

LinkedHashMap有5个构造函数

public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
public LinkedHashMap() {
    super();
    accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super(m);
    accessOrder = false;
}

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

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

// 这个Entry继承了HashMap的Entry
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);
    }
    // 将新的Entry插入到existingEntry之前
    private void addBefore(Entry<K,V> existingEntry) {
        after  = existingEntry;
        before = existingEntry.before;
        before.after = this;
        after.before = this;
    }
}       

// 在HashMap中,构造函数调用了createEntry;在LinkedHashMap需要重写此方法构造双链表(同时LinkedHashMap在put方法的时候也调用了此方法,而HashMap中是没有的)
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;// 新增元素始终是在table[i]处,即亦是i处链表头
    e.addBefore(header);
    size++;
}
// HashMap在构造函数中调用了createEntry方法,而LinkedHashMap的结构与HashMap有区别,所以需要重写createEntry来构造双链表结构

前4个构造函数中accessOrder都是false。 最后一个构造函数,让我们自己显示指定accessOrder值,如果我们传入true,则可以构建基于LRU算法进行迭代的Map。

注意init()方法,在HashMap中,所有的构造方法都调用了init(),现在LinkedHashMap对其进行了重构,在构造的时候对链表进行了初始化,

3.    LinkedHashMap的方法

LinkedHashMap继承HashMap,它只需要重构某些方法来实现自己的结构就可以。

addEntry()
containsValue(Object value) : boolean
get(Object key): V
  • addEntry()

在构造数据的时候是put方法,里面调用addEntry(),因为现在LinkedHashMap与HashMap的链结构不一样,因此LinkedHashMap只需要在构造数据的时候重写这个方法就可以。

void addEntry(int hash, K key, V value, int bucketIndex) {
    createEntry(hash, key, value, bucketIndex);

    // Remove eldest entry if instructed, else grow capacity if appropriate
    // 在createEntry中新元素始终是在header前面,所以header.after取出来的就是eldset的那个元素
    Entry<K,V> eldest = header.after;
    
    // 如果有必要,移除LRU里面时间最久的的Entry,否则是否resize  
    if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);
    } else {
        if (size >= threshold)
            resize(2 * table.length);
    }
}

// 如果发生了resize,那么需要对元素进行重新hash,调用了transfer方法
void transfer(HashMap.Entry[] newTable) {
    int newCapacity = newTable.length;
    // 不用像HashMap先遍历table,再遍历Entry的链表。因为它是双链表,因此只需要遍历这个Entry双链表即可。
    for (Entry<K,V> e = header.after; e != header; e = e.after) {
        int index = indexFor(e.hash, newCapacity);
        e.next = newTable[index];
        newTable[index] = e;
    }
}
//Entry里面的方法
void recordRemoval(HashMap<K,V> m) {
    remove();
}
// 当使用LRU,则remveEntryForKey函数会调用recordRemoval()将当前eldest元素删除
private void remove() {
    before.after = after;
    after.before = before;
}
  • containsValue(Object value): boolean

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;
}
// 遍历整个链表然后依次比较值
  • get(Object k): V

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;
}
// 这个是LinkedHashMap重写的recordAccess方法,在HashMap里面是一个空实现。因为HashMap没有维护Entry的pre,next关系。
void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    if (lm.accessOrder) { // 如果使用LRU
        lm.modCount++;
        remove();        // 将当前的Entry移除
        addBefore(lm.header);// 在将当前元素插入到header之前。
    }
}

//LinkedHashMap内部类:Entry里面的remove()方法
private void remove() {
    before.after = after;
    after.before = before;
}

LinkedHashMap的迭代 LinkedHashIterator

private abstract class LinkedHashIterator<T> implements Iterator<T> {
    Entry<K,V> nextEntry    = header.after; // 从header的after开始
    Entry<K,V> lastReturned = null;

    /**
     * The modCount value that the iterator believes that the backing
     * List should have.  If this expectation is violated, the iterator
     * has detected concurrent modification.
     */
    int expectedModCount = modCount;

    public boolean hasNext() {
        return nextEntry != header;
    }

    public void remove() {
        if (lastReturned == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();

        LinkedHashMap.this.remove(lastReturned.key);
        lastReturned = null;
        expectedModCount = modCount;
    }

    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;
    }
}

4.    用LinkedHashMap实现LRU算法

LinkedHashMap怎么实现LRU算法的?

当调用get方法的时候,

e.recordAccess(this);
void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    if (lm.accessOrder) { // 如果使用LRU
        lm.modCount++;
        remove();        // 将当前的Entry移除
        addBefore(lm.header);// 在将当前元素插入到header之前。
    }
}

recordAccess方法根据值accessOrder=true的时候,调用remove将当前Entry的前后指向清除,然后再将其加入到header Entry之前。

当调用put方法的时候:

// 如果有必要,移除LRU里面时间最久的的Entry,否则是否resize  
    if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);
    } else {
        if (size >= threshold)
            resize(2 * table.length);
    }
    
    void recordRemoval(HashMap<K,V> m) {
    remove();
}

当加入新元素的时候,会调用Entry的addEntry方法,然后调用removeEldestEntry方法将过期(一个规则来指定过期)元素移除。

默认removeEledestEntry是返回false。所以如果我们要实现LRU,除了构造LinkedHashMap的时候需要将accessOrder传入true,还需要重写这个方法。

public class LRUCache<K, V>
        extends LinkedHashMap<K, V> {

    private int cacheSize;

    public LRUCache(int cacheSize) {
        super(16, 0.75f, true);
        this.cacheSize = cacheSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() >= cacheSize;
    }
}


© 著作权归作者所有

c
粉丝 1
博文 22
码字总数 16864
作品 0
成都
私信 提问
LinkedHashMap源码浅析jdk1.7

LinkedHahsMap的继承关系 LinkedHashMap直接继承了HahsMap,而linkedHashMap和HashMap在同一个包下,因此HashMap中所有的非private的属性都能拿过来直接用。 LinkedHashMap继承HashMap原来的...

kin1492
2018/07/24
0
0
Java集合 --- LinkedHashMap底层实现和原理(源码解析)

概述 文章的内容基于JDK1.7进行分析,之所以选用这个版本,是因为1.8的有些类做了改动,增加了阅读的难度,虽然是1.7,但是对于1.8做了重大改动的内容,文章也会进行说明。 LinkedHashMap,见...

起个名忒难
2017/09/24
0
0
LinkedHashMap.Entry的addBefore方法

LinkedHashMap在按访问有序时,get/put会将节点放在最后面,jdk1.9的一幕了然: 但是jdk1.7就看不懂了: e.addBefore(header)只是将要put的节点e添加到header(首节点)的前面而已,怎么就变...

飞来飞去1
2018/07/18
421
0
Java面试必问之---HashMap

   本文有些长,贴的源码较多,请各位看官自备花生瓜子啤酒饮料矿泉水小板凳,且听我慢慢道来。    Java面试都会问集合,集合必问HashMap,CurrentHashMap,后面的套路就肯定会问多线程...

Marksmanbat
2018/08/17
0
0
BAT面试必备——Java 集合类

本文首发于我的个人博客:尾尾部落 1. Iterator接口 Iterator接口,这是一个用于遍历集合中元素的接口,主要包含hashNext(),next(),remove()三种方法。它的一个子接口LinkedIterator在它的基...

繁著
2018/09/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

ubuntu或ubuntu kylin优麒麟中安装QQ、wechat微信、百度网盘

从中国国内的地址下载deepin wine,码云上的。这样网速比较快。然后,按照说明向下安装。 https://gitee.com/wszqkzqk/deepin-wine-for-ubuntu...

gugudu
11分钟前
0
0
基于redis分布式锁实现“秒杀”

最近在项目中遇到了类似“秒杀”的业务场景,在本篇博客中,我将用一个非常简单的demo,阐述实现所谓“秒杀”的基本思路。 业务场景 所谓秒杀,从业务角度看,是短时间内多个用户“争抢”资源...

别打我会飞
31分钟前
8
0
Zookeeper的实践指南

本章重点 1.数据存储2.基于Java API初探Zookeeper的使用3.深入分析Watcher机制的实现原理4.Curator客户端的使用,简单高效 数据存储 事务日志快照日志运行时日志 bin/zookeepe...

须臾之余
34分钟前
1
0
MySQL mybatis Point类型数据

MySQL中的point用于表示GIS中的地理坐标,在GIS中广泛使用 如何写入mysql,如下图: CREATE TABLE `test-point` ( `id` int(11) NOT NULL AUTO_INCREMENT COMMENT '序号', `point` ......

张欢19933
46分钟前
2
0
设计模式-适配器模式

适配器模式 适配器模式(Adapter Pattern)是作为两个不兼容的接口之间的桥梁。这种类型的设计模式属于结构型模式,它结合了两个独立接口的功能。 这种模式涉及到一个单一的类,该类负责加入...

HOT_POT
今天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部