初識 ArrayMap

小菜在之前學習 SharedPreferences 源碼時注意到，其資料存儲主要用到了 ArrayMap，小菜在日常中對于 key-value 方式主要是 HashMap 居多，今天簡單研究一下 ArrayMap；

ArrayMap

ArrayMap 是一種相較于 HashMap 具有更高記憶體效率的 key-value 對存儲結構；ArrayMap 内部包括兩個數組結構，分别是專門用來存儲 HashCode 的 mHashes 和用來存儲 key-value 的 Object 數組類型的 mArray；

ArrayMap 是非線程安全的；

源碼分析

構造函數

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

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

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

ArrayMap 提供了三種構造方法，分别為無參的預設構造函數，添加預設容積的構造函數和一個隐藏的構造函數；若指定容積大小則直接配置設定相應大小的記憶體；若是預設構造函數，預設為 0，會在添加資料時動态擴容；

元素查詢

int indexOf(Object key, int hash) {
    final int N = mSize;
    // ====== TAG 01 ======
    int index = binarySearchHashes(mHashes, N, hash);
    if (index < 0) {
        return index;
    }
    if (key.equals(mArray[index<<1])) {
        return index;
    }
    // ====== TAG 02 ======
    for (end = index + 1; end < N && mHashes[end] == hash; end++) {
        if (key.equals(mArray[end << 1])) return end;
    }
    for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
        if (key.equals(mArray[i << 1])) return i;
    }
    return ~end;
}

ArrayMap 查找元素主要是通過 binarySearchHashes 二分查找方式來查找 index；若 HashCode 和 Key 均比對則為要查找的 index；若隻有 HashCode 相同但對象不同(即 HashCode 沖突)，則從目前對應的 index 向後和向前分别周遊查找；注意：采用二分查找，則說明 mHashes 數組是有序的；

元素添加

ArrayMap 添加元素的方式主要有 put 和 append 方式；

1. put()

public V put(K key, V value) {
    final int osize = mSize;
    final int hash;
    int index;
    if (key == null) {
        hash = 0;
        index = indexOfNull();
    } else {
        hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
        // ====== TAG 01 ====== 
        index = indexOf(key, hash);
    }
    if (index >= 0) {
        // ====== TAG 02 ====== 
        index = (index<<1) + 1;
        final V old = (V)mArray[index];
        mArray[index] = value;
        return old;
    }
    // ====== TAG 03 ====== 
    index = ~index;
    if (osize >= mHashes.length) {
        final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1)) : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
        final int[] ohashes = mHashes;
        final Object[] oarray = mArray;
        // ====== TAG 04 ======
        allocArrays(n);
        if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
            throw new ConcurrentModificationException();
        }
        // ====== TAG 05 ======
        if (mHashes.length > 0) {
            System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
            System.arraycopy(oarray, 0, mArray, 0, oarray.length);
        }
        freeArrays(ohashes, oarray, osize);
    }
    // ====== TAG 06 ======
    if (index < osize) {
        System.arraycopy(mHashes, index, mHashes, index + 1, osize - 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;
}

小菜在源碼處打了幾個需要注意的 TAG；

TAG 01: 主要用于二分查找的方式，在 mHashes 數組中查找 HashCode 值相等的 Key；
TAG 02: 在 index > 0 即有對應 HashCode 相等的 Key 之後，更新其 Value 值；通過 index << 1 左移的方式相當于 index * 2 隻是效率更高效，可多在實際項目中應用；
TAG 03: 在 index < 0 即沒有對應 HashCode 相等的 Key，此時需要插入新資料；
TAG 04: 當需要擴容時，可采用 allocArrays() 方式配置設定更大的記憶體空間；且 ArrayMap 是非線程安全的，不可并行；
TAG 05: 通過 System.arraycopy 将老的數組資料拷貝到新的數組中，再通過 freeArrays() 釋放老的數組記憶體；
TAG 06: 當需要插入的元素不在末尾時，拷貝完資料之後需要将 index 後移一位；

2. append()

public void append(K key, V value) {
    int index = mSize;
    final int hash = key == null ? 0 : (mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
    if (index >= mHashes.length) {
        throw new IllegalStateException("Array is full");
    }
    if (index > 0 && mHashes[index-1] > hash) {
        RuntimeException e = new RuntimeException("here");
        e.fillInStackTrace();
        // ====== TAG ======
        put(key, value);
        return;
    }
    mSize = index+1;
    mHashes[index] = hash;
    index <<= 1;
    mArray[index] = key;
    mArray[index+1] = value;
}

簡單檢視 append() 源碼，與 put() 相比少了擴容和記憶體回收等步驟；其兩者使用場景不同，append() 無需驗證即可将元素追加到數組末尾的特殊快速路徑，要求是數組必須足夠大；當資料需要插入到數組中間時調用 put() 方式；

元素删除

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

ArrayMap 可以通過 remove() 來删除固定元素；首先通過 indexOfKey 二分查找是否有對應要删除的元素，如果有通過 removeAt() 進行删除；

public V removeAt(int index) {
    final Object old = mArray[(index << 1) + 1];
    final int osize = mSize;
    final int nsize;
    // ====== TAG 01 ======
    if (osize <= 1) {
        final int[] ohashes = mHashes;
        final Object[] oarray = mArray;
        mHashes = EmptyArray.INT;
        mArray = EmptyArray.OBJECT;
        freeArrays(ohashes, oarray, osize);
        nsize = 0;
    } else {
        nsize = osize - 1;
        // ====== TAG 02 ======
        if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
            final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);
            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
            allocArrays(n);

            if (index > 0) {
                System.arraycopy(ohashes, 0, mHashes, 0, index);
                System.arraycopy(oarray, 0, mArray, 0, index << 1);
            }
            if (index < nsize) {
                System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index);
                System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, (nsize - index) << 1);
            }
        } else {
            // ====== TAG 03 ======
            if (index < nsize) {
                System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index);
                System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, (nsize - index) << 1);
            }
            mArray[nsize << 1] = null;
            mArray[(nsize << 1) + 1] = null;
        }
    }
    mSize = nsize;
    return (V)old;
}

TAG 01: 當數組隻有一個要删除的元素時，直接将 mHashes 和 mArray 置空并通過 freeArrays 釋放記憶體即可；
TAG 02: 當數組記憶體大小大于 8 并且元素數量少于 1/3 空間大小時，通過 allocArrays 進行減少記憶體配置設定，将老資料拷貝到新的數組中，并清空老資料數組空間；這是 HashMap 不曾實作的；
TAG 03: 當删除其中一個元素時，需要将該元素之後的所有元素向前移動一位；

數組擴容

HashMap 直接以容積的 2 倍進行擴容，而 ArrayMap 數組擴容是分階段擴容的；與基礎數組長度有關；

final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1)) : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

當 osize >= 8 時，數組擴容為原來的 1.5 倍；其中 osize >> 1 相當于 osize / 2；
當 4 <= osize < 8 時，此時擴充為 8；
當 osize < 4 時，此時擴充為 4；

記憶體機制

// ArrayMap 擴容的最小容積(用于調整為相對節省空間方式)
private static final int BASE_SIZE = 4;
// 最大緩存數組數
private static final int CACHE_SIZE = 10;
// 用來緩存 BASE_SIZE = 4 的數組内容
static Object[] mBaseCache;
// mBaseCache 緩存的數量
static int mBaseCacheSize;
// 用來存儲 BASE_SIZE * 2 = 8 的數組内容
static Object[] mTwiceBaseCache;
// mTwiceBaseCache 緩存的數量
static int mTwiceBaseCacheSize;

ArrayMap 為了避免頻繁的建立和銷毀，提供了 mBaseCache 和 mTwiceBaseCache 兩個數組緩沖池，同時提供了 allocArrays 和 freeArrays 記憶體配置設定和釋放的方法，兩者互相對應，都通過緩沖池配置設定和釋放記憶體；

private void allocArrays(final int size) {
    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--;
                return;
            }
        }
    } else if (size == BASE_SIZE) {
        ...
    }
    mHashes = new int[size];
    mArray = new Object[size<<1];
}

當需要配置設定記憶體大小為 BASE_SIZE 或 BASE_SIZE * 2 時，會先檢視對應的緩存池中取出 mArray 和 mHashes；其方式是先将緩存池指向上一條緩存位址，将緩存池的第 array[1] 個元素指派為 mHashes ，再把 mArray 的第 array[0] 和第 array[1] 個位置的資料置為 null；

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++;
            }
        }
    } else if (hashes.length == BASE_SIZE) {
        ...
    }
}

當記憶體需要釋放時，釋放大小為 BASE_SIZE 或 BASE_SIZE * 2 時，會将數組加入到緩沖池中；其方she式是先将原緩沖池和哈希數組分别指向 array 前兩位，之後的元素全部置空，最後将緩存池的頭部指向最新的數組位置；

注意事項

ArrayMap 不适合大量的資料結構，Google 建議在 1000 以内的資料量比較好；ArrayMap 内部采用了二分查找方式查詢，時間複雜度 O(logN)，每次添加和删除元素都需要移動其後面的元素，速度相對較慢；而 HashMap 查找和删除時間複雜度為 O(1)；

ArrayMap 相對于 HashMap 增加了記憶體緩存政策，避免頻繁建立對象而配置設定記憶體與 GC 操作，同時限制了緩沖池的上限(10 個)；與此同時，ArrayMap 還提供了靈活的擴容和縮容機制，這兩種機制比 HashMap 更靈活且節省時間；

ArrayMap 還解決了 HashMap 稀疏數組的問題，相對占用記憶體更少；

案例嘗試

ArrayMap map01 = new ArrayMap();
ArrayMap map02 = new ArrayMap(4);
// 元素添加
for (int i = 0;i < 6;i ++) {
    map01.put("index_"+(i+1), "map01.value_"+(i +1));
    map02.put("index_"+(i+1), "map02.value_"+(i +1));
}
for(int i = 0 ;i < map01.size();i ++){
    Log.e("ArrayMap 01 -->", map01.get("index_"+(i+1)).toString()+"==HashCode=="+map01.get("index_"+(i+1)).hashCode());
}
for(int i = 0 ;i < map02.size();i ++){
    Log.e("ArrayMap 02 -->", map02.get("index_"+(i+1)).toString()+"==HashCode=="+map02.get("index_"+(i+1)).hashCode());
}
// 元素删除
map01.remove("index_3");
// 元素修改
map01.put("index_4", "map01.value_4 changed!");
map02.remove("index_1");
map02.remove("index_2");
for(int i = 0 ;i < map01.size();i ++){
    if (map01.get("index_"+(i+1)) != null) {
        Log.e("ArrayMap 01 -->", map01.get("index_" + (i + 1)).toString() + "==HashCode==" + map01.get("index_" + (i + 1)).hashCode());
    }
}
for(int i = 0 ;i < map02.size();i ++){
    if (map02.get("index_"+(i+1)) != null) {
        Log.e("ArrayMap 02 -->", map02.get("index_" + (i + 1)).toString() + "==HashCode==" + map02.get("index_" + (i + 1)).hashCode());
    }
}

小菜對 ArrayMap 的源碼了解還不夠深入，與其他存儲方式的橫向對比也不夠全面；如有錯誤請多多指導！

來源：阿策小和尚

初識 ArrayMap

ArrayMap

源碼分析

構造函數

元素查詢

元素添加

1. put()

2. append()

元素删除

數組擴容

記憶體機制

注意事項

案例嘗試

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method