java源码-LinkedHashMap

  1. 云栖社区>
  2. 博客>
  3. 正文

java源码-LinkedHashMap

晴天哥 2018-07-29 19:10:00 浏览356
展开阅读全文

开篇

 LinkedHashMap是HashMap的变种,有一些额外的特性其中最重要的就是维护数据插入的有序性,这篇文章就是为了讲清楚LinkedHashMap的实现细节。


LinkedHashMap类图

img_ae34a2e49bfbb0f4e908ec64e0d065dd.png
LinkedHashMap类图


LinkedHashMap和HashMap的差别

  • LinkedHashMap可以认为是HashMap+LinkedList,即它既使用HashMap操作数据结构,又使用LinkedList维护插入元素的先后顺序。
  • LinkedHashMap除了维持Map的有序性质外,其他和HashMap是一模一样的,

LinkedHashMap实现细节

 从LinkedHashMap的类依赖图可以看出来,LinkedHashMap其实是继承自HashMap类,所以LinkedHashMap的所有接口基本上都是继承自己HashMap类,当然也存在一个非常核心的差别。

  • LinkedHashMap用于存储key/value的结果是继承自己HashMap的,但是LinkedHashMap本身维护着一个有序列表。
  • head是LinkedHashMap的列表头,tail是LinkedHashMap的列表尾,通过这两个变量保证了维护LinkedHashMap的插入顺序。
  • LinkedHashMap的Entry相比HashMap.Node对象增加了before和after两个变量,由于指向前后节点。
  • LinkedHashMap通过重写HashMap的newNode方法,创建Entry对象并在内部初始化了HashMap当中的Node节点。
  • 在创建Entry的newNode过程中通过linkNodeLast()方法按照put顺序维持LinkHashMap的有序性。
public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
    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有序列表的头
    transient LinkedHashMap.Entry<K,V> head;
    // 保存HashMap有序列表的尾
    transient LinkedHashMap.Entry<K,V> tail;

    final boolean accessOrder;
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

   
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }


LinkedHashMap实际存储结构图

img_1a278a7a62b26c6c9ebcb1d95eda81f7.png
image.png

说明:
上述按照Entry1->Entry6的顺序进行存储的,不过这个图有些问题,正常的情况是head就是Entry1的对象,tail是Entry6的对象。


参考文章

图解LinkedHashMap原理

网友评论

登录后评论
0/500
评论
晴天哥
+ 关注