ArrayMap是Android提供的一種替換HashMap的數(shù)據(jù)結構，官方對它的介紹說ArrayMap是一種更有效率的Map結構，其原理是內部維護了兩個數(shù)組，一個數(shù)組用來保存每一個key值得hash值，另一個數(shù)組用來保存key-value, 用來保存key-value的數(shù)組是保存hash值數(shù)組大小的兩倍，下面這張圖很好的展示了ArrayMap原理:

ArrayMap.png

成員變量

    private static final int BASE_SIZE = 4;

    private static final int CACHE_SIZE = 10;

    static final int[] EMPTY_IMMUTABLE_INTS = new int[0];

    public static final ArrayMap EMPTY = new ArrayMap<>(-1);

    //緩存相關
    static Object[] mBaseCache;
    static int mBaseCacheSize;
    static Object[] mTwiceBaseCache;
    static int mTwiceBaseCacheSize;

    final boolean mIdentityHashCode;
    int[] mHashes;
    Object[] mArray;
    int mSize;
    //集合操作工具類
    MapCollections<K, V> mCollections;

mHashes用來存放key值相對應的hash值
mArray用來存放key-value, key值在2n處， value在2n+1處
ArrayMap還加入了緩存，mBaseCache用來緩存容量為BASE_SIZE的數(shù)組，mTwiceBaseCache用來緩存容量為2 * BASE_SIZE的數(shù)組

構造函數(shù)

    public ArrayMap() {
        this(0, false);
    }


    public ArrayMap(int capacity) {
        this(capacity, false);
    }

    /** {@hide} */
    public ArrayMap(int capacity, boolean identityHashCode) {
        mIdentityHashCode = identityHashCode;

        if (capacity < 0) {
            mHashes = EMPTY_IMMUTABLE_INTS;
            mArray = EmptyArray.OBJECT;
        } else if (capacity == 0) {
            mHashes = EmptyArray.INT;
            mArray = EmptyArray.OBJECT;
        } else {
            allocArrays(capacity);
        }
        mSize = 0;
    }

    public ArrayMap(ArrayMap<K, V> map) {
        this();
        if (map != null) {
            putAll(map);
        }
    }

一般情況下，在開發(fā)中我們主要使用空參構造函數(shù)和一個參數(shù)的構造函數(shù)，不過這兩個構造函數(shù)都是調用了第三個hide的構造函數(shù), 這個構造函數(shù)中主要工作就是分配數(shù)組

allocArrays

private void allocArrays(final int size) {
        if (mHashes == EMPTY_IMMUTABLE_INTS) {
            throw new UnsupportedOperationException("ArrayMap is immutable");
        }
        if (size == (BASE_SIZE*2)) {
            synchronized (ArrayMap.class) {
                if (mTwiceBaseCache != null) {
                    final Object[] array = mTwiceBaseCache;
                    mArray = array;
                    mTwiceBaseCache = (Object[])array[0];
                    mHashes = (int[])array[1];
                    array[0] = array[1] = null;
                    mTwiceBaseCacheSize--;
                    if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes
                            + " now have " + mTwiceBaseCacheSize + " entries");
                    return;
                }
            }
        } else if (size == BASE_SIZE) {
            synchronized (ArrayMap.class) {
                if (mBaseCache != null) {
                    final Object[] array = mBaseCache;
                    mArray = array;
                    mBaseCache = (Object[])array[0];
                    mHashes = (int[])array[1];
                    //將緩存置為null
                    array[0] = array[1] = null;
                    //遞減mBaseCacheSize
                    mBaseCacheSize--;
                    if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes
                            + " now have " + mBaseCacheSize + " entries");
                    return;
                }
            }
        }

        mHashes = new int[size];
        mArray = new Object[size<<1];
    }

從代碼中可以看到，如果分配的size恰好等于4或者8, 則ArrayMap會優(yōu)先在緩存中找，如果有緩存則直接使用緩存的數(shù)組，這樣就避免了頻繁的創(chuàng)建數(shù)組帶來的內存消耗

方法

1. put

 public V put(K key, V value) {
        final int hash;
        int index;
        //查找key值對應的index,如果找到則為正數(shù)，否則為負數(shù)，代表了將要被插入的位置
        if (key == null) {
            hash = 0;
            //【1.1】
            index = indexOfNull();
        } else {
            hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
            index = indexOf(key, hash);
        }
        //已存在key值，直接覆蓋為新值
        if (index >= 0) {
            index = (index<<1) + 1;
            final V old = (V)mArray[index];
            mArray[index] = value;
            return old;
        }

        //key值并不存在，則對index取反，獲取將要被插入的index
        index = ~index;
        if (mSize >= mHashes.length) {
            //確定擴容的容量
            final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
                    : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

            if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);

            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
            //重新分配數(shù)組，如果滿足緩存條件，使用緩存
            allocArrays(n);

            //遷移數(shù)組
            if (mHashes.length > 0) {
                if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");
                System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
                System.arraycopy(oarray, 0, mArray, 0, oarray.length);
            }

            //釋放之前的數(shù)組，如果之前的數(shù)組滿足緩存條件，則將數(shù)組緩存起來, 【1.2】
            freeArrays(ohashes, oarray, mSize);
        }
        
        //插入數(shù)據(jù)
        if (index < mSize) {
            if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index)
                    + " to " + (index+1));
            System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
            System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
        }

        mHashes[index] = hash;
        mArray[index<<1] = key;
        mArray[(index<<1)+1] = value;
        mSize++;
        return null;
    }

查找key值對應的index, 這里使用的也是二分搜索法，如果key值已存在則index為正數(shù)，否則為負數(shù)
如果key值已存在，直接覆蓋為新值
如果key值不存在，對index取反
如果容量不夠，進行擴容操作，生成新的數(shù)組，如果滿足緩存條件，還會將就數(shù)組緩存起來避免頻繁分配數(shù)組，之后前移現(xiàn)有數(shù)據(jù)到新數(shù)組
插入數(shù)據(jù)

1.1 indexOfNull

    int indexOfNull() {
        final int N = mSize;

        //如果數(shù)組為空，那么什么也不做
        if (N == 0) {
            return ~0;
        }
        
        //二分搜索
        int index = ContainerHelpers.binarySearch(mHashes, N, 0);

        //index < 0 代表數(shù)組中并不存在key,直接返回
        if (index < 0) {
            return index;
        }

        //如果index處對應的key值恰好就是null, 則直接返回index
        if (null == mArray[index<<1]) {
            return index;
        }

        //從index后面找尋是否存在key為null
        int end;
        for (end = index + 1; end < N && mHashes[end] == 0; end++) {
            if (null == mArray[end << 1]) return end;
        }

        //從index前面找尋是否存在key為null
        for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {
            if (null == mArray[i << 1]) return i;
        }
        
        //都沒找到，返回將要被插入的索引位置的負數(shù)
        return ~end;
    }

indexOf的實現(xiàn)與indexOfNull基本一樣，只不過indexOfNull是判斷key值是否等于null

1.2 freeArrays

    private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
        if (hashes.length == (BASE_SIZE*2)) {
            synchronized (ArrayMap.class) {
                if (mTwiceBaseCacheSize < CACHE_SIZE) {
                    array[0] = mTwiceBaseCache;
                    array[1] = hashes;
                    for (int i=(size<<1)-1; i>=2; i--) {
                        array[i] = null;
                    }
                    mTwiceBaseCache = array;
                    mTwiceBaseCacheSize++;
                    if (DEBUG) Log.d(TAG, "Storing 2x cache " + array
                            + " now have " + mTwiceBaseCacheSize + " entries");
                }
            }
        } else if (hashes.length == BASE_SIZE) {
            synchronized (ArrayMap.class) {
                if (mBaseCacheSize < CACHE_SIZE) {
                    array[0] = mBaseCache;
                    array[1] = hashes;
                    for (int i=(size<<1)-1; i>=2; i--) {
                        array[i] = null;
                    }
                    mBaseCache = array;
                    mBaseCacheSize++;
                    if (DEBUG) Log.d(TAG, "Storing 1x cache " + array
                            + " now have " + mBaseCacheSize + " entries");
                }
            }
        }
    }

CACHE_SIZE等于10，這意味著最多緩存十個數(shù)組，當舊的數(shù)組大小等于4或者8的時候，都會被緩存

2. get


    public V get(Object key) {
        final int index = indexOfKey(key);
        return index >= 0 ? (V)mArray[(index<<1)+1] : null;
    }

get方法非常簡單，獲取索引，根據(jù)索引返回對應值，就這么簡單!

3. remove

    public V remove(Object key) {
        final int index = indexOfKey(key);
        if (index >= 0) {
            return removeAt(index);
        }

        return null;
    }
    
    public V removeAt(int index) {
        final Object old = mArray[(index << 1) + 1];
        if (mSize <= 1) {
            freeArrays(mHashes, mArray, mSize);
            mHashes = EmptyArray.INT;
            mArray = EmptyArray.OBJECT;
            mSize = 0;
        } else {
            //如果容量不到1/3降低ArrayMap容量
            if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
                //保證容量不小于BASE_SIZE * 2
                final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2);
                final int[] ohashes = mHashes;
                final Object[] oarray = mArray;
                allocArrays(n);

                mSize--;
                if (index > 0) {
                    System.arraycopy(ohashes, 0, mHashes, 0, index);
                    System.arraycopy(oarray, 0, mArray, 0, index << 1);
                }
                if (index < mSize) {
                    System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index);
                    System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
                            (mSize - index) << 1);
                }
            } else {
                mSize--;
                if (index < mSize) {
                    //把后面的數(shù)據(jù)往前前移一位
                    System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);
                    System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
                            (mSize - index) << 1);
                }
                mArray[mSize << 1] = null;
                mArray[(mSize << 1) + 1] = null;
            }
        }
        return (V)old;
    }

remove首先獲取索引值，然后直接調用removeAt來刪除對應的值，

性能分析

ArrayMap在確定index時，使用的也是二分查找法，其效率肯定會隨著數(shù)據(jù)量的增大而受到影響，另外從代碼中也可以看到，ArrayMap中比較頻繁的出現(xiàn)了數(shù)組遷移，這就又會造成一些性能的損失，但是如果從內存角度來看，ArrayMap內部使用了緩存，且在刪除元素后，會適當?shù)目s小容量，減少內存占用，綜合來看，如果數(shù)據(jù)量不大，且鯊如何刪除操作不頻繁時ArrayMap還是比較適用

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

ArrayMap源碼分析

ArrayMap源碼分析

成員變量

構造函數(shù)

allocArrays

方法

1. put

1.1 indexOfNull

1.2 freeArrays

2. get

3. remove

性能分析

相關閱讀更多精彩內容

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

ArrayMap源碼分析

成員變量

構造函數(shù)

allocArrays

方法

1. put

1.1 indexOfNull

1.2 freeArrays

2. get

3. remove

性能分析

相關閱讀更多精彩內容

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av