LinkedHashMap

2018-11-14 今天开始看LinkedHashMap的源码.
以前看源码写博客都是大段大段的贴代码,但是转回去看的时候发现我自己都看不下去了,LinkedHashMap并不难理解,就当是一次测试吧.
LinkedHashMap大部分的结构和算法和HashMap一致,所以在阅读LinkedHashMap源码之前可能要先了解下HashMap的原理,
LinkedList不仅实现了List接口还实现了Deque，因此除链表之外还可以作为队列使用。(自己画结构图被丑哭了).
LinkedList和ArrayList不同，底层并不是数组，还是一个由Node内部类实现的双向链表，Node结构下面说。

成员变量

// 记录链表的大小
transient int size = 0;
// 记录链表的头结点
transient Node<E> first;
// 记录链表的尾节点
transient Node<E> last;
// 参数全部被`transient`修饰，所以序列化是都不会被记录。

Node 内部类

Node类非常简单，但是是底层链表的基础结构。

除了存储数据之外，Node还需要记录前驱和后继节点，串联成一个双向链表。

// Node就是`LinkedList`底层链表的节点。
// item记录具体内容,next表示后继节点，prev为前驱节点
  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;
      }
  }

构造函数

LinkedList的构造函数也非常简单，此处不放代码。

一个默认的无参构造，一个就是以集合为参数的构造函数，后者调用下面的addAll()将集合中的数据转移。

链表操作方法

linkBefore(E e,Node succ)

该方法的作用是将e作为节点插入到succ节点之前。
类似方法还有linkFirst和linkLast

void linkBefore(E e, Node<E> succ) {
       // assert succ != null;     assert语法已经out了
        // 获取前驱节点
       final Node<E> pred = succ.prev;
       // 创建新节点,pred为前驱，e为元素，succ为后继
       final Node<E> newNode = new Node<>(pred, e, succ);
        // 插入链表节点的操作，改变后继节点的前驱节点属性，和前驱节点的后继节点属性
       succ.prev = newNode;
       if (pred == null)
           first = newNode;
       else
           pred.next = newNode;
        // 记录元素数量 
       size++;
        // 记录修改，和ArrayList里应该一致
       modCount++;
   }

E unlink(Node x)

unlink的方法都是用来删除链表中的元素
类似的方法还有unlinkFrist和unlinkLast，但我不清楚为什么对象中已经记录了first和last两个节点，还需要在unlinkFirst的时候传入一个节点作为参数。

E unlink(Node<E> x) {
      // 获取x节点的所有属性
      final E element = x.item;
      final Node<E> next = x.next;
      final Node<E> prev = x.prev;
      // 前驱为空，表示x即为first节点
      if (prev == null) {
          first = next;
      } else {
          prev.next = next;
          x.prev = null;
      }
      // 后继为空 表示x即为last节点
      if (next == null) {
          last = prev;
      } else {
          next.prev = prev;
          x.next = null;
      }
      // 清空存储数据
      x.item = null;
         // 修改元素个数和修改统计
      size--;
      modCount++;
      return element;
  }

LinkedList相关问题

LinkedList vs ArrayList

(Array和ArrayList的结构是一致的.勉强能看)

从结构上来说LinkedList是由双向链表实现,而ArrayList由动态数组实现,这是最根本的不同.
从元素存取来说;
1. ArrayList继承RandomAccess接口支持随机访问,获取元素的时间复杂度为O(1),LinkedList不支持随机访问,获取元素只能逐个遍历,时间复杂度为O(n).
2. ArrayList的插入操作还有数组边界的检查,扩容以及元素迁移等问题,而LinkedList仅需要改变前驱后继两个节点属性就足够.

LinkedHashMap 源码分析

LinkedHashMap

成员变量

Node 内部类

构造函数

链表操作方法

LinkedList相关问题

LinkedList vs ArrayList

results matching ""

No results matching ""