>> 欢迎您客人: 登录 | 注册 | 在线 | 搜索 | 风格 | 帮助 | 统计 | 文章

返回首页

>>分享数据结构和算法相关的知识和技术

书籍支持

卫琴直播

品书摘要

在线测试

资源下载

联系我们

Java技术网站 → 『 Java开发技术』 → 『数据结构和算法专题』 → LinkedList，LinkedHashMap，LruCache源码解析

您是本文章第 19521 个阅读者

* 贴子主题: LinkedList，LinkedHashMap，LruCache源码解析

点赞(0) 收藏

作者:flybird 发表时间：2020-03-08 23:58:02

消息

查看

搜索

好友

邮件

复制

引用

LinkedList，LinkedHashMap，LruCache源码解析

最近正好在复习数据结构的知识，顺带看了下jdk 1.8中的LinkedList和LinkedHashMap以及android中常用的LruCache的源码（内部采用LinkedHashMap实现），以加强自己的理解，下面就分享一下我阅读源码的一些简单的心得。

一、简单高效的双链表LinkedList

     为什么使用双链表而不使用单链表，原因应该是，作为一种需要频繁在表头或表尾进行插入或删除操作的数据结构，选用双链表的效率会比单链表要高。试想一下，如果要删除单链表的表尾节点，除了需要将最后一个节点置空，还需要将该节点的上一个节点的next域置为null，因为此时无法直接通过最后一个节点得到倒数第二个节点的位置，所以只能重新从表头开始遍历，时间复杂度为O（n），而如果是双链表的话，可以直接通过最后一个节点的prev域即前驱节点得到它上一个节点，然后再将其next域置空，时间复杂度为O（1）。所以，双链表的优势就是，增加或删除节点的速度较快，尤其是在表尾节点。

         源码

先来看下节点类的定义

      private  static  class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
             this.item = element;
             this.next = next;
             this.prev = prev;
        }
    }

很简单，Node类是一个静态内部类，包含了数据部分和两个引用，分别指向前驱节点和后继节点，在节点类构造的时候分别指定它的前驱节点，数据域和后继节点。这样的构造函数，在后面进行插入或删除操作的时候给我们省去了很多麻烦。

在表头插入

  /**
     * Links e as first element.
     */
     private  void  linkFirst(E e) {
         final Node<E> f = first;
         final Node<E> newNode =  new Node<>( null, e, f);
        first = newNode;
         if (f ==  null)
            last = newNode;
         else
            f.prev = newNode;
        size++;
        modCount++;
    }

我们来分析一下，也不是很复杂，first是LinkedList的成员变量，即链表的头指针，该方法首先先保存原来的头结点，赋值给一个新的Node类f，然后创建新的节点，数据为e，前驱节点为null（因为要做新的第一个嘛），后继节点是f，接着将头指针指向新创建的节点。这样就成功地将新节点插入到了原头结点的前面，但由于是双链表，插入删除时需要调整两部分的指针，我们还要将原来头结点（f）的prev域设为新的头结点，在这之前，先判断一下原来的头结点是不是为null，如果为null的话，说明原来的双链表是空表，现在插入的是第一个节点，所以last尾指针也设为newNode。最后增加链表的size。

在表尾插入

  /**
     * Links e as last element.
     */
     void linkLast(E e) {
         final Node<E> l = last;
         final Node<E> newNode =  new Node<>(l, e,  null);
        last = newNode;
         if (l ==  null)
            first = newNode;
         else
            l.next = newNode;
        size++;
        modCount++;
    }

与在表头插入很类似，先保存原先尾节点的值为l，然后创建新的尾节点插入到l后面，然后调整原先尾节点l的next域，指向新的尾节点。在这之前同样先判断一下是不是空表，是空表的话，插入一个节点后first头结点也指向newNode。

在一个节点之前插入

  /**
     * Inserts element e before non-null Node succ.
     */
     void linkBefore(E e, Node<E> succ) {
         // assert succ != null;
         final Node<E> pred = succ.prev;
         final Node<E> newNode =  new Node<>(pred, e, succ);
        succ.prev = newNode;
         if (pred ==  null)
            first = newNode;
         else
            pred.next = newNode;
        size++;
        modCount++;
    }

该方法将一个新节点插入到succ节点前面。逻辑也很清晰，首先先获取到succ的前驱节点pred，然后新创建一个节点插入到pred和succ两者之间，然后分别修改succ的prev域和pred的next域，都指向新的节点。同样的，在修改pred的next域之前，判断pred是否为空，如果为空，说明原来succ是头结点，所以要把头指针指向新创建的节点newNode。

在表头删除

   /**
     * Unlinks non-null first node f.
     */
     private E  unlinkFirst(Node<E> f) {
         // assert f == first && f != null;
         final E element = f.item;
         final Node<E> next = f.next;
        f.item =  null;
        f.next =  null;  // help GC
        first = next;
         if (next ==  null)
            last =  null;
         else
            next.prev =  null;
        size--;
        modCount++;
         return element;
    }

在删除表头节点f的时候，先保存其下一个节点next，接着将f的数据域和指针域强制置为null，这样可以帮助垃圾收集器GC很快的回收这两个引用。跟着将新的头指针指向next，然后判断next是否为空，如果next为空，说明原来只有一个节点，删除后表变空了，所以将last也设为null，否则的话将next（此时的新头结点）的prev前驱指针设为null，最后修改表的长度大小，并将删除的头结点的值返回。

在表尾删除

  /**
     * Unlinks non-null last node l.
     */
     private E  unlinkLast(Node<E> l) {
         // assert l == last && l != null;
         final E element = l.item;
         final Node<E> prev = l.prev;
        l.item =  null;
        l.prev =  null;  // help GC
        last = prev;
         if (prev ==  null)
            first =  null;
         else
            prev.next =  null;
        size--;
        modCount++;
         return element;
    }

逻辑与上面在表头删除正好相反，就不在赘述了。

在表中删除

  /**
     * Unlinks non-null node x.
     */
    E unlink(Node<E> x) {
         // assert x != null;
         final E element = x.item;
         final Node<E> next = x.next;
         final Node<E> prev = x.prev;

         if (prev ==  null) {
            first = next;
        }  else {
            prev.next = next;
            x.prev =  null;
        }

         if (next ==  null) {
            last = prev;
        }  else {
            next.prev = prev;
            x.next =  null;
        }

        x.item =  null;
        size--;
        modCount++;
         return element;
    }

从双链表中删除指定结点x，首先获得x的前驱和后继节点，如果前驱节点为null，说明x为头结点，删除后直接将头指针指向x的后继节点，如果不是头结点则将x的前驱节点的后继指向x的后继，并将x的前驱置为空，将x从链中断开，此处画个图就很好理解；接着同样判断x的后继next是不是空，如果是空说明x是尾节点，要删除的话则直接将尾指针指向x的前驱，否则修改x后继节点的前驱指针，指向x的前驱，再把x的next置为null，将x从链中断开。

我们常用的一些add和remove操作，调用的都是上面的函数。

  public  boolean  add(E e) {
        linkLast(e);
         return  true;
    }

  public  void  addFirst(E e) {
        linkFirst(e);
    }

   public  void  addLast(E e) {
        linkLast(e);
    }

  public E  removeFirst() {
         final Node<E> f = first;
         if (f ==  null)
             throw  new NoSuchElementException();
         return unlinkFirst(f);
    }

  public E  removeLast() {
         final Node<E> l = last;
         if (l ==  null)
             throw  new NoSuchElementException();
         return unlinkLast(l);
    }

  public  void  push(E e) {
        addFirst(e);
    }

   public E  pop() {
         return removeFirst();
    }

如果你理解了双链表的基本插入删除操作，那么LinkedList的源码你也可以差不多基本理解了，剩下的一些细节我就不再说了，下面看LinkedHashMap。

二、LinkedHashMap

LinkedHashMap是HashMap的子类，通俗的讲就是加了双链表结构的HashMap。HashMap大家都很清楚，本质就是Entry数组加链表（或者红黑树）的形式，Entry这个数据结构包括hash值，key-value键值对，和next索引（通过链地址法用来解决哈希冲突）。而我们看看LinkedHashMap里的Entry

LinkedHashMap的Entry

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

可以看到LinkedHashMap在原来HashMap的Entry的基础上又增加了before和after两个指针（java中只有引用，这里说指针是为了方便理解），分别指向前驱和后继节点，所以说，它是一个完完全全的双链表+HashMap。

双链表表头与表尾的定义

  /**
     * The head (eldest) of the doubly linked list.
     */
     transient LinkedHashMap.Entry<K,V> head;

     /**
     * The tail (youngest) of the doubly linked list.
     */
     transient LinkedHashMap.Entry<K,V> tail;

还有一个很重要的成员变量accessOrder

final boolean accessOrder;

如果accessOrder为true表明LinkedHashMap按照访问的顺序来迭代，如果为false表明LinkedHashMap按照插入的顺序来迭代。默认是按照插入顺序来遍历：

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

在创建新节点的时候，是直接将Entry加入到双链表的尾部：

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

下面我们就来看一下这个linkNodeLast（）方法

  // link at the end of list
     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;
        }
    }

     linkNodeLast方法将一个Entry节点加入到双链表的尾部。首先保存原双链表的表尾节点tail为last，然后将tail指向新插入的节点p，此时判断原来的表尾节点last是否为null，如果为null，说明原来双链表为空表，插入后只有一个节点，所以将head头指针也指向p，否则的话，将p的前驱指向原来的表尾节点last，将原来表尾节点last的后继指向新的表尾节点p。

         细想一下，和LinkedList那段是不是很像？没错，因为归根结底还是双链表的插入操作。

         下面看一下LinkedHashMap的get()方法

  public V  get(Object key) {
        Node<K,V> e;
         if ((e = getNode(hash(key), key)) ==  null)
             return  null;
         if (accessOrder)
            afterNodeAccess(e);
         return e. value;
    }

可以看到，在访问完一个节点后，如果accessOrder为true的话（即设置按照访问顺序来迭代），会调用afterNodeAccess()函数将刚访问过的节点放置到双链表的尾部，即放到最新的位置，代表这个节点刚被访问过。我们再去afterNodeAccess()函数看看究竟

  void afterNodeAccess(Node<K,V> e) {  // move node to last
        LinkedHashMap.Entry<K,V> last;
         if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after =  null;
             if (b ==  null)        //如果p是表头
                head = a;         //将e从表中断开后，表头指向e的后继
             else
                b.after = a;      //否则将e从表中断开
             if (a !=  null)
                a.before = b;
             else                  //p是表尾
                last = b;         //将e从表中断开后，表尾指向e的前驱
             if (last ==  null)     //如果原链表是空表
                head = p;         //表头指向p
             else {                //否则插向原链表的表尾
                p.before = last;
                last.after = p;
            }
            tail = p;             //尾节点指向新插入的节点
            ++modCount;
        }
    }

该函数将节点e从原双链表中摘下，并插入到最后的位置。这里还是先用一个last来保存原来的tail表尾节点，如果accessOrder为true，并且此时节点p（由e转换而来）并不在表尾，则执行后面的操作，后面的操作可以分为两部分，第一部分是将节点p从原来双链表的位置中断开，第二部分是将节点p插入到表尾。和之前在LinkedList中的操作很类似，将节点p从原链表中删除时，判断了p是否在表头或是在表尾（与LinkedList的unlinkFirst和unlinkLast函数相同）；将p插入到链表尾部时，加入了表是否为空的判断（与LinkedList的linkLast函数相同）。

综上，我们可以看到，将LinkedList中双链表的增加和删除操作与HashMap相结合，就是LinkedHashMap。

三、LruCache

理解了LinkedHashMap，就不难理解LruCache的实现原理了。这个Android中最常用的缓存类，内部就维护了一个LinkedHashMap的引用

private final LinkedHashMap<K, V> map;

在 LruCache初始化时，指定了hasmap的扩容因子，并设置accessOrder为true，按访问顺序迭代，来达到LRU（最近最久未使用）算法的效果：最近被访问的，或者最新插入的，总是在表尾，而不怎么被经常访问的，就会逐渐向表头移动，此时就可以从表头将这些不常用的缓存淘汰。

我们来看一下从缓存中取数据的get方法

  public  final V  get(K key) {
     if (key ==  null) {
         throw  new NullPointerException( "key == null");
    }

    V mapValue;
     synchronized ( this) {
　　　　  // 如果根据相应的key能查找到value，就增加一次缓存命中的次数hitCount，并且返回结果
        mapValue = map.get(key);
         if (mapValue !=  null) {
            hitCount++;
             return mapValue;
        }
　　　　　 // 否则增加一次未命中次数missCount
        missCount++;
    }

     /*
     * Attempt to create a value. This may take a long time, and the map
     * may be different when create() returns. If a conflicting value was
     * added to the map while create() was working, we leave that value in
     * the map and release the created value.
     */
    V createdValue = create(key);
     if (createdValue ==  null) {
         return  null;
    }

     synchronized ( this) {
        createCount++;
　　　　  // 如果我们重写了create(key)方法而且返回值不为空，那么将上述的key与这个返回值写入到map当中
        mapValue = map.put(key, createdValue);

         if (mapValue !=  null) {
             // There was a conflict so undo that last put
　　　　　　　 // 方法放入最后put的key，value值
            map.put(key, mapValue);
        }  else {
            size += safeSizeOf(key, createdValue);
        }
    }

     if (mapValue !=  null) {
　　　　　 // 这个方法也可以重写
        entryRemoved( false, key, createdValue, mapValue);
         return mapValue;
    }  else {
        trimToSize(maxSize);
         return createdValue;
    }
}

下面再看一下LruCache更新缓存的策略，主要在trimToSize()这个函数中

   /**
     * Remove the eldest entries until the total of remaining entries is at or
     * below the requested size.
     *
     *  @param maxSize the maximum size of the cache before returning. May be -1
     *            to evict even 0-sized elements.
     */
     public  void  trimToSize( int maxSize) {
         while ( true) {
            K key;
            V value;
             synchronized ( this) {
                 if (size <  0 || (map.isEmpty() && size !=  0)) {
                     throw  new IllegalStateException(getClass().getName()
                            +  ".sizeOf() is reporting inconsistent results!");
                }

                 if (size <= maxSize || map.isEmpty()) {
                     break;
                }
                 //按照访问顺序来迭代，最新访问过的都在表尾，表头的是最近长时间内都没有使用过的缓存
                Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
                key = toEvict.getKey();
                value = toEvict.getValue();
                 //将缓存移除
                map.remove(key);
                 //修改缓存链表的size
                size -= safeSizeOf(key, value);
                 //淘汰掉一个缓存
                evictionCount++;
            }

            entryRemoved( true, key, value,  null);
        }
    }

     从注释中就可以看到，这个函数将最老的也就是最久没有访问过的entry删除，以将整体entry的容量降低到指定大小（淘汰了最近不常用的缓存）。可以看到，它通过map.entrySet().iterator()获得LinkedHashMap的迭代器，从保存了缓存数据的双链表的第一个节点开始（即最久没有使用过的缓存，因为最近刚使用过的缓存都移到了表尾），逐个调用remove函数，将其从表中删除，以降低整体缓存的大小。

         看到了这里，是不是对LinkedList，LinkedHashMap，LruCache的基本原理有了一个清楚的认识呢？我们看到，万变不离其宗，其重点就是围绕双链表的增删改操作，数据结构的基础确实很重要。


----------------------------
原文链接:https://blog.csdn.net/SakuraMashiro/article/details/80754682

程序猿的技术大观园：www.javathinker.net

[这个贴子最后由 flybird 在 2020-03-09 22:37:03 重新编辑]

网站系统异常

返回首页 → 网站系统异常

系统异常信息

Request URL: http://www.javathinker.net/WEB-INF/lybbs/jsp/topic.jsp?postID=2695

java.lang.NullPointerException

如果你不知道错误发生的原因，请把上面完整的信息提交给本站管理人员。