集合

Collection 接口

List

LinkedList

LinkedList是一个双向链表，往集合中插入数据和删除数据效率非常高，只需要移动相关节点的next和previous指向的对象就能完成删除和新增的操作。但是双向链表的读取数据的效率非常低。get()方法的时间复杂度为n/2。

源码窥探

• 新增元素

//添加元素到集合中
public boolean add(E e) {
  linkLast(e);
  return true;
}
void linkLast(E e) {
  //获取当前双向链表的最后一个节点
  final Node<E> l = last;
  //把当前要加入到集合中的数据包装成node数据结构
  final Node<E> newNode = new Node<>(l, e, null);
  //设置链表中最后一个节点指向新创建的node节点
  last = newNode;
  //判断是否是第一次新增数据，如果是，则当前新增的节点也是首节点
  //否则，把新增前的最后一个节点的next节点设置为新节点
  if (l == null)
    first = newNode;
  else
    l.next = newNode;
  //集合元素个数+1
  size++;
  //修改计数+1，该属性是用来记录集合中元素的修改状态
  modCount++;
}

• 删除元素

//删除节点
public boolean remove(Object o) {
  if (o == null) {
    for (Node<E> x = first; x != null; x = x.next) {
      if (x.item == null) {
        unlink(x);
        return true;
      }
    }
  } else {
    for (Node<E> x = first; x != null; x = x.next) {
      if (o.equals(x.item)) {
        unlink(x);
        return true;
      }
    }
  }
  return false;
}

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;

  //处理前置节点
  //如果是prev是空，则是首节点，则把当前节点的下一个节点设置为首节点
  if (prev == null) {
    first = next;
  } else {
    //不为空，则将前一个节点的下一个几点设置为当前节点的next节点，（跳过当前节点）
    prev.next = next;
    x.prev = null;
  }

  //处理后置节点
  if (next == null) {
    last = prev;
  } else {
    next.prev = prev;
    x.next = null;
  }
    //将节点保存的数据置空
  x.item = null;
  //减少当前集合大小
  size--;
  //修改次数加1
  modCount++;
  return element;
}

• 获取元素

public E get(int index) {
  //判断index下标是否超出范围
  checkElementIndex(index);
  return node(index).item;
}

Node<E> node(int index) {
  // assert isElementIndex(index);
  //size >> 1 左移一位，相当于除以2，如果index小于链表元素个数的一办
  //从0开始遍历，如果大于size的一半，则从链表尾部开始遍历
  //这个方法的效率很低，不建议使用
  if (index < (size >> 1)) {
    Node<E> x = first;
    for (int i = 0; i < index; i++)
      x = x.next;
    return x;
  } else {
    Node<E> x = last;
    for (int i = size - 1; i > index; i--)
      x = x.prev;
    return x;
  }

ArrayList

ArrayList是平常开发中使用最多的集合类，一般数据库的查询都使用ArrayList进行接收。

他实现了RandomAccess接口，这是一个标志接口，没有实现，标志这个类能够进行快速访问。

ArrayList内部维护一个动态再分配的对象数组。

transient Object[] elementData;

• 初始化

ArrayList构造方法有三个方法

//指定初始化容量的构造方法
public ArrayList(int initialCapacity) {
  if (initialCapacity > 0) {
    this.elementData = new Object[initialCapacity];
  } else if (initialCapacity == 0) {
    this.elementData = EMPTY_ELEMENTDATA;
  } else {
    throw new IllegalArgumentException("Illegal Capacity: "+
                                       initialCapacity);
  }
}

//无参构造，初始化内部数组为一个空数组，第一次add元素时会初始化成默认大小为10的数组
public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//根据一个集合构建
public ArrayList(Collection<? extends E> c) {
  elementData = c.toArray();
  if ((size = elementData.length) != 0) {
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
      elementData = Arrays.copyOf(elementData, size, Object[].class);
  } else {
    // replace with empty array.
    this.elementData = EMPTY_ELEMENTDATA;
  }
}

• 新增元素

//新增元素
public boolean add(E e) {
  //判断内部数组容量是否超出默认大小
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  //将新元素保存到数组中
  elementData[size++] = e;
  return true;
}

private void ensureCapacityInternal(int minCapacity) {
  //如果elementData数组是空（无参构造函数），则取minCapacity和Default（10）中的最大值
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  }
    //判断是否需要扩容
  ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
  modCount++;

  // overflow-conscious code
  //如果当前所需要的最小容量大于内部数组的大小，则需要扩容
  if (minCapacity - elementData.length > 0)
    //扩容
    grow(minCapacity);
}

private void grow(int minCapacity) {
  // overflow-conscious code
  //记录扩容前的容量 第一次是0，扩容后是10
  int oldCapacity = elementData.length;
  //获取新的数组容量，相当于old + old * 0.5，左移一位是除以2
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
  //如果数组容量超过最大值(2147483639)，则使用hugeCapacity 2147483639 + 8
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
  // minCapacity is usually close to size, so this is a win:
  //将原来的数组复制到新的数组，并初始化扩容后的容量
  elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
  if (minCapacity < 0) // overflow
    throw new OutOfMemoryError();
  return (minCapacity > MAX_ARRAY_SIZE) ?
    Integer.MAX_VALUE :
  MAX_ARRAY_SIZE;
}

可以看到，ArrayList是一个可以动态扩容的List，默认容量是10，扩容后是原来的1.5倍，如果频繁的向其中添加元素，会导致其内部不断地进行扩容，伴随着复制数组，效率不高。

• 移除指定位置的元素

public E remove(int index) {
  //检查下标是否在范围内
  rangeCheck(index);

  modCount++;
  //获取当前下标下的值
  E oldValue = elementData(index);
  //计算要复制的数组个数
  int numMoved = size - index - 1;
  if (numMoved > 0)
    //从elementData的index+1位开始复制numMoved个元素到elementData的第index位开始
    System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);
  //清空最后一位的引用
  elementData[--size] = null; // clear to let GC do its work

  return oldValue;
}

image-20200519000244447.png

由上面的分析可以看出，LinkedList在新增、删除操作上的效率比较高，而ArrayList在查询的效率比较高，所以在实际开发中，要根据不同的应用场景使用不同的集合类型。

Vector

上面的LinkedList和ArrayList都是线程不安全的集合类，在多线程开发中，会有问题，而Vector是一个线程安全的集合，它的实现基本上和ArrayList一样，只是在方法上都加上了synchronized的关键字，保证每个有线程安全隐患的方法都是同步访问。

Set

HashSet

HashSet实际上内部是通过HashMap实现，把set中的元素当作key，一个固定的值作为value，插入到HashMap中去，由于HashMap不允许有相同的key，正好满足set的要求。

 private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

public boolean add(E e) {
  //将添加的元素put进map，如果返回值为null，则说明map中没有存过该值，则set成功
  return map.put(e, PRESENT)==null;
}

TreeSet

与HashSet类似TreeSet内部是通过TreeMap实现的，它可以确保集合中的元素处于排序状态。默认是使用自然比较器，TreeSet中元素的排序规则按照比较器确定，如果需要自定义比较器，则需要在初始化的时候传递参数，这里具体的代码分析在Map相关集合中细说。

LinkedHashSet

LinkedHashSet继承自HashSet，它通过链表记录元素插入到集合中的顺序。

Queue

ArrayDeque

ArrayDeque是一个双端队列，可以从两端插入元素和取出元素，默认的长度是16，也可以传入初始化的容量大小。

• 初始化

//无参构造函数，默认初始化容量为16
public ArrayDeque() {
  elements = new Object[16];
}
//设置容量大小
 public ArrayDeque(int numElements) {
   allocateElements(numElements);
 }

private void allocateElements(int numElements) {
  //获取默认的最小初始化容量8，必须是2的幂
  int initialCapacity = MIN_INITIAL_CAPACITY;
  // Find the best power of two to hold elements.
  // Tests "<=" because arrays aren't kept full.
  //如果出入的容量小于8，直接初始化数组
  //如果numElements大于等于8，则通过位运算，使得numElements值为2的k次幂，且比n大
  if (numElements >= initialCapacity) {
    initialCapacity = numElements;
    initialCapacity |= (initialCapacity >>>  1);
    initialCapacity |= (initialCapacity >>>  2);
    initialCapacity |= (initialCapacity >>>  4);
    initialCapacity |= (initialCapacity >>>  8);
    initialCapacity |= (initialCapacity >>> 16);
    initialCapacity++;

    if (initialCapacity < 0)   // Too many elements, must back off
      initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
  }
  elements = new Object[initialCapacity];
}

• 添加方法

public void addFirst(E e) {
  if (e == null)
    throw new NullPointerException();
  //将head - 1 与 数组长度 - 1取余，防止数组到了边界
  elements[head = (head - 1) & (elements.length - 1)] = e;
  //如果头和尾碰在一起，则进行扩容
  if (head == tail)
    doubleCapacity();
}


public void addLast(E e) {
  if (e == null)
    throw new NullPointerException();
  //将尾部设为e
  elements[tail] = e;
  //尾部加1，并与数组长度-1取余，防止数组越界
  //如果头部和尾部碰在一起，则扩容
  if ( (tail = (tail + 1) & (elements.length - 1)) == head)
    doubleCapacity();
}

//扩容方法
private void doubleCapacity() {
  assert head == tail;
  int p = head;
  int n = elements.length;
  int r = n - p; // number of elements to the right of p
  //右移一位，扩容两倍
  int newCapacity = n << 1;
  if (newCapacity < 0)
    throw new IllegalStateException("Sorry, deque too big");
  Object[] a = new Object[newCapacity];
  //复制数组数据
  //将head后到最后一位的数据复制到新数组的前面
  System.arraycopy(elements, p, a, 0, r);
  //将0到head的元素复制到新数组的从r开始的后面，如下图
  System.arraycopy(elements, 0, a, r, p);
  elements = a;
  head = 0;
  tail = n;
}

image-20200521234717498.png

• 移除数据

与添加数据类似，移除也可以从头和尾分别进行移除，原理类似，就不详细分析了。

由上面分析可以看出，ArrayDeque是一个效率不错的双向队列，也可以直接作为栈来使用。

PriorityQueue

PriorityQueue是一个优先队列，其中的元素可以按照任意的顺序插入，但是会按照书序进行检索。每次调用remove方法，都会获取队列中优先级最小的元素。 与其他集合类似，PriorityQueue内部也是通过一个数组保存数据，用堆（完全二叉树）这种逻辑结构来满足要求（关于堆），每次添加或者删除的时候，可以把最小的元素移动到根节点，默认的初始化容量是11，不同的是，在扩容的时候，如果当前容量小于64，则扩充为原来的2倍，超过64，则扩充为原来的1.5倍。

这里贴出几段关键的代码

//使用比较器筛选 k表示当前存入的元素个数size，x表示元素本身
//这里是为了实现二叉树
private void siftUpComparable(int k, E x) {
  Comparable<? super E> key = (Comparable<? super E>) x;
  while (k > 0) {
    //k-1进行无符号右移一位，即是缩小两倍，
    int parent = (k - 1) >>> 1;
    //获取此位置上的元素
    Object e = queue[parent];
    //比较元素，如果x比parent大，则直接跳出循环，将k位置的数组值设为x
    //否则，将parent的值移动到当前位置，并以parent的下标位置，继续循环
    if (key.compareTo((E) e) >= 0)
      break;
    queue[k] = e;
    k = parent;
  }
  queue[k] = key;
}

Map接口

image-20200526000606557.png

HashMap

HashMap是最常用的集合类之一，jdk1.7和jdk1.8中对于该集合做了改变，1.7中HashMap采用的是数组+链表的数据结构，1.8中，增加了红黑树的结构，当一个桶下面的链表的长度超过8之后，会把链表转为红黑树结构。HashMap的一些基本信息：

• 默认的初始化数组大小为16，最大为2的32次方
• 负载因子为0.75
• 扩容为原数组的2倍
• 当桶中的元素超过64，且链表的长度超过8之后进行树化，小于6时再转为链表

关键源码

//初始化
public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " +
                                       initialCapacity);
  //判断初始化容量是否超过最大值
  if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
  if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " +
                                       loadFactor);
  this.loadFactor = loadFactor;
  //计算阀值，当put元素之后，如果到达阀值，需要对数组进行扩容
  this.threshold = tableSizeFor(initialCapacity);
}

//put元素
public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
  Node<K,V>[] tab;

  Node<K,V> p;
  //n表示数组容量，i表示当前插入的下标
  int n, i;
  //第一次put的时候，存放node的table为空，需要先初始化
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  //如果当前hash的位置内没有存储元素，则直接插入到该位置
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  else {
    Node<K,V> e; K k;
    //如果当前hash下标的节点key相同，保存e，后续判断是否要修改值
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
    //如果p是红黑树，则调用putTreeVal新增一个元素
    else if (p instanceof TreeNode)
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
      //链表情况，遍历当前节点下所有的元素
      for (int binCount = 0; ; ++binCount) {
        //如果p.next为空，则直接将元素设置p节点的next
        if ((e = p.next) == null) {
          p.next = newNode(hash, key, value, null);
          //如果当前链表的个数超出8，则将链表转为红黑树
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
          break;
        }
        //如果当前节点的key与插入的key相同，则保存当前节点，用于判断是否要替换
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        p = e;
      }
    }
    //如果e不为空（key已经存在），则替换value
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e);
      return oldValue;
    }
  }
  ++modCount;
  if (++size > threshold)
    resize();
  afterNodeInsertion(evict);
  return null;
}

//扩容
final Node<K,V>[] resize() {
  Node<K,V>[] oldTab = table;
  int oldCap = (oldTab == null) ? 0 : oldTab.length;
  int oldThr = threshold;
  int newCap, newThr = 0;
  if (oldCap > 0) {
    //如果之前的数组容量已经到达最大值，则调整阀值为最大的integer
    if (oldCap >= MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return oldTab;
    }
    //扩容两倍，如果还小于最大容量，且之前的容量比默认的16大，则把阀值也扩大两倍
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
      newThr = oldThr << 1; // double threshold
  }
  else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;
  else {
    // zero initial threshold signifies using defaults
    //初始化默认节点数组为16
    newCap = DEFAULT_INITIAL_CAPACITY;
    //初始化默认的阀值为16*0.75 = 12
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
  }
  threshold = newThr;
  @SuppressWarnings({"rawtypes","unchecked"})
  //创建新的节点数组
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  //如果之前的节点数组，不为空，则需要rehash，将数据值存入新的数组中
  if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e;
      if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
        if (e.next == null)
          //rehash后存入数组中
          newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof TreeNode)
          //如果该节点是红黑树，则将树重新插入新的数组中
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // preserve order
          //如果是链表，则使用尾插法，将所有的节点加入到新的数组中
          Node<K,V> loHead = null, loTail = null;
          Node<K,V> hiHead = null, hiTail = null;
          Node<K,V> next;
          do {
            next = e.next;
            if ((e.hash & oldCap) == 0) {
              if (loTail == null)
                loHead = e;
              else
                loTail.next = e;
              loTail = e;
            }
            else {
              if (hiTail == null)
                hiHead = e;
              else
                hiTail.next = e;
              hiTail = e;
            }
          } while ((e = next) != null);
          if (loTail != null) {
            loTail.next = null;
            newTab[j] = loHead;
          }
          if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead;
          }
        }
      }
    }
  }
  return newTab;
}

//获取元素
final Node<K,V> getNode(int hash, Object key) {
  Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  //如果数组不为空，长度不为0，且当且槽内的节点不为空
  if ((tab = table) != null && (n = tab.length) > 0 &&
      (first = tab[(n - 1) & hash]) != null) {
    //判断第一个节点的hash和key是否相等，如果相等，则返回该节点
    if (first.hash == hash && // always check first node
        ((k = first.key) == key || (key != null && key.equals(k))))
      return first;
    if ((e = first.next) != null) {
      //如果第一个节点不是要查询的key，则根据该节点下是链表还是红黑树查找节点
      if (first instanceof TreeNode)
        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
      do {
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          return e;
      } while ((e = e.next) != null);
    }
  }
  return null;
}

//移除元素
final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
  Node<K,V>[] tab; Node<K,V> p; int n, index;
  if ((tab = table) != null && (n = tab.length) > 0 &&
      (p = tab[index = (n - 1) & hash]) != null) {
    // 根据key，获取到对应的node，保存在node变量中
    Node<K,V> node = null, e; K k; V v;
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      node = p;
    else if ((e = p.next) != null) {
      if (p instanceof TreeNode)
        node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
      else {
        do {
          if (e.hash == hash &&
              ((k = e.key) == key ||
               (key != null && key.equals(k)))) {
            node = e;
            break;
          }
          p = e;
        } while ((e = e.next) != null);
      }
    }
    //如果node不为空，则
    if (node != null && (!matchValue || (v = node.value) == value ||
                         (value != null && value.equals(v)))) {
      if (node instanceof TreeNode)
        //移除红黑树中相应的节点，可能需要去树链表化
        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
      else if (node == p)
        //直接设置index下标下的节点为node的下一个节点
        tab[index] = node.next;
      else
        //此时p是node的上一个节点，把p的next设为node的next节点
        p.next = node.next;
      ++modCount;
      --size;
      afterNodeRemoval(node);
      return node;
    }
  }
  return null;
}

TreeMap

TreeMap底层通过红黑树，实现了对于元素的排序功能，当插入一条数据时候，会根据一定的排序方式，对key进行比较排序，然后插入到红黑树相应的位置。关于红黑树，有几个特性需要了解：

• 每个节点是红色或者黑色
• 根节点是黑色
• 每个叶子节点是黑色（这里的叶子节点，是指为空的叶子节点
• 如果一个节点是红色的，则他的子节点必须是黑色的
• 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点

源码分析

//put元素
public V put(K key, V value) {
  Entry<K,V> t = root;
  //第一次直接新增一个entry
  if (t == null) {
    compare(key, key); // type (and possibly null) check

    root = new Entry<>(key, value, null);
    size = 1;
    modCount++;
    return null;
  }
  int cmp;
  Entry<K,V> parent;
  // split comparator and comparable paths
  Comparator<? super K> cpr = comparator;
  if (cpr != null) {
    //如果root不为空，且有自定义的比较器，则比较当前key和root的key
    //do while 循环，逐个比较各entry的key，如果比key大，则获取右子节点，否则获取左子节点
    //直到最后一个节点
    do {
      parent = t;
      cmp = cpr.compare(key, t.key);
      if (cmp < 0)
        t = t.left;
      else if (cmp > 0)
        t = t.right;
      else
        return t.setValue(value);
    } while (t != null);
  }
  else {
    if (key == null)
      throw new NullPointerException();
    @SuppressWarnings("unchecked")
    //获取当前key的默认比较器，按照相同的逻辑判断要插入的位置
    Comparable<? super K> k = (Comparable<? super K>) key;
    do {
      parent = t;
      cmp = k.compareTo(t.key);
      if (cmp < 0)
        t = t.left;
      else if (cmp > 0)
        t = t.right;
      else
        return t.setValue(value);
    } while (t != null);
  }
  //创建新的entry
  Entry<K,V> e = new Entry<>(key, value, parent);
  //如果最后一次比较为比父节点小，则添加到左子节点上，否则加在右子节点上
  if (cmp < 0)
    parent.left = e;
  else
    parent.right = e;
  //重新调整树的结构，满足红黑树的条件
  fixAfterInsertion(e);
  size++;
  modCount++;
  return null;
}
//删除节点
public V remove(Object key) {
  Entry<K,V> p = getEntry(key);
  if (p == null)
    return null;

  V oldValue = p.value;
  deleteEntry(p);
  return oldValue;
}

private void deleteEntry(Entry<K,V> p) {
  modCount++;
  size--;

  /**
    * 二叉树的删除规则
    * 1.如果删除的节点下既有左节点，又有右节点，则将右节点下的最小元素作为替代元素，与删除节点交换，并删除子节点
    * 2.如果删除节点下只有一个节点，则直接与删除节点交换后，从删除该节点
    * 3.如果删除节点下没有子节点，则直接将该节点删除
    * 4.如果是红黑树，删除的是黑色节点，则需要重新平衡
    * 5.如果有替代元素，则交换后，需要以此元素作为当前节点，再平衡
    * 6.如果没有替代元素，则以当前元素为节点再平衡
  */     
  // If strictly internal, copy successor's element to p and then make p
  // point to successor.接班人，
  if (p.left != null && p.right != null) {
    Entry<K,V> s = successor(p);
    p.key = s.key;
    p.value = s.value;
    p = s;
  } // p has 2 children

  // Start fixup at replacement node, if it exists.
  Entry<K,V> replacement = (p.left != null ? p.left : p.right);

  if (replacement != null) {
    // Link replacement to parent
    replacement.parent = p.parent;
    if (p.parent == null)
      root = replacement;
    else if (p == p.parent.left)
      p.parent.left  = replacement;
    else
      p.parent.right = replacement;

    // Null out links so they are OK to use by fixAfterDeletion.
    p.left = p.right = p.parent = null;

    // Fix replacement
    if (p.color == BLACK)
      fixAfterDeletion(replacement);
  } else if (p.parent == null) { // return if we are the only node.
    root = null;
  } else { //  No children. Use self as phantom replacement and unlink.
    if (p.color == BLACK)
      fixAfterDeletion(p);

    if (p.parent != null) {
      if (p == p.parent.left)
        p.parent.left = null;
      else if (p == p.parent.right)
        p.parent.right = null;
      p.parent = null;
    }
  }
}

LinkedHashMap

LinkedHashMap继承与HashMap，它拥有HashMap的所有特性，即使用数组、链表加红黑树的结构，同时，在内部它还维护一个双向链表，他能够保存元素的插入顺序，可以按照插入顺序获取到集合中的key和value，也可以根据访问顺序对元素进行排序。利用这个特性，可以实现LRU（Least Recently Used 最近最少使用，也就是优先淘汰最近最少使用的元素）。

源码分析

//内部类，继承自HashMap.Node,并新增before，after属性，实现双向链表

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

private static final long serialVersionUID = 3801124242820219131L;

/**
       * 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;

/**
     * The iteration ordering method for this linked hash map: <tt>true</tt>
     * for access-order, <tt>false</tt> for insertion-order.
     *
     * @serial
     */
//true表示按照访问顺序排序，false表示按照插入顺序排序
final boolean accessOrder;

在HashMap已经预留了方法，用来对LinkedHashMap操作内部的双向链表。

// Callbacks to allow LinkedHashMap post-actions
//这三个方法在HashMap中并没有具体的实现，但在LinkedHashMap都逐一实现了功能
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }


//删除元素后将双向链表中的该元素也删除
void afterNodeRemoval(Node<K,V> e) { // unlink
  LinkedHashMap.Entry<K,V> p =
    (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  p.before = p.after = null;
  if (b == null)
    head = a;
  else
    b.after = a;
  if (a == null)
    tail = b;
  else
    a.before = b;
}

//删除双线链表中的最先插入或者最少使用的节点
//evict是驱逐的意思，true表示可能删除链尾的元素（取决于removeEldestEntry方法返回值，默认范围false，不删除）
void afterNodeInsertion(boolean evict) { // possibly remove eldest
  LinkedHashMap.Entry<K,V> first;
  if (evict && (first = head) != null && removeEldestEntry(first)) {
    K key = first.key;
    removeNode(hash(key), key, null, false, true);
  }
}
//accessOrder为ture即按照元素访问顺序排序时，
//当put一个已经存在的key的值（更新）后，将该节点调整至双向链表的末尾
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)
      head = a;
    else
      b.after = a;
    if (a != null)
      a.before = b;
    else
      last = b;
    if (last == null)
      head = p;
    else {
      p.before = last;
      last.after = p;
    }
    tail = p;
    ++modCount;
  }
}

public V get(Object key) {
  Node<K,V> e;
  if ((e = getNode(hash(key), key)) == null)
    return null;
  //如果accessOrder为true，更新双向链表
  if (accessOrder)
    afterNodeAccess(e);
  return e.value;
}

通过继承LinkedHashMap，并且初始化集合的时候，将accessOrder设为true，并且重写removeEldestEntry方法，根据条件返回true则可以实现LRU。

WeakHashMap

WeakHashMap是一个特殊的map，他的key是一个弱引用，当进行GC的时候，如果key没有被强引用，那么这个key就会被GC清除，利用这个特性可以实现缓存的功能。WeakHashMap有以下几个特性：

• 数据结构为数组和链表
• 初始化容量是16，扩容后是原来的2倍
• 插入元素到链表中是使用的头插法
• 如果传入的key为空，则使用静态变量Object替代空对象
• 操作map之前，会调用expungeStaleEntries() 方法移除队列(GC的时候会把要清除的key保存到一个queue中)中已经被清除的key所对应的所有entry。

总结：