JDK source 之 LinkedHashMap原理浅谈

注：本文参考JDK1.7.0_45源码。

LinkedHashMap是基于HashMap实现的数据结构，与HashMap主要的不同为每个Entry是使用双向链表实现的，并且提供了根据访问顺序进行排序的功能。

// 双向链表

private transient Entry<K,V> header;

// 如果为true，按照访问顺序排序；如果为false，按照插入顺序排序。默认为false，可以在构造函数中设置。

private final boolean accessOrder;

LinkedHashMap中的内部类Entry大概如下，可以看到都是基于链表（数据结构意义上的）节点的操作：

Entry<K,V> before, after;

private void remove() {

    before.after = after;

    after.before = before;

}

private void addBefore(Entry<K,V> existingEntry) {

    after  = existingEntry;

    before = existingEntry.before;

    before.after = this;

    after.before = this;

}

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();

}

当accessOrder为true的时候，当对map进行get和put操作都会将对应的kv移动到最map最前端。这种数据的移动影响到了数据的数据的遍历，比如foreach和containsValue会先查到最近最新被访问的元素。

还有一个点是，当put数据的时候内部有addEntry方法调用如下逻辑：

if (removeEldestEntry(eldest)) {

    removeEntryForKey(eldest.key);

}

// 调用方法如下：

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {

    return false;

}

可以看到，返回值永远为false，目的是为了扩展。继承LinkedHashMap重写removeEldestEntry方法，即可以非常方便的实现一个LRU，赞。

巴特西

JDK source 之 LinkedHashMap原理浅谈

最新文章

热门文章