本筆記來自 計(jì)算機(jī)程序的思維邏輯 系列文章

ArrayList

內(nèi)部組成

• Object[] elementData，動(dòng)態(tài)數(shù)組，存放數(shù)據(jù)
• int size，記錄實(shí)際元素個(gè)數(shù)
• int modCount，記錄修改次數(shù)
• int DEFAULT_CAPACITY，數(shù)組初始化默認(rèn)分配空間為 10

可迭代接口

• Iterable 表示可迭代；
• iterator()返回一個(gè)實(shí)現(xiàn)了Iterator接口的對(duì)象

public interface Iterable {
    Iterator<T> iterator();
}

迭代器接口

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove();
}

ListIterator

擴(kuò)展了Iterator接口，增加向前遍歷，返回索引，添加元素，修改元素等

迭代中刪除元素

使用迭代器遍歷，調(diào)用迭代器的remove方法進(jìn)行刪除

必須先調(diào)用next()，使cursor指向該元素再進(jìn)行刪除

實(shí)現(xiàn)接口

ArrayList實(shí)現(xiàn)了Collection RandomAccess List

• Collection表示數(shù)據(jù)集合，數(shù)據(jù)間沒有位置或順序的概念
• RandomAccess表示可以隨機(jī)訪問
• List表示有順序或位置的數(shù)據(jù)集合

LinkedList

內(nèi)部組成

由長度、頭節(jié)點(diǎn)和尾節(jié)點(diǎn)組成雙向鏈表

節(jié)點(diǎn)

private static class Node {
    E item;
    Node prev;
    Node next;
    
    Node(Node prev, E element, Node next) {
        this.item = element;
        this.prev = prev;
        this.next = next;
    }
}

特點(diǎn)

• 按需分配內(nèi)存
• 不可以隨機(jī)訪問，按照索引訪問效率比較低，從頭或尾順著鏈表找，效率為O(N/2)
• 按照內(nèi)容查找，效率為O(N)
• 在兩端添加或刪除元素，效率為O(1)
• 在中間插入，刪除元素，需定位，效率為O(N)，修改本身效率為O(1)

實(shí)現(xiàn)接口

實(shí)現(xiàn)了List Queue Deque接口

隊(duì)列 Queue

特點(diǎn)

先進(jìn)先出

方法

add offer element peek remove poll

注意

• 隊(duì)列為空時(shí)，element和remove會(huì)拋異常，而peek和poll會(huì)返回null
• 隊(duì)列為滿時(shí)，add會(huì)拋異常，而offer會(huì)返回false

棧 Stack

特點(diǎn)

先進(jìn)后出

方法

push peek pop

注意

• 棧為空時(shí)，pop會(huì)拋異常，peek返回null
• 棧為滿時(shí)，push會(huì)拋異常

雙端隊(duì)列 Deque

特點(diǎn)

擴(kuò)展了Queue，包含棧的操作方法，額外添加其他方法

方法

addFirst addLast getFirst getLast removeFirst removeLast offerFirst offerLast peekFirst peekLast pollFirst pollLast

注意

• 隊(duì)列為空時(shí)，get和remove會(huì)拋異常，peek和poll會(huì)返回null
• 隊(duì)列為滿時(shí)，add會(huì)拋異常，offer會(huì)返回false

迭代器descendingIterator，從后往前遍歷

HashMap

鍵值對(duì)結(jié)構(gòu)，一個(gè)鍵映射一個(gè)值；鍵不能重復(fù)，即對(duì)同一個(gè)鍵重復(fù)操作會(huì)覆蓋原來的值

內(nèi)部組成

• Node<K,V>[] table，初始化為空數(shù)組
• Set<Map.Entry<K,V>> entrySet，鍵值對(duì)集合
• int size，實(shí)際鍵值對(duì)的個(gè)數(shù)
• int modCount，記錄修改次數(shù)
• int threshold，閾值，當(dāng)鍵值對(duì)個(gè)數(shù)大于該值時(shí)才進(jìn)行擴(kuò)展，threshold = table.length * loadFactor
• float loadFactor，負(fù)載因子，表示table被占用的程度，默認(rèn)為 0.75

Map.Entry

interface Entry<K, V> {
    K getKey();
    V getValue();
    V setValue(V value);
}

HashMap.Node

內(nèi)部類，HashMap的核心元素

static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;
    
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

保存鍵值對(duì)

• 如果為空數(shù)組，則初始化，默認(rèn)長度為 16
• 計(jì)算key的hash值
• 再計(jì)算其存儲(chǔ)位置
• 再判斷該位置是否有值
  • 有則判斷key是否一樣，是則修改其value并返回oldValue
  • 沒有則直接插入該鏈表頭部，返回null

HashSet

沒有重復(fù)元素，無序的集合

內(nèi)部組成

• HashMap<E,Object> map，使用map的key來存儲(chǔ)元素
• Object PRESENT，map的固定value

排序二叉樹

特點(diǎn)

• 沒有重復(fù)元素，有序
• 如果左子樹不為空，則左子樹所有節(jié)點(diǎn)都小于該節(jié)點(diǎn)
• 如果右子樹不為空，則右子樹所有節(jié)點(diǎn)都大于該節(jié)點(diǎn)

查找

• 跟根節(jié)點(diǎn)比較，相同則找到
• 小于根節(jié)點(diǎn)，則到左子樹遞歸查找
• 大于根節(jié)點(diǎn)，則到右子樹遞歸查找

最值

最左邊是最小值，最右邊是最大值

遍歷

遞歸

訪問左子樹，訪問當(dāng)前節(jié)點(diǎn)，訪問右子樹

不遞歸

先找到最左邊節(jié)點(diǎn)，然后依次找后繼節(jié)點(diǎn)

后繼節(jié)點(diǎn)查找方式

• 如果該節(jié)點(diǎn)有右孩子，則后繼節(jié)點(diǎn)為右子樹中最小的節(jié)點(diǎn)
• 如果該節(jié)點(diǎn)沒有右孩子，則后繼節(jié)點(diǎn)為父節(jié)點(diǎn)或某個(gè)祖先節(jié)點(diǎn)
  • 從當(dāng)前節(jié)點(diǎn)往上找，如果它是父節(jié)點(diǎn)的右孩子，則繼續(xù)找父節(jié)點(diǎn)
  • 直到它不是右孩子或父節(jié)點(diǎn)為空，第一個(gè)非右孩子節(jié)點(diǎn)的父節(jié)點(diǎn)就是后繼節(jié)點(diǎn)
  • 如果找不到，則后繼節(jié)點(diǎn)為空，遍歷結(jié)束

插入

• 首先查找插入位置，即插入節(jié)點(diǎn)的父節(jié)點(diǎn)，從根節(jié)點(diǎn)開始找
  • 與當(dāng)前節(jié)點(diǎn)相同，說明已存在，不能再插入
  • 小于當(dāng)前節(jié)點(diǎn)，則到左子樹查找，如果左子樹為空，則當(dāng)前節(jié)點(diǎn)為插入節(jié)點(diǎn)的父節(jié)點(diǎn)
  • 大于當(dāng)前節(jié)點(diǎn)，則到右子樹查找，如果右子樹為空，則當(dāng)前節(jié)點(diǎn)為插入節(jié)點(diǎn)的父節(jié)點(diǎn)
• 找到父節(jié)點(diǎn)后，如果插入元素小于父節(jié)點(diǎn)，則作為左孩子插入，反之作為右孩子插入

刪除

• 節(jié)點(diǎn)為葉子節(jié)點(diǎn)
  • 即沒有孩子，直接刪除，修改父節(jié)點(diǎn)的對(duì)應(yīng)孩子為空
• 節(jié)點(diǎn)只有一個(gè)孩子
  • 替換待刪節(jié)點(diǎn)為孩子節(jié)點(diǎn)
• 節(jié)點(diǎn)有兩個(gè)孩子
  • 先找到該節(jié)點(diǎn)的后繼節(jié)點(diǎn)（該節(jié)點(diǎn)為右子樹的最小節(jié)點(diǎn)，沒有左孩子），找到后，替換待刪節(jié)點(diǎn)為后繼節(jié)點(diǎn)，再刪除后繼節(jié)點(diǎn)（節(jié)點(diǎn)只有一個(gè)孩子的情況）

平衡二叉樹

節(jié)點(diǎn)分布比較均勻，即為平衡

AVL樹

• 任何節(jié)點(diǎn)的左右子樹的高度差最多為一
• 實(shí)現(xiàn)方法：在每次的插入和刪除操作時(shí)，通過一次或多次的旋轉(zhuǎn)操作來重新平衡樹

TreeMap

有序的Map

構(gòu)造方法

• 空構(gòu)造，要求Map中的鍵實(shí)現(xiàn)Comparable接口
• 帶Comparator參數(shù)的構(gòu)造，傳入一個(gè)comparator對(duì)象，TreeMap內(nèi)部會(huì)用它比較元素

內(nèi)部組成

• Comparator<? super K> comparator，沒傳則為null
• Entry<K,V> root，指向根節(jié)點(diǎn)
• int size，記錄元素個(gè)數(shù)
• int modCount，記錄修改次數(shù)

SortedMap 接口

public interface SortedMap<K,V> extends Map<K,V> {
    Comparator<? super K> comparator();
    SortedMap<K,V> subMap(K fromKey, K toKey);
    SortedMap<K,V> headMap(K toKey);
    SortedMap<K,V> tailMap(K fromKey);
    K firstKey();
    K lastKey();
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
}

NavigableMap 接口

public interface NavigableMap<K,V> extends SortedMap<K,V> {
    Map.Entry<K,V> lowerEntry(K key);
    K lowerKey(K key);
    Map.Entry<K,V> floorEntry(K key);
    K floorKey(K key);
    Map.Entry<K,V> ceilingEntry(K key);
    K ceilingKey(K key);
    Map.Entry<K,V> higherEntry(K key);
    K higherKey(K key);
    Map.Entry<K,V> firstEntry();
    Map.Entry<K,V> lastEntry();
    Map.Entry<K,V> pollFirstEntry();
    Map.Entry<K,V> pollLastEntry();
    NavigableMap<K,V> descendingMap();
    NavigableSet<K> navigableKeySet();
    NavigableSet<K> descendingKeySet();
    NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                             K toKey,   boolean toInclusive);
    NavigableMap<K,V> headMap(K toKey, boolean inclusive);
    NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
}

TreeMap.Entry

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
    
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
}

TreeSet

構(gòu)造方法

• 空構(gòu)造，要求元素實(shí)現(xiàn)Comparable接口
• 帶Comparator參數(shù)的構(gòu)造，內(nèi)部使用它比較元素

內(nèi)部組成

• NavigableMap<E,Object> m，同HashSet，使用map的key存儲(chǔ)元素
• Object PRESENT，同HashSet，固定的value

內(nèi)部操作

都是調(diào)用內(nèi)部變量m的對(duì)應(yīng)方法

堆

概念上是完全二叉樹，使用數(shù)組進(jìn)行物理存儲(chǔ)

滿二叉樹

除最后一層外，每個(gè)節(jié)點(diǎn)都有兩個(gè)孩子，最后一層都是葉子節(jié)點(diǎn)，沒有孩子

完全二叉樹

不要求最后一層是滿的，但如果不滿，要求所有節(jié)點(diǎn)必須集中在最左邊，從左到右是連續(xù)的，中間不能有空的

特點(diǎn)：在完全二叉樹中，可以給每個(gè)節(jié)點(diǎn)一個(gè)編號(hào)，編號(hào)從1開始遞增，從上到下，從左到右；當(dāng)給定任意一個(gè)節(jié)點(diǎn)的編號(hào)，可以快速計(jì)算出其父節(jié)點(diǎn)和孩子節(jié)點(diǎn)編號(hào)

這個(gè)特點(diǎn)使得邏輯概念上的二叉樹可以方便的存儲(chǔ)到數(shù)組中

最大堆 最小堆

與排序二叉樹不同，在堆中，可以有重復(fù)元素，元素間不是完全有序的，父子節(jié)點(diǎn)之間有一定的順序要求

算法（最小堆）

添加元素

log2(N) siftup

• 添加元素到最后位置
• 與父節(jié)點(diǎn)比較，如果大于等于父節(jié)點(diǎn)，則滿足堆的性質(zhì)，結(jié)束
• 否則與父節(jié)點(diǎn)交換，再與父節(jié)點(diǎn)比較，直到父節(jié)點(diǎn)為空或大于等于父節(jié)點(diǎn)

從頭部刪除元素

log2(N) siftdown

• 用最后一個(gè)元素替換頭部元素，并刪除最后一個(gè)元素
• 將新的頭部元素與倆孩子節(jié)點(diǎn)中較小的的比較，如果不大于該孩子節(jié)點(diǎn)，則滿足堆的性質(zhì)，結(jié)束
• 否則與該孩子節(jié)點(diǎn)交換，再與較小的孩子節(jié)點(diǎn)比較，直到?jīng)]有孩子或者不大于兩個(gè)孩子

從中間刪除元素

• 還是用最后一個(gè)元素替換頭部元素，并刪除最后一個(gè)元素
• 然后判斷，如果該元素大于某個(gè)孩子節(jié)點(diǎn)，則需向下調(diào)整，如果小于父節(jié)點(diǎn)，則需向上調(diào)整

構(gòu)建初始堆

O(N) heapify

• 從最后一個(gè)非葉子節(jié)點(diǎn)開始，一直往前直到根，對(duì)每個(gè)節(jié)點(diǎn)，執(zhí)行向下調(diào)整

查找和遍歷

O(N)

• 就是數(shù)組的查找和遍歷

PriorityQueue

有優(yōu)先級(jí)的隊(duì)列

特點(diǎn)

• 長度沒有限制，默認(rèn)為 11
• 元素有優(yōu)先級(jí)，隊(duì)頭的元素永遠(yuǎn)是優(yōu)先級(jí)最高的
• 內(nèi)部元素不是完全有序的，逐個(gè)出隊(duì)會(huì)得到有序的輸出
• 與TreeMap TreeSet類似，要么元素實(shí)現(xiàn)Comparable接口，要么傳入一個(gè)Comparator比較器

內(nèi)部組成

• Object[] queue，存儲(chǔ)元素的數(shù)組
• int size，記錄元素個(gè)數(shù)
• Comparator<? super E> comparator，比較器
• int modCount，記錄修改次數(shù)

ArrayDeque

使用數(shù)組存儲(chǔ)的雙端隊(duì)列

內(nèi)部組成

• Object[] elements，存儲(chǔ)元素的數(shù)組
• int head，頭部元素索引
• int tail，尾部元素索引

循環(huán)數(shù)組

• 如果head和tail相同，則數(shù)組為空，長度為 0
• 如果tail大于head，則第一個(gè)元素為elements[head]，最后一個(gè)元素為elements[tail - 1]，長度為tail - head，元素索引從head到tail - 1
• 如果tail小于head，且為 0 ，則第一個(gè)元素為elements[head]，最后一個(gè)元素為elements[elements.length - 1]，元素索引從head到elements.length - 1
• 如果tail小于head，且大于 0 ，則會(huì)形成循環(huán)，第一個(gè)元素為elements[head]，最后一個(gè)元素為elements[tail - 1]，元素索引從head到elements.length - 1，然后再從0到tail - 1

內(nèi)部實(shí)現(xiàn)

• 數(shù)組的長度要嚴(yán)格大于實(shí)際存儲(chǔ)元素的個(gè)數(shù)，為了讓head或tail指向下一個(gè)空位
• 數(shù)組長度為 2 的冪次方，方便計(jì)算
• 計(jì)算方式
  • 下一個(gè)位置：(tail + 1) & (elements.length - 1)
  • 上一個(gè)位置：(head - 1) & (elements.length - 1)

LinkedHashMap

特點(diǎn)

支持兩種順序：插入順序和訪問順序

內(nèi)部組成

• LinkedHashMap.Entry<K,V> head，雙向鏈表的頭
• LinkedHashMap.Entry<K,V> tail，雙向鏈表的尾
• boolean accessOrder，是否按訪問順序的標(biāo)志

LinkedHashMap.Entry

• before：前一個(gè)節(jié)點(diǎn)
• after：后一個(gè)節(jié)點(diǎ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);
    }
}

訪問順序

訪問指get put操作，對(duì)一個(gè)鍵執(zhí)行get put操作后，其對(duì)應(yīng)的鍵值對(duì)會(huì)移到鏈表末尾

構(gòu)造方法

只有一個(gè)構(gòu)造方法可以指定按訪問順序

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

用途

用于實(shí)現(xiàn)緩存，比如 LRU緩存

如果緩存滿了，當(dāng)需要存儲(chǔ)新數(shù)據(jù)時(shí)，就需要一定的策略將一些老的數(shù)據(jù)清理，這個(gè)策略稱為 替換算法

EnumMap

內(nèi)部組成

• Class<K> keyType，key的類型
• K[] keyUniverse，存儲(chǔ)所有key
• Object[] vals，存儲(chǔ)所有的value
• int size，記錄元素個(gè)數(shù)

實(shí)現(xiàn)原理

內(nèi)部維護(hù)兩個(gè)數(shù)組，長度相等，一個(gè)表示所有的鍵，一個(gè)表示對(duì)應(yīng)的值，值為null表示沒有該鍵值對(duì)，鍵都有一個(gè)對(duì)應(yīng)的索引ordinal，根據(jù)索引可以很方便訪問鍵和值

EnumSet

抽象類，如果枚舉個(gè)數(shù)小于 64 ，則靜態(tài)工廠方法創(chuàng)建的就是 RegularEnumSet，大于則是JumboEnumSet

內(nèi)部組成

• Class<E> elementType，元素類型
• Enum<?>[] universe，存儲(chǔ)所有枚舉值

RegularEnumSet

元素個(gè)數(shù)在 64 以內(nèi)的集合

• long elements，位向量，使用一個(gè)long類型的變量存儲(chǔ)所有元素
• int size()，返回元素個(gè)數(shù)，方法實(shí)現(xiàn)：Long.bitCount(elements);

用一個(gè)位表示一個(gè)元素的狀態(tài)，用一組位表示一個(gè)集合的狀態(tài)，每個(gè)位對(duì)應(yīng)一個(gè)元素，而狀態(tài)只可能有兩種

JumboEnumSet

元素個(gè)數(shù)在 64 以上的集合

• long elements[]，使用long數(shù)組存儲(chǔ)所有元素
• int size，記錄元素個(gè)數(shù)

內(nèi)部操作

• 都是利用位運(yùn)算來實(shí)現(xiàn)的
• 根據(jù)枚舉值找到索引，對(duì)對(duì)應(yīng)的位進(jìn)行 位或 ，位與 ，取反 操作

容器類

接口

• Collection
• List
• Map
• Set
• Queue
• Deque

抽象類

• AbstractCollection
• AbstractList
• AbstractMap
• AbstractSet
• AbstractQueue
• AbstractSequentialList

AbstractList 與 AbstractSequentialList 對(duì)比

• AbstractList需要具體子類重寫根據(jù)索引操作的方法get set add remove，它提供了迭代器，但迭代器是基于這些方法實(shí)現(xiàn)的；它假定子類可以高效的根據(jù)索引位置進(jìn)行操作，適用于內(nèi)部是隨機(jī)訪問類型的存儲(chǔ)結(jié)構(gòu)（如數(shù)組），比如ArrayList就繼承自AbstractList
• AbstractSequentialList需要具體子類重寫迭代器，它提供了根據(jù)索引操作的方法get set add remove，但這些方法是基于迭代器實(shí)現(xiàn)的；它適用于內(nèi)部是順序訪問類型的存儲(chǔ)結(jié)構(gòu)（如鏈表），比如LinkedList就繼承自AbstractSequentialList

操作

查找

• 利用迭代器遍歷進(jìn)行查找

二分查找

• 要求List的每個(gè)元素實(shí)現(xiàn)Comparable接口或提供一個(gè)Comparator
• 如果List可以隨機(jī)訪問，即實(shí)現(xiàn)RandomAccess接口，或者元素個(gè)數(shù)比較少，則直接使用索引訪問中間元素進(jìn)行查找；否則使用迭代器的方式訪問中間元素進(jìn)行查找

查找元素出現(xiàn)個(gè)數(shù)

• frequency方法

查看兩個(gè)集合是否有交集

• disjoint方法

排序

• 先將List元素拷貝到一個(gè)數(shù)組中，然后使用Arrays.sort方法，排序后，再拷貝回List

交換元素位置

• list.set(i, list.set(j, list.get(i)))

翻轉(zhuǎn)列表順序

• 如果List可以隨機(jī)訪問，將第一個(gè)和最后一個(gè)交換，第二個(gè)和倒數(shù)第二個(gè)交換，依此類推，直到中間兩個(gè)元素交換完畢；否則，使用一前一后兩個(gè)listIterator定位待交換的元素

隨機(jī)化重排

• 如果List可以隨機(jī)訪問，從后往前遍歷列表，逐個(gè)給每個(gè)位置重新賦值，值從前面未重新賦值的元素中隨機(jī)選?。环駝t，先將List拷貝到一個(gè)數(shù)組中，重排后再拷貝回List

循環(huán)移位

• 使用rotate(list, distance)方法
• distance：正數(shù)表示右移，負(fù)數(shù)表示左移
• 可以看作列表的兩個(gè)子列表進(jìn)行順序交換
• 根據(jù)列表長度和移位個(gè)數(shù)，計(jì)算出兩個(gè)子列表的分割點(diǎn)，然后通過三次翻轉(zhuǎn)得到最終結(jié)果