前言

這次算一個(gè)總結(jié)，我們平時(shí)都會(huì)用到各種各樣的數(shù)據(jù)結(jié)構(gòu)，但是可能從未看過它們內(nèi)部是如何去實(shí)現(xiàn)的。只有了解了它們內(nèi)部大概的一個(gè)實(shí)現(xiàn)原理，才能在不同的場景中能選出最適合這個(gè)場景的數(shù)據(jù)結(jié)構(gòu)。

雖然標(biāo)題說是Android，但其實(shí)有一半是屬于java的，由于涉及得比較多，所以打算分篇來寫會(huì)比較好，我不會(huì)把全部的源碼都進(jìn)行分析，主要做的是分析一些能表現(xiàn)這些數(shù)據(jù)結(jié)構(gòu)的特征。

Collection

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

AbstractCollection是它的抽象實(shí)現(xiàn)類，里面有實(shí)現(xiàn)一些基本的行為，還是拿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;
}

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

Set和List

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

先看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;
    }
}

可以看到，它其實(shí)內(nèi)部是只要判斷到傳進(jìn)來的Set內(nèi)部的所有元素都能在這個(gè)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());
}

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

其他的方法也是，存在一些差異，所以很多人會(huì)和你總結(jié)Set和List的區(qū)別，但是只有當(dāng)你去了解它的內(nèi)部實(shí)現(xiàn)，你才能更好的感受到這區(qū)別是什么。

Queue和Deque

有點(diǎn)基礎(chǔ)我們都知道數(shù)據(jù)結(jié)構(gòu)有棧和隊(duì)列，一個(gè)是后進(jìn)先出，一個(gè)是先進(jìn)先出。而Queue就是隊(duì)列，它是一個(gè)接口，定義了入隊(duì)列出隊(duì)列這些方法。而Deque是一個(gè)雙向隊(duì)列，java 這里是可以使用雙向隊(duì)列來實(shí)現(xiàn)棧的效果，Deque也是一個(gè)接口繼承Queue。

這里的內(nèi)容肯能會(huì)有點(diǎn)無聊，但是是比較重要的基礎(chǔ)內(nèi)容。隊(duì)列定義的Queue方法有入隊(duì)列的方法add和offer，出隊(duì)列的方法remove和poll，還有拿隊(duì)列頭的方法element和peek。

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

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

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

說完Queue再簡單介紹一下Deque，Deque因?yàn)槭请p向隊(duì)列，所以它能實(shí)現(xiàn)棧和隊(duì)列。

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

Map

Mao是另一種數(shù)據(jù)結(jié)構(gòu)，它獨(dú)立于Collection，它的是一個(gè)接口，它的抽象實(shí)現(xiàn)是AbstractMap，它內(nèi)部是會(huì)通過Set來實(shí)現(xiàn)迭代器

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

是和Set有關(guān)聯(lián)的，思想上主要以key-value的形式存儲(chǔ)數(shù)據(jù)，但是具體的實(shí)現(xiàn)會(huì)交給子類去實(shí)現(xiàn)。

上層的數(shù)據(jù)結(jié)構(gòu)大概就這些，接下來會(huì)介紹一些常用的實(shí)現(xiàn)類。

ArrayList

我們常用的ArrayList來實(shí)現(xiàn)列表，它內(nèi)部其實(shí)就是一個(gè)對(duì)象數(shù)組

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

添加元素的時(shí)候主要就是擴(kuò)容和添加元素到數(shù)組的指定位置

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

數(shù)組為空的時(shí)候第一次會(huì)初始化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);
}

然后之后的擴(kuò)容是舊的容量加舊的容量右移一位，其實(shí)就是擴(kuò)容當(dāng)前容量的一半（舊版本也是這樣嗎？不記得了），擴(kuò)容后會(huì)復(fù)制當(dāng)前數(shù)組的元素到新的數(shù)組中。再看看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++;
}

能看到也有一個(gè)System.arraycopy復(fù)制數(shù)組的操作。所以ArrayList的劣勢就體現(xiàn)在這里，復(fù)制數(shù)組是耗時(shí)的操作，頻繁的進(jìn)行復(fù)制數(shù)組會(huì)得不償失。

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

LinkedList

這東西就厲害了，用得少你會(huì)叫它鏈表，其實(shí)它是雙向鏈表，實(shí)現(xiàn)我們上面的Deque，能實(shí)現(xiàn)的功能挺龐大的。

既然實(shí)現(xiàn)Deque，那它就有offer、poll、peek、push、pop、peel這些操作。不會(huì)吧不會(huì)吧，不會(huì)只有人用它的add方法吧。

內(nèi)部兩個(gè)結(jié)點(diǎn)表示鏈表頭和鏈表尾（鏈表在代碼中的體現(xiàn)就是結(jié)點(diǎn)，比如MessageQueue的Message）

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

功能非常龐大，非常建議沒看過源碼的人去熟悉一下，因?yàn)楸容^多，我這里就只舉幾個(gè)例子。看看我們常用的add方法

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)化處理，查找結(jié)點(diǎn)的時(shí)候根據(jù)下標(biāo)去決定從頭開始查找還是從尾開始查找，看著覺得這操作也沒啥好厲害的，我只想說看別人的和自己想的是兩碼事。

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

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

Vector

Vector就更簡單了，內(nèi)部也是一個(gè)Object數(shù)組Object[] elementData，可以看看它的add方法

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

看得出出ArrayList的操作一樣，只不過加了個(gè)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;
    }

從這里可以看出，按照棧的思想是后進(jìn)先出，而它這里是把數(shù)組的最后的位置當(dāng)成棧頂，相應(yīng)的pop就是拿數(shù)組的最后一個(gè)元素，然后再移除。而我們用LinkedList實(shí)現(xiàn)的棧的效果，是把頭當(dāng)成棧頂（再回顧一下）

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

他們都實(shí)現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)，但是是用不同的方法去實(shí)現(xiàn)的。

ArraySet

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

內(nèi)部是兩個(gè)數(shù)組，一個(gè)用來存對(duì)象，一個(gè)用來存對(duì)象的hash

    int[] mHashes;
    Object[] mArray;

我們可以從add方法中具體去看出它的設(shè)計(jì)思想

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

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

HashSet

HashSet的內(nèi)部實(shí)現(xiàn)是HashMap

private transient HashMap<E,Object> map;

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

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

所以它這里就體現(xiàn)出Set的一個(gè)特征，沒有重復(fù)元素。

TreeSet

TreeSet內(nèi)部的數(shù)據(jù)結(jié)構(gòu)是TreeMap

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

和TreeMap不同的是，它和HashSet一樣，用傳進(jìn)來的Object當(dāng)key，用Object常量當(dāng)values

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

Set小結(jié)

Set的數(shù)據(jù)結(jié)構(gòu)當(dāng)然還有其它，比如LinkedHashSet這些。但是比較有代表性的就是這3個(gè)，其中Set和Map其實(shí)是有一定的聯(lián)系，我們上面講Map的時(shí)候說，它內(nèi)部是持有Set，而ArraySet和ArrayMap的數(shù)據(jù)結(jié)構(gòu)一樣，都是雙數(shù)組，HashSet內(nèi)部的實(shí)現(xiàn)是HashMap，TreeSet的內(nèi)部實(shí)現(xiàn)是TreeMap。他們的不同在于Set把傳進(jìn)來的value當(dāng)成key，而Map是會(huì)傳key和value獨(dú)立開（下篇會(huì)講）。

ArraySet、HashSet、TreeMap看著沒有關(guān)聯(lián)，其實(shí)是有一定的聯(lián)系，沒錯(cuò)，就是hash，它們都會(huì)去計(jì)算hash，所以這就是沒有重復(fù)元素的原因，因?yàn)橄嗤膶?duì)象，它們的hash是相同的。

上面講了比較經(jīng)典的List和Set的數(shù)據(jù)結(jié)構(gòu)，接下來會(huì)講幾個(gè)比較特殊的數(shù)據(jù)結(jié)構(gòu)。

SparseArray

這個(gè)數(shù)據(jù)結(jié)構(gòu)可能很多人沒見過，它是屬于Android的，上面我們說的那些都是java的。

他的內(nèi)部也是兩個(gè)數(shù)組構(gòu)成。

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

但它和ArraySet不同，它是傳兩個(gè)值

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，但是它是根據(jù)key去做二分查找，而ArraySet是根據(jù)hash去做二分查找找到下標(biāo)。那他們誰快？ 當(dāng)然是SparseArray，它少了一步操作，它不需要計(jì)算hash。所以能看出它是傳一個(gè)整形來表示key，那既然是key-value的形式，那又可以去和HashMap比較有什么不同了。其實(shí)都能很明顯的看出HashMap的key是Object，會(huì)去計(jì)算hash，它的key是直接傳盡量的整形。HashMap的查找是根據(jù)Key去計(jì)算hash，再去計(jì)算下標(biāo)，最后可能變量鏈表（紅黑樹），而SparseArray是通過二分查找。 從理論上來說，它的速度比HashMap快，特別是數(shù)據(jù)量大的情況下能體現(xiàn)出來。

還有一個(gè)特征是它有一系列的兄弟結(jié)果，比如SparseBooleanArray、SparseIntArray之類的，他們和SparseArray的結(jié)構(gòu)一樣，比如SparseIntArray

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

不同在于他們的mValues都是基礎(chǔ)數(shù)據(jù)類型數(shù)組，這有什么用？ 這還真有用，如果你存的是基礎(chǔ)數(shù)據(jù)類型的話，使用這些數(shù)據(jù)結(jié)構(gòu)，就能省去裝箱的操作。

PriorityQueue

這個(gè)東西也用得比較少，它表示優(yōu)先隊(duì)列，內(nèi)部也是一個(gè)object數(shù)組

transient Object[] queue

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

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

因?yàn)槭顷?duì)列，所以它實(shí)現(xiàn)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是個(gè)堆排的操作，這里就不詳細(xì)去說了，感興趣官方的堆排是怎么實(shí)現(xiàn)的，可以去看看源碼，但它也不是純堆排的操作，會(huì)有些許不同。

總結(jié)

這篇主要講了一些java中頂層的數(shù)據(jù)結(jié)構(gòu)，包括Collection、Queue和Deque，這些頂層的結(jié)構(gòu)主要是定義一些行為，他們還有自己的抽象實(shí)現(xiàn)類。

除了這些，還講了List和Set里面一些比較經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，他們的內(nèi)部是如何實(shí)現(xiàn)的，他們有什么相同點(diǎn)和不同點(diǎn)，他們是如何體現(xiàn)出接口List或Set的特點(diǎn)的。

除了List或Set之外，還講了一些比較常用的數(shù)據(jù)結(jié)構(gòu)，包含SparseArray和PriorityQueue，主要是我比較常用，如果有大佬還會(huì)用到什么其它的，覺得比較實(shí)用的，也可以在評(píng)論留言。

之后的文章會(huì)分開講Map和線程安全的數(shù)據(jù)結(jié)構(gòu)，Concurrent、同步隊(duì)列和CopyOnWriteArrayList。而Map中的HashMap比較經(jīng)典所以會(huì)花更多的筆墨去寫。這些文章我都是主要講一些特點(diǎn)為主，不會(huì)去完全解析各種數(shù)據(jù)結(jié)構(gòu)，比如LinkedList，它的實(shí)現(xiàn)就很多，如果去講的話就要花費(fèi)大篇幅，而且它們內(nèi)部的源碼不復(fù)雜，所以我認(rèn)為沒必要去詳細(xì)的講解，感興趣的可以去看源碼還比看文章快，主要就是講這些結(jié)構(gòu)的設(shè)計(jì)和一些體現(xiàn)出它們特點(diǎn)的操作。

以上就是Android 數(shù)據(jù)結(jié)構(gòu)全面總結(jié)分析的詳細(xì)內(nèi)容，更多關(guān)于Android數(shù)據(jù)結(jié)構(gòu)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論