集合

Collection 接口

List

LinkedList

LinkedList是一個(gè)雙向鏈表，往集合中插入數(shù)據(jù)和刪除數(shù)據(jù)效率非常高，只需要移動(dòng)相關(guān)節(jié)點(diǎn)的next和previous指向的對(duì)象就能完成刪除和新增的操作。但是雙向鏈表的讀取數(shù)據(jù)的效率非常低。get()方法的時(shí)間復(fù)雜度為n/2。

源碼窺探

• 新增元素

//添加元素到集合中
public boolean add(E e) {
  linkLast(e);
  return true;
}
void linkLast(E e) {
  //獲取當(dāng)前雙向鏈表的最后一個(gè)節(jié)點(diǎn)
  final Node<E> l = last;
  //把當(dāng)前要加入到集合中的數(shù)據(jù)包裝成node數(shù)據(jù)結(jié)構(gòu)
  final Node<E> newNode = new Node<>(l, e, null);
  //設(shè)置鏈表中最后一個(gè)節(jié)點(diǎn)指向新創(chuàng)建的node節(jié)點(diǎn)
  last = newNode;
  //判斷是否是第一次新增數(shù)據(jù)，如果是，則當(dāng)前新增的節(jié)點(diǎn)也是首節(jié)點(diǎn)
  //否則，把新增前的最后一個(gè)節(jié)點(diǎn)的next節(jié)點(diǎn)設(shè)置為新節(jié)點(diǎn)
  if (l == null)
    first = newNode;
  else
    l.next = newNode;
  //集合元素個(gè)數(shù)+1
  size++;
  //修改計(jì)數(shù)+1，該屬性是用來(lái)記錄集合中元素的修改狀態(tài)
  modCount++;
}

• 刪除元素

//刪除節(jié)點(diǎn)
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;
  //獲取當(dāng)前的節(jié)點(diǎn)的前置節(jié)點(diǎn)和后置節(jié)點(diǎn)
  final Node<E> next = x.next;
  final Node<E> prev = x.prev;

  //處理前置節(jié)點(diǎn)
  //如果是prev是空，則是首節(jié)點(diǎn)，則把當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)設(shè)置為首節(jié)點(diǎn)
  if (prev == null) {
    first = next;
  } else {
    //不為空，則將前一個(gè)節(jié)點(diǎn)的下一個(gè)幾點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)的next節(jié)點(diǎn)，（跳過(guò)當(dāng)前節(jié)點(diǎn)）
    prev.next = next;
    x.prev = null;
  }

  //處理后置節(jié)點(diǎn)
  if (next == null) {
    last = prev;
  } else {
    next.prev = prev;
    x.next = null;
  }
    //將節(jié)點(diǎn)保存的數(shù)據(jù)置空
  x.item = null;
  //減少當(dāng)前集合大小
  size--;
  //修改次數(shù)加1
  modCount++;
  return element;
}

• 獲取元素

public E get(int index) {
  //判斷index下標(biāo)是否超出范圍
  checkElementIndex(index);
  return node(index).item;
}

Node<E> node(int index) {
  // assert isElementIndex(index);
  //size >> 1 左移一位，相當(dāng)于除以2，如果index小于鏈表元素個(gè)數(shù)的一辦
  //從0開始遍歷，如果大于size的一半，則從鏈表尾部開始遍歷
  //這個(gè)方法的效率很低，不建議使用
  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是平常開發(fā)中使用最多的集合類，一般數(shù)據(jù)庫(kù)的查詢都使用ArrayList進(jìn)行接收。

他實(shí)現(xiàn)了RandomAccess接口，這是一個(gè)標(biāo)志接口，沒(méi)有實(shí)現(xiàn)，標(biāo)志這個(gè)類能夠進(jìn)行快速訪問(wèn)。

ArrayList內(nèi)部維護(hù)一個(gè)動(dòng)態(tài)再分配的對(duì)象數(shù)組。

transient Object[] elementData;

• 初始化

ArrayList構(gòu)造方法有三個(gè)方法

//指定初始化容量的構(gòu)造方法
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);
  }
}

//無(wú)參構(gòu)造，初始化內(nèi)部數(shù)組為一個(gè)空數(shù)組，第一次add元素時(shí)會(huì)初始化成默認(rèn)大小為10的數(shù)組
public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//根據(jù)一個(gè)集合構(gòu)建
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) {
  //判斷內(nèi)部數(shù)組容量是否超出默認(rèn)大小
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  //將新元素保存到數(shù)組中
  elementData[size++] = e;
  return true;
}

private void ensureCapacityInternal(int minCapacity) {
  //如果elementData數(shù)組是空（無(wú)參構(gòu)造函數(shù)），則取minCapacity和Default（10）中的最大值
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  }
    //判斷是否需要擴(kuò)容
  ensureExplicitCapacity(minCapacity);
}

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

  // overflow-conscious code
  //如果當(dāng)前所需要的最小容量大于內(nèi)部數(shù)組的大小，則需要擴(kuò)容
  if (minCapacity - elementData.length > 0)
    //擴(kuò)容
    grow(minCapacity);
}

private void grow(int minCapacity) {
  // overflow-conscious code
  //記錄擴(kuò)容前的容量 第一次是0，擴(kuò)容后是10
  int oldCapacity = elementData.length;
  //獲取新的數(shù)組容量，相當(dāng)于old + old * 0.5，左移一位是除以2
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
  //如果數(shù)組容量超過(guò)最大值(2147483639)，則使用hugeCapacity 2147483639 + 8
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
  // minCapacity is usually close to size, so this is a win:
  //將原來(lái)的數(shù)組復(fù)制到新的數(shù)組，并初始化擴(kuò)容后的容量
  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是一個(gè)可以動(dòng)態(tài)擴(kuò)容的List，默認(rèn)容量是10，擴(kuò)容后是原來(lái)的1.5倍，如果頻繁的向其中添加元素，會(huì)導(dǎo)致其內(nèi)部不斷地進(jìn)行擴(kuò)容，伴隨著復(fù)制數(shù)組，效率不高。

• 移除指定位置的元素

public E remove(int index) {
  //檢查下標(biāo)是否在范圍內(nèi)
  rangeCheck(index);

  modCount++;
  //獲取當(dāng)前下標(biāo)下的值
  E oldValue = elementData(index);
  //計(jì)算要復(fù)制的數(shù)組個(gè)數(shù)
  int numMoved = size - index - 1;
  if (numMoved > 0)
    //從elementData的index+1位開始復(fù)制numMoved個(gè)元素到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在查詢的效率比較高，所以在實(shí)際開發(fā)中，要根據(jù)不同的應(yīng)用場(chǎng)景使用不同的集合類型。

Vector

上面的LinkedList和ArrayList都是線程不安全的集合類，在多線程開發(fā)中，會(huì)有問(wèn)題，而Vector是一個(gè)線程安全的集合，它的實(shí)現(xiàn)基本上和ArrayList一樣，只是在方法上都加上了synchronized的關(guān)鍵字，保證每個(gè)有線程安全隱患的方法都是同步訪問(wèn)。

Set

HashSet

HashSet實(shí)際上內(nèi)部是通過(guò)HashMap實(shí)現(xiàn)，把set中的元素當(dāng)作key，一個(gè)固定的值作為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進(jìn)map，如果返回值為null，則說(shuō)明map中沒(méi)有存過(guò)該值，則set成功
  return map.put(e, PRESENT)==null;
}

TreeSet

與HashSet類似TreeSet內(nèi)部是通過(guò)TreeMap實(shí)現(xiàn)的，它可以確保集合中的元素處于排序狀態(tài)。默認(rèn)是使用自然比較器，TreeSet中元素的排序規(guī)則按照比較器確定，如果需要自定義比較器，則需要在初始化的時(shí)候傳遞參數(shù)，這里具體的代碼分析在Map相關(guān)集合中細(xì)說(shuō)。

LinkedHashSet

LinkedHashSet繼承自HashSet，它通過(guò)鏈表記錄元素插入到集合中的順序。

Queue

ArrayDeque

ArrayDeque是一個(gè)雙端隊(duì)列，可以從兩端插入元素和取出元素，默認(rèn)的長(zhǎng)度是16，也可以傳入初始化的容量大小。

• 初始化

//無(wú)參構(gòu)造函數(shù)，默認(rèn)初始化容量為16
public ArrayDeque() {
  elements = new Object[16];
}
//設(shè)置容量大小
 public ArrayDeque(int numElements) {
   allocateElements(numElements);
 }

private void allocateElements(int numElements) {
  //獲取默認(rèn)的最小初始化容量8，必須是2的冪
  int initialCapacity = MIN_INITIAL_CAPACITY;
  // Find the best power of two to hold elements.
  // Tests "<=" because arrays aren't kept full.
  //如果出入的容量小于8，直接初始化數(shù)組
  //如果numElements大于等于8，則通過(guò)位運(yùn)算，使得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 與 數(shù)組長(zhǎng)度 - 1取余，防止數(shù)組到了邊界
  elements[head = (head - 1) & (elements.length - 1)] = e;
  //如果頭和尾碰在一起，則進(jìn)行擴(kuò)容
  if (head == tail)
    doubleCapacity();
}


public void addLast(E e) {
  if (e == null)
    throw new NullPointerException();
  //將尾部設(shè)為e
  elements[tail] = e;
  //尾部加1，并與數(shù)組長(zhǎng)度-1取余，防止數(shù)組越界
  //如果頭部和尾部碰在一起，則擴(kuò)容
  if ( (tail = (tail + 1) & (elements.length - 1)) == head)
    doubleCapacity();
}

//擴(kuò)容方法
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
  //右移一位，擴(kuò)容兩倍
  int newCapacity = n << 1;
  if (newCapacity < 0)
    throw new IllegalStateException("Sorry, deque too big");
  Object[] a = new Object[newCapacity];
  //復(fù)制數(shù)組數(shù)據(jù)
  //將head后到最后一位的數(shù)據(jù)復(fù)制到新數(shù)組的前面
  System.arraycopy(elements, p, a, 0, r);
  //將0到head的元素復(fù)制到新數(shù)組的從r開始的后面，如下圖
  System.arraycopy(elements, 0, a, r, p);
  elements = a;
  head = 0;
  tail = n;
}

image-20200521234717498.png

• 移除數(shù)據(jù)

與添加數(shù)據(jù)類似，移除也可以從頭和尾分別進(jìn)行移除，原理類似，就不詳細(xì)分析了。

由上面分析可以看出，ArrayDeque是一個(gè)效率不錯(cuò)的雙向隊(duì)列，也可以直接作為棧來(lái)使用。

PriorityQueue

PriorityQueue是一個(gè)優(yōu)先隊(duì)列，其中的元素可以按照任意的順序插入，但是會(huì)按照書序進(jìn)行檢索。每次調(diào)用remove方法，都會(huì)獲取隊(duì)列中優(yōu)先級(jí)最小的元素。 與其他集合類似，PriorityQueue內(nèi)部也是通過(guò)一個(gè)數(shù)組保存數(shù)據(jù)，用堆（完全二叉樹）這種邏輯結(jié)構(gòu)來(lái)滿足要求（關(guān)于堆），每次添加或者刪除的時(shí)候，可以把最小的元素移動(dòng)到根節(jié)點(diǎn)，默認(rèn)的初始化容量是11，不同的是，在擴(kuò)容的時(shí)候，如果當(dāng)前容量小于64，則擴(kuò)充為原來(lái)的2倍，超過(guò)64，則擴(kuò)充為原來(lái)的1.5倍。

這里貼出幾段關(guān)鍵的代碼

//使用比較器篩選 k表示當(dāng)前存入的元素個(gè)數(shù)size，x表示元素本身
//這里是為了實(shí)現(xiàn)二叉樹
private void siftUpComparable(int k, E x) {
  Comparable<? super E> key = (Comparable<? super E>) x;
  while (k > 0) {
    //k-1進(jìn)行無(wú)符號(hào)右移一位，即是縮小兩倍，
    int parent = (k - 1) >>> 1;
    //獲取此位置上的元素
    Object e = queue[parent];
    //比較元素，如果x比parent大，則直接跳出循環(huán)，將k位置的數(shù)組值設(shè)為x
    //否則，將parent的值移動(dòng)到當(dāng)前位置，并以parent的下標(biāo)位置，繼續(xù)循環(huán)
    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中對(duì)于該集合做了改變，1.7中HashMap采用的是數(shù)組+鏈表的數(shù)據(jù)結(jié)構(gòu)，1.8中，增加了紅黑樹的結(jié)構(gòu)，當(dāng)一個(gè)桶下面的鏈表的長(zhǎng)度超過(guò)8之后，會(huì)把鏈表轉(zhuǎn)為紅黑樹結(jié)構(gòu)。HashMap的一些基本信息：

• 默認(rèn)的初始化數(shù)組大小為16，最大為2的32次方
• 負(fù)載因子為0.75
• 擴(kuò)容為原數(shù)組的2倍
• 當(dāng)桶中的元素超過(guò)64，且鏈表的長(zhǎng)度超過(guò)8之后進(jìn)行樹化，小于6時(shí)再轉(zhuǎn)為鏈表

關(guān)鍵源碼

//初始化
public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " +
                                       initialCapacity);
  //判斷初始化容量是否超過(guò)最大值
  if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
  if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " +
                                       loadFactor);
  this.loadFactor = loadFactor;
  //計(jì)算閥值，當(dāng)put元素之后，如果到達(dá)閥值，需要對(duì)數(shù)組進(jìn)行擴(kuò)容
  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表示數(shù)組容量，i表示當(dāng)前插入的下標(biāo)
  int n, i;
  //第一次put的時(shí)候，存放node的table為空，需要先初始化
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  //如果當(dāng)前hash的位置內(nèi)沒(méi)有存儲(chǔ)元素，則直接插入到該位置
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  else {
    Node<K,V> e; K k;
    //如果當(dāng)前hash下標(biāo)的節(jié)點(diǎn)key相同，保存e，后續(xù)判斷是否要修改值
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
    //如果p是紅黑樹，則調(diào)用putTreeVal新增一個(gè)元素
    else if (p instanceof TreeNode)
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
      //鏈表情況，遍歷當(dāng)前節(jié)點(diǎn)下所有的元素
      for (int binCount = 0; ; ++binCount) {
        //如果p.next為空，則直接將元素設(shè)置p節(jié)點(diǎn)的next
        if ((e = p.next) == null) {
          p.next = newNode(hash, key, value, null);
          //如果當(dāng)前鏈表的個(gè)數(shù)超出8，則將鏈表轉(zhuǎn)為紅黑樹
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
          break;
        }
        //如果當(dāng)前節(jié)點(diǎn)的key與插入的key相同，則保存當(dāng)前節(jié)點(diǎn)，用于判斷是否要替換
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        p = e;
      }
    }
    //如果e不為空（key已經(jīng)存在），則替換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;
}

//擴(kuò)容
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) {
    //如果之前的數(shù)組容量已經(jīng)到達(dá)最大值，則調(diào)整閥值為最大的integer
    if (oldCap >= MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return oldTab;
    }
    //擴(kuò)容兩倍，如果還小于最大容量，且之前的容量比默認(rèn)的16大，則把閥值也擴(kuò)大兩倍
    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
    //初始化默認(rèn)節(jié)點(diǎn)數(shù)組為16
    newCap = DEFAULT_INITIAL_CAPACITY;
    //初始化默認(rèn)的閥值為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"})
  //創(chuàng)建新的節(jié)點(diǎn)數(shù)組
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  //如果之前的節(jié)點(diǎn)數(shù)組，不為空，則需要rehash，將數(shù)據(jù)值存入新的數(shù)組中
  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后存入數(shù)組中
          newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof TreeNode)
          //如果該節(jié)點(diǎn)是紅黑樹，則將樹重新插入新的數(shù)組中
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // preserve order
          //如果是鏈表，則使用尾插法，將所有的節(jié)點(diǎn)加入到新的數(shù)組中
          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;
  //如果數(shù)組不為空，長(zhǎng)度不為0，且當(dāng)且槽內(nèi)的節(jié)點(diǎn)不為空
  if ((tab = table) != null && (n = tab.length) > 0 &&
      (first = tab[(n - 1) & hash]) != null) {
    //判斷第一個(gè)節(jié)點(diǎn)的hash和key是否相等，如果相等，則返回該節(jié)點(diǎn)
    if (first.hash == hash && // always check first node
        ((k = first.key) == key || (key != null && key.equals(k))))
      return first;
    if ((e = first.next) != null) {
      //如果第一個(gè)節(jié)點(diǎn)不是要查詢的key，則根據(jù)該節(jié)點(diǎn)下是鏈表還是紅黑樹查找節(jié)點(diǎn)
      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) {
    // 根據(jù)key，獲取到對(duì)應(yīng)的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)
        //移除紅黑樹中相應(yīng)的節(jié)點(diǎn)，可能需要去樹鏈表化
        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
      else if (node == p)
        //直接設(shè)置index下標(biāo)下的節(jié)點(diǎn)為node的下一個(gè)節(jié)點(diǎn)
        tab[index] = node.next;
      else
        //此時(shí)p是node的上一個(gè)節(jié)點(diǎn)，把p的next設(shè)為node的next節(jié)點(diǎn)
        p.next = node.next;
      ++modCount;
      --size;
      afterNodeRemoval(node);
      return node;
    }
  }
  return null;
}

TreeMap

TreeMap底層通過(guò)紅黑樹，實(shí)現(xiàn)了對(duì)于元素的排序功能，當(dāng)插入一條數(shù)據(jù)時(shí)候，會(huì)根據(jù)一定的排序方式，對(duì)key進(jìn)行比較排序，然后插入到紅黑樹相應(yīng)的位置。關(guān)于紅黑樹，有幾個(gè)特性需要了解：

• 每個(gè)節(jié)點(diǎn)是紅色或者黑色
• 根節(jié)點(diǎn)是黑色
• 每個(gè)葉子節(jié)點(diǎn)是黑色（這里的葉子節(jié)點(diǎn)，是指為空的葉子節(jié)點(diǎn)
• 如果一個(gè)節(jié)點(diǎn)是紅色的，則他的子節(jié)點(diǎn)必須是黑色的
• 從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)

源碼分析

//put元素
public V put(K key, V value) {
  Entry<K,V> t = root;
  //第一次直接新增一個(gè)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不為空，且有自定義的比較器，則比較當(dāng)前key和root的key
    //do while 循環(huán)，逐個(gè)比較各entry的key，如果比key大，則獲取右子節(jié)點(diǎn)，否則獲取左子節(jié)點(diǎn)
    //直到最后一個(gè)節(jié)點(diǎn)
    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")
    //獲取當(dāng)前key的默認(rèn)比較器，按照相同的邏輯判斷要插入的位置
    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);
  }
  //創(chuàng)建新的entry
  Entry<K,V> e = new Entry<>(key, value, parent);
  //如果最后一次比較為比父節(jié)點(diǎn)小，則添加到左子節(jié)點(diǎn)上，否則加在右子節(jié)點(diǎn)上
  if (cmp < 0)
    parent.left = e;
  else
    parent.right = e;
  //重新調(diào)整樹的結(jié)構(gòu)，滿足紅黑樹的條件
  fixAfterInsertion(e);
  size++;
  modCount++;
  return null;
}
//刪除節(jié)點(diǎn)
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--;

  /**
    * 二叉樹的刪除規(guī)則
    * 1.如果刪除的節(jié)點(diǎn)下既有左節(jié)點(diǎn)，又有右節(jié)點(diǎn)，則將右節(jié)點(diǎn)下的最小元素作為替代元素，與刪除節(jié)點(diǎn)交換，并刪除子節(jié)點(diǎn)
    * 2.如果刪除節(jié)點(diǎn)下只有一個(gè)節(jié)點(diǎn)，則直接與刪除節(jié)點(diǎn)交換后，從刪除該節(jié)點(diǎn)
    * 3.如果刪除節(jié)點(diǎn)下沒(méi)有子節(jié)點(diǎn)，則直接將該節(jié)點(diǎn)刪除
    * 4.如果是紅黑樹，刪除的是黑色節(jié)點(diǎn)，則需要重新平衡
    * 5.如果有替代元素，則交換后，需要以此元素作為當(dāng)前節(jié)點(diǎn)，再平衡
    * 6.如果沒(méi)有替代元素，則以當(dāng)前元素為節(jié)點(diǎn)再平衡
  */     
  // 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的所有特性，即使用數(shù)組、鏈表加紅黑樹的結(jié)構(gòu)，同時(shí)，在內(nèi)部它還維護(hù)一個(gè)雙向鏈表，他能夠保存元素的插入順序，可以按照插入順序獲取到集合中的key和value，也可以根據(jù)訪問(wèn)順序?qū)υ剡M(jìn)行排序。利用這個(gè)特性，可以實(shí)現(xiàn)LRU（Least Recently Used 最近最少使用，也就是優(yōu)先淘汰最近最少使用的元素）。

源碼分析

//內(nèi)部類，繼承自HashMap.Node,并新增before，after屬性，實(shí)現(xiàn)雙向鏈表

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.
       * 雙向鏈表的頭（最多使用或者最新插入的節(jié)點(diǎn)）
       */
transient LinkedHashMap.Entry<K,V> head;

/**
     * The tail (youngest) of the doubly linked list.
     * 雙向鏈表的尾（最少使用或者最開始插入的節(jié)點(diǎn)）
     */
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表示按照訪問(wèn)順序排序，false表示按照插入順序排序
final boolean accessOrder;

在HashMap已經(jīng)預(yù)留了方法，用來(lái)對(duì)LinkedHashMap操作內(nèi)部的雙向鏈表。

// Callbacks to allow LinkedHashMap post-actions
//這三個(gè)方法在HashMap中并沒(méi)有具體的實(shí)現(xiàn)，但在LinkedHashMap都逐一實(shí)現(xiàn)了功能
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;
}

//刪除雙線鏈表中的最先插入或者最少使用的節(jié)點(diǎn)
//evict是驅(qū)逐的意思，true表示可能刪除鏈尾的元素（取決于removeEldestEntry方法返回值，默認(rèn)范圍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即按照元素訪問(wèn)順序排序時(shí)，
//當(dāng)put一個(gè)已經(jīng)存在的key的值（更新）后，將該節(jié)點(diǎn)調(diào)整至雙向鏈表的末尾
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;
}

通過(guò)繼承LinkedHashMap，并且初始化集合的時(shí)候，將accessOrder設(shè)為true，并且重寫removeEldestEntry方法，根據(jù)條件返回true則可以實(shí)現(xiàn)LRU。

WeakHashMap

WeakHashMap是一個(gè)特殊的map，他的key是一個(gè)弱引用，當(dāng)進(jìn)行GC的時(shí)候，如果key沒(méi)有被強(qiáng)引用，那么這個(gè)key就會(huì)被GC清除，利用這個(gè)特性可以實(shí)現(xiàn)緩存的功能。WeakHashMap有以下幾個(gè)特性：

• 數(shù)據(jù)結(jié)構(gòu)為數(shù)組和鏈表
• 初始化容量是16，擴(kuò)容后是原來(lái)的2倍
• 插入元素到鏈表中是使用的頭插法
• 如果傳入的key為空，則使用靜態(tài)變量Object替代空對(duì)象
• 操作map之前，會(huì)調(diào)用expungeStaleEntries() 方法移除隊(duì)列(GC的時(shí)候會(huì)把要清除的key保存到一個(gè)queue中)中已經(jīng)被清除的key所對(duì)應(yīng)的所有entry。

總結(jié)：