前言

這次算一個總結，我們平時都會用到各種各樣的數據結構，但是可能從未看過它們內部是如何去實現的。只有了解了它們內部大概的一個實現原理，才能在不同的場景中能選出最適合這個場景的數據結構。

雖然標題說是Android，但其實有一半是屬于java的，由于涉及得比較多，所以打算分篇來寫會比較好，我不會把全部的源碼都進行分析，主要做的是分析一些能表現這些數據結構的特征。

Collection

一切數據結構的最頂層，是一個接口，繼承迭代器Iterable，主要是定義所有數據結構的公共行為，比如說boolean contains(Object o)方法，可能在hashmap用得多，很多人都覺得這個是hashmap才有的方法，其實它是在Collection中定義的，不同的數據結構可以去重寫。

AbstractCollection是它的抽象實現類，里面有實現一些基本的行為，還是拿contains方法來說

public boolean contains(Object o) {
    Iterator<E> it = iterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return true;
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return true;
    }
    return false;
}

其實就是遍歷和判斷，其它的方法也差不多，都比較簡單，就不多說了。

Set和List

這兩個也都是接口，抽象的實現分別是AbstractSet和AbstractList。最簡單來說，它們兩個的區(qū)別就在于是否有重復元素，和“宏觀”上的有序和無序（因為TreeSet紅黑樹是有序的，所以不能說全部Set都是無序），舉個例子，比如說equest方法，兩邊的實現就不同。

先看AbstractSet的

public boolean equals(Object o) {
    ......
    Collection<?> c = (Collection<?>) o;
    if (c.size() != size())
        return false;
    try {
        return containsAll(c);
    } catch (ClassCastException unused)   {
        return false;
    } catch (NullPointerException unused) {
        return false;
    }
}

可以看到，它其實內部是只要判斷到傳進來的Set內部的所有元素都能在這個Set中找到一樣的就行（包含）。再看看AbstractList

public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof List))
        return false;
    ListIterator<E> e1 = listIterator();
    ListIterator<?> e2 = ((List<?>) o).listIterator();
    while (e1.hasNext() && e2.hasNext()) {
        E o1 = e1.next();
        Object o2 = e2.next();
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }
    return !(e1.hasNext() || e2.hasNext());
}

看得出其實它是作了一個迭代，然后一個一個元素去判斷是否相同。光看這兩個方法你就知道Set的equest方法只要判斷有包含就行，不會在意順序，而List需要元素的順序相同。

其他的方法也是，存在一些差異，所以很多人會和你總結Set和List的區(qū)別，但是只有當你去了解它的內部實現，你才能更好的感受到這區(qū)別是什么。

Queue和Deque

有點基礎我們都知道數據結構有棧和隊列，一個是后進先出，一個是先進先出。而Queue就是隊列，它是一個接口，定義了入隊列出隊列這些方法。而Deque是一個雙向隊列，java 這里是可以使用雙向隊列來實現棧的效果，Deque也是一個接口繼承Queue。

這里的內容肯能會有點無聊，但是是比較重要的基礎內容。隊列定義的Queue方法有入隊列的方法add和offer，出隊列的方法remove和poll，還有拿隊列頭的方法element和peek。

可以看到它的操作是有2組，它們的差別是：

• add() ： 無返回值
• offer()： 有返回值
• remove()：移除失敗拋出異常
• poll()：移除失敗返回null
• element()：隊列為空拋出異常
• peek()：隊列為空返回null

所以如果你不了解這些，你只會無腦add，這樣就很不好。但其實對于LinkedList來說add()和offer()區(qū)別不大?？赡軈^(qū)別比較大的地方在你自定義數據結果實現Queue和Deque的時候該怎么處理這兩個方法。

說完Queue再簡單介紹一下Deque，Deque因為是雙向隊列，所以它能實現棧和隊列。

• 隊列：入隊列offer；出隊列poll；獲取隊列頭peek
• 棧：入棧push；出棧pop；獲取棧頂peel

Map

Mao是另一種數據結構，它獨立于Collection，它的是一個接口，它的抽象實現是AbstractMap，它內部是會通過Set來實現迭代器

Set<Map.Entry<K, V>> entrySet();

是和Set有關聯的，思想上主要以key-value的形式存儲數據，但是具體的實現會交給子類去實現。

上層的數據結構大概就這些，接下來會介紹一些常用的實現類。

ArrayList

我們常用的ArrayList來實現列表，它內部其實就是一個對象數組

// Android-note: Also accessed from java.util.Collections
transient Object[] elementData; // non-private to simplify nested class access

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

添加元素的時候主要就是擴容和添加元素到數組的指定位置

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

數組為空的時候第一次會初始化10的容量

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    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);
}

然后之后的擴容是舊的容量加舊的容量右移一位，其實就是擴容當前容量的一半（舊版本也是這樣嗎？不記得了），擴容后會復制當前數組的元素到新的數組中。再看看add到指定位置的操作

public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

能看到也有一個System.arraycopy復制數組的操作。所以ArrayList的劣勢就體現在這里，復制數組是耗時的操作，頻繁的進行復制數組會得不償失。

懂得他里面的這些實現的話我們就可以在使用的時候進行優(yōu)化，比如使用的時候初始化定好數組的大小，防止頻繁擴容。比如插入、刪除這些操作更多的話，我們可以選擇使用其它更合適的數據結構。

LinkedList

這東西就厲害了，用得少你會叫它鏈表，其實它是雙向鏈表，實現我們上面的Deque，能實現的功能挺龐大的。

既然實現Deque，那它就有offer、poll、peek、push、pop、peel這些操作。不會吧不會吧，不會只有人用它的add方法吧。

內部兩個結點表示鏈表頭和鏈表尾（鏈表在代碼中的體現就是結點，比如MessageQueue的Message）

transient Node<E> first;
transient Node<E> last;

功能非常龐大，非常建議沒看過源碼的人去熟悉一下，因為比較多，我這里就只舉幾個例子?？纯次覀兂Ｓ玫腶dd方法

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

Node<E> node(int index) {
    // assert isElementIndex(index);
    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;
    }
}

它這里就先做了一步優(yōu)化處理，查找結點的時候根據下標去決定從頭開始查找還是從尾開始查找，看著覺得這操作也沒啥好厲害的，我只想說看別人的和自己想的是兩碼事。

public boolean offer(E e) {
    return add(e);
}

offer其實是調用了add，上面也有說LinkedList的這兩個操作一樣，但是接口定義的這兩個操作的含義是不同的?？梢钥纯吹讲迦氩僮髦皇亲隽斯?jié)點指針的變化，不會像ArrayList一樣每次插入到中間位置都需要數組位置移動。

Vector

Vector就更簡單了，內部也是一個Object數組Object[] elementData，可以看看它的add方法

    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

看得出出ArrayList的操作一樣，只不過加了個synchronized，所以它是線程安全的。

Stack

Stack繼承Vector，所以它的操作也是線程安全的?？梢钥纯此膒ush方法

public E push(E item) {
    addElement(item);
    return item;
}

    public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }

從這里可以看出，按照棧的思想是后進先出，而它這里是把數組的最后的位置當成棧頂，相應的pop就是拿數組的最后一個元素，然后再移除。而我們用LinkedList實現的棧的效果，是把頭當成棧頂（再回顧一下）

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

他們都實現棧的數據結構，但是是用不同的方法去實現的。

ArraySet

這個東西可能平時我們開發(fā)用得比較少，但是如果你看源碼比較多的話，你會發(fā)現android有些地方也是會用到ArraySet或者ArrayMap，Map我打算下篇文章寫，這里可以提前說一下，ArraySet我們可以拿去和后面的ArrayMap做比較，他們的實現其實是一樣的。

內部是兩個數組，一個用來存對象，一個用來存對象的hash

    int[] mHashes;
    Object[] mArray;

我們可以從add方法中具體去看出它的設計思想

public boolean add(E value) {
    final int oSize = mSize;
    final int hash; 
    int index;
    if (value == null) {
        hash = 0;
        index = indexOfNull();
    } else {
        // 根據Object生成它對應的hash
        hash = mIdentityHashCode ? System.identityHashCode(value) : value.hashCode();
        index = indexOf(value, hash);
    }
    index = ~index; // indexOf里面會取反，這里要轉回來
    ......
    mHashes[index] = hash;
    mArray[index] = value;
    mSize++;
    return true;
}

我把簡單的步驟寫出來，就是根據object去計算它的hash，然后再根據hash去計算數組的下標index，把object和hash分別存到對應數組的對應位置，所以這兩個數組的元素是對應的。indexOf里面主要的操作是int index = binarySearch(mHashes, hash)，它其實就是一個二分查找的操作，代碼比較簡單，這里就不擴展說了。

HashSet

HashSet的內部實現是HashMap

private transient HashMap<E,Object> map;

它把值作為HashMap的key，而HashMap的values是用一個Object常量。

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

所以它這里就體現出Set的一個特征，沒有重復元素。

TreeSet

TreeSet內部的數據結構是TreeMap

public TreeSet() {
    this(new TreeMap<>());
}

和TreeMap不同的是，它和HashSet一樣，用傳進來的Object當key，用Object常量當values

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

Set小結

Set的數據結構當然還有其它，比如LinkedHashSet這些。但是比較有代表性的就是這3個，其中Set和Map其實是有一定的聯系，我們上面講Map的時候說，它內部是持有Set，而ArraySet和ArrayMap的數據結構一樣，都是雙數組，HashSet內部的實現是HashMap，TreeSet的內部實現是TreeMap。他們的不同在于Set把傳進來的value當成key，而Map是會傳key和value獨立開（下篇會講）。

ArraySet、HashSet、TreeMap看著沒有關聯，其實是有一定的聯系，沒錯，就是hash，它們都會去計算hash，所以這就是沒有重復元素的原因，因為相同的對象，它們的hash是相同的。

上面講了比較經典的List和Set的數據結構，接下來會講幾個比較特殊的數據結構。

SparseArray

這個數據結構可能很多人沒見過，它是屬于Android的，上面我們說的那些都是java的。

他的內部也是兩個數組構成。

private int[] mKeys;
private Object[] mValues;

但它和ArraySet不同，它是傳兩個值

public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    if (i >= 0) {
        mValues[i] = value;
    } else {
        ......
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

看到它也用了binarySearch，但是它是根據key去做二分查找，而ArraySet是根據hash去做二分查找找到下標。那他們誰快？ 當然是SparseArray，它少了一步操作，它不需要計算hash。所以能看出它是傳一個整形來表示key，那既然是key-value的形式，那又可以去和HashMap比較有什么不同了。其實都能很明顯的看出HashMap的key是Object，會去計算hash，它的key是直接傳盡量的整形。HashMap的查找是根據Key去計算hash，再去計算下標，最后可能變量鏈表（紅黑樹），而SparseArray是通過二分查找。 從理論上來說，它的速度比HashMap快，特別是數據量大的情況下能體現出來。

還有一個特征是它有一系列的兄弟結果，比如SparseBooleanArray、SparseIntArray之類的，他們和SparseArray的結構一樣，比如SparseIntArray

private int[] mKeys;
private int[] mValues;

不同在于他們的mValues都是基礎數據類型數組，這有什么用？ 這還真有用，如果你存的是基礎數據類型的話，使用這些數據結構，就能省去裝箱的操作。

PriorityQueue

這個東西也用得比較少，它表示優(yōu)先隊列，內部也是一個object數組

transient Object[] queue

什么是優(yōu)先隊列，簡單來說，有種結構叫最大堆，最小堆。有種排序叫堆排序。他能實現這個效果，它的內部是用堆排序去實現，它能自定義排序的條件。比如它默認實現最小堆，如果你要實現最大堆的話，可以寫

PriorityQueue<T> heap = new PriorityQueue<>(Collenctions.reverseOrder())

因為是隊列，所以它實現Queue的那些操作，比如offer

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

siftUp是個堆排的操作，這里就不詳細去說了，感興趣官方的堆排是怎么實現的，可以去看看源碼，但它也不是純堆排的操作，會有些許不同。

總結

這篇主要講了一些java中頂層的數據結構，包括Collection、Queue和Deque，這些頂層的結構主要是定義一些行為，他們還有自己的抽象實現類。

除了這些，還講了List和Set里面一些比較經典的數據結構，他們的內部是如何實現的，他們有什么相同點和不同點，他們是如何體現出接口List或Set的特點的。

除了List或Set之外，還講了一些比較常用的數據結構，包含SparseArray和PriorityQueue，主要是我比較常用，如果有大佬還會用到什么其它的，覺得比較實用的，也可以在評論留言。

之后的文章會分開講Map和線程安全的數據結構，Concurrent、同步隊列和CopyOnWriteArrayList。而Map中的HashMap比較經典所以會花更多的筆墨去寫。這些文章我都是主要講一些特點為主，不會去完全解析各種數據結構，比如LinkedList，它的實現就很多，如果去講的話就要花費大篇幅，而且它們內部的源碼不復雜，所以我認為沒必要去詳細的講解，感興趣的可以去看源碼還比看文章快，主要就是講這些結構的設計和一些體現出它們特點的操作。

以上就是Android 數據結構全面總結分析的詳細內容，更多關于Android數據結構的資料請關注腳本之家其它相關文章！