Android數(shù)據(jù)結(jié)構(gòu)優(yōu)化教程

更新時間：2023年01月31日 08:33:33 作者：劉知意

這篇文章主要介紹了Android數(shù)據(jù)結(jié)構(gòu)優(yōu)化方案，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習吧

ArrayList與LinkedList

ArrayList查找快，增刪慢，內(nèi)部為數(shù)組，連續(xù)空間，地址帶順序查找修改快，增加，刪除底層為System.copy操作，而copy為循環(huán)賦值，末尾添加刪除不受影響。
LinkedList增刪快，查找慢，內(nèi)部操作node，是鏈表，插入刪除只操作該節(jié)點的頭尾指針即可，內(nèi)存不連續(xù)，查找是輪詢的方式，使用的for循環(huán)耗時操作。查找修改慢

選擇方式：數(shù)據(jù)不進行大量增刪，只按順序排列顯示用ArrayList如listview，recycleview；顯示的數(shù)據(jù)包含用戶可以進行刪除操作，使用LinkedList；

HashMap：1.7之前Android24之前使用的數(shù)組保存，數(shù)組的構(gòu)造使用的鏈表，數(shù)組（ArrayList） + 鏈表，整體為一個數(shù)組，數(shù)組內(nèi)每一個元素，為鏈表，數(shù)組和鏈表共同構(gòu)成一個節(jié)點；1.8之后，除了數(shù)組和鏈表外還有紅黑樹(二叉樹，平衡二叉樹)，LinkedHaspMap雙向指針。

1.7：

transient Entry[] table = (Entry<K,V>[]) EMPTY_TABLE;

如何保證K:V唯一對應(yīng)，查看put（）方法

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K, V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;	
    addEntry(hash, key, value, i);
    return null;
}

final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    static int indexFor(int h, int length) {
        return h & (length-1);
    }

void addEntry(int hash, K key, V value, int bucketIndex) {
    	//sizi大于閾值 2倍擴容	
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }

void createEntry(int hash, K key, V value, int bucketIndex) {  
        Entry<K,V> e = table[bucketIndex]; 
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

put過程：k為object類型，根據(jù)k找到int類型的hashcode，裝箱過程，table []大小未知，根據(jù)hashcode % table的length求模運算，得到范圍0-length-1，求模運算等價于位運算，源碼中使用的是位運算，更快，往JVM轉(zhuǎn)為字節(jié)碼時速度更快，這時得到下標index即源碼中的i，通過下標i找到要操作的位置，完成k的任務(wù)。然后進行 addEntry(hash, key, value, i);調(diào)用了createEntry方法，先把下標i記錄成e，然后使用HashMapEntry賦值，new一個新的節(jié)點，新節(jié)點指向e，再把新節(jié)點賦值給table[bucketIndex]即頭插法，將新節(jié)點放到i的位置。

put: k:Object -> hashcode :int -> (hashcode % length) == (h & (length -1))-> :0~length-1 index;

哈希碰撞：得到index的過程是hash運算的位移運算（求模），求模是多對一的過程，多對一的過程，hashcode1 hashcode2 會得到相同的index，于是出現(xiàn)了哈希碰撞（哈希沖突），hashmap提供了解決碰撞的方法：鏈表法，將新加入的的節(jié)點作為下一個節(jié)點的next節(jié)點。

cpu：所有操作都是位運算，其中最快的就是位置，&或|運算而不是+

查看get（）方法

public V get(Object key) {   
    if (key == null)   
        return getForNullKey();   
    int hash = hash(key.hashCode());   
    for (Entry<K,V> e = table[indexFor(hash, table.length)];   
        e != null;   
        e = e.next) {   
        Object k;   
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))   
            return e.value;   
    }   
    return null;   
}

類似get（）先找到index ，然后輪詢table[]這個位置的鏈表。

擴容問題：

加載因子：final float loadFactor = 0.75；（這個表超過百分之多少開始擴容）

閾值： 0.75f*16(length)=12;element（所有存的元素）>12即擴容，

默認hashmap大小：16，即new Hashmap（）內(nèi)的table[16]，大小需為2的次冪

擴容的意義：0.6-0.75做加載因子最合適，數(shù)學家測試的結(jié)果。提升效率，當一個表全部沖突的時候效率最低退化成單鏈表，增刪高效，查找低。避免沖突，長度更大，沖突的可能性更低

addEntry時如果大于閾值2倍擴容，調(diào)用resize（）

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);//用來將原先table的元素全部移到newTable里面
    table = newTable;  //再將newTable賦值給table
    threshold = (int)(newCapacity * loadFactor);//重新計算臨界值
}

擴容的時候?qū)asp表進行轉(zhuǎn)移transfer

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        //遍歷舊表
        for (Entry<K,V> e : table) {
            //將所有的節(jié)點進行hash運算
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

擴容耗性能，避免擴容，創(chuàng)建時應(yīng)該評估hash表的大小，（大小/0.75+1），如何保證大小為2的次冪，這就和put時有關(guān)。表空時調(diào)用inflateTable(threshold);

private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);//初始化hashSeed變量
}
private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY
        ? MAXIMUM_CAPACITY
        : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

會進行運算，轉(zhuǎn)為最近的2的次冪。hash表真正的初始化是在put的時候，而不是new的時候。

初始化：put時候，防止創(chuàng)建未用，再put時，才真正初始化

大小為2的次冪原因：保證h & (length -1)運算，如 16-1的二進制位:1111,32-1為：11111,如果不是2的次冪，如length為10，length-1為9，二進制為：1001，進行與運算后只有最高位和最低位起作用，2的次冪的話，起作用的值更多，碰撞的可能性更低

例子：

	十進制	二進制（hash值）	與運算
h1	6	0110
length1-1	9	1001	0000
length2-1	15	1111	0110
h2	7	0111
length1-1	9	1001	0001
length2-1	15	1111	0111

hashmap有閾值，25%的內(nèi)存浪費空間換時間，尤其擴容的時候，如果多1個節(jié)點就擴容了兩倍。

安卓中出現(xiàn)了SparseArray：使用雙數(shù)組，一個存key 一個存value

public class SparseArray<E> implements Cloneable {
    private static final Object DELETED = new Object();
    private boolean mGarbage = false;
    private int[] mKeys;
    private Object[] mValues;
    private int mSize;

key為int類型，value對object

public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    //原來已經(jīng)有key，可能是remove后，value存放著DELETED，也可能是存放舊值，那么就替換
    if (i >= 0) {
        mValues[i] = value;
    } else {
        //沒有找到，對i取反，得到i= lo（ContainerHelpers.binarySearch）
        i = ~i;
        //如果i小于數(shù)組長度，且mValues==DELETED(i對應(yīng)的Key被延遲刪除了)
        if (i < mSize && mValues[i] == DELETED) {
            //直接取代，實現(xiàn)真實刪除原鍵值對
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }
        //數(shù)組中可能存在延遲刪除元素且當前數(shù)組長度滿，無法添加
        if (mGarbage && mSize >= mKeys.length) {
            //真實刪除，將所有延遲刪除的元素從數(shù)組中清除；
            gc();
            //清除后重新確定當前key在數(shù)組中的目標位置；
            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }
        //不存在垃圾或者當前數(shù)組仍然可以繼續(xù)添加元素，不需要擴容，則將i之后的元素全部后移，數(shù)組中仍然存在被DELETED的垃圾key；
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        //新元素添加成功，潛在可用元素數(shù)量+1
        mSize++;
    }
}

class ContainerHelpers {

// This is Arrays.binarySearch(), but doesn't do any argument validation.
//第一個參數(shù)array為keys的數(shù)組，第二個為數(shù)組中元素個數(shù)（與keys的length不一定相等），第三個value為目標的key
static int binarySearch(int[] array, int size, int value) {
    //lo為二分查找的左邊界
    int lo = 0;
    //hi為二分查找的右邊界
    int hi = size - 1;
    //還沒找到，繼續(xù)查找
    while (lo <= hi) {
        //左邊界+右邊界處以2，獲取到mid 的index
        final int mid = (lo + hi) >>> 1;
        //獲取中間元素
        final int midVal = array[mid];
        // 目標key在右部分  。。。。感覺這部分太簡單了
        if (midVal < value) {
            lo = mid + 1;
        } else if (midVal > value) {
            hi = mid - 1;
        } else {
            //相等，找到了，返回key對應(yīng)在array的下標；
            return mid;  // value found
        }
    }
    //沒有找到該元素，對lo取反?。。。?！很重要
    return ~lo;  // value not present
}

尋找key使用二分查找，找到該插入的index后，后續(xù)的元素使用arraycopy。

內(nèi)存節(jié)約，速度不會慢，使用的二分查找，一個一個放for循環(huán)放入，亂序二分。越用越快，remove的時候，把移除的下標標記為delet，下次插入到這里，直接放，不要數(shù)組位移?？臻g復用，效率更高。

public void delete(int key) {
    //查找對應(yīng)key在數(shù)組中的下標，如果存在，返回下標，不存在，返回下標的取反；
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    //key存在于mKeys數(shù)組中，將元素刪除，用DELETED替換原value，起標記作用；
    if (i >= 0) {
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;
            mGarbage = true;
        }
    }
}
/**
 * @hide
 * Removes the mapping from the specified key, if there was any, returning the old value.
 */
public E removeReturnOld(int key) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 
    if (i >= 0) {
        if (mValues[i] != DELETED) {
            final E old = (E) mValues[i];
            mValues[i] = DELETED;
            mGarbage = true;
            return old;
        }
    }
    return null;
}
/**
 * Alias for {@link #delete(int)}.
 */
public void remove(int key) {
    delete(key);
}

缺點：key只能是int值

ArrayMap：HashMap + SparseArray思想

@Override
    public V put(K key, V value) {
        //當前容量
        final int osize = mSize;
        //key的散列值
        final int hash;
        //key的hash所在的下標
        int index;
        if (key == null) {
            //key為空hash值為0
            hash = 0;
            //找到key的hash值的下標
            index = indexOfNull();
        } else {
            //key的hash值
            hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
            // 找到key的hash值的下標
            index = indexOf(key, hash);
        }
        if (index >= 0) {
            //當前要添加的元素已經(jīng)存在，則直接進行替換操作
            index = (index<<1) + 1;
            final V old = (V)mArray[index];
            mArray[index] = value;
            return old;
        }
        //取反得到要添加元素的位置
        index = ~index;
        if (osize >= mHashes.length) {
            //擴容新的容量
            final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
                    : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
            if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);
            //原h(huán)ash數(shù)組
            final int[] ohashes = mHashes;
            //原散列表
            final Object[] oarray = mArray;
            //擴容操作
            allocArrays(n);
            if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
                throw new ConcurrentModificationException();
            }
            if (mHashes.length > 0) {
                if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0");
                //將原數(shù)組中的拷貝回新數(shù)組中
                System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
                System.arraycopy(oarray, 0, mArray, 0, oarray.length);
            }
            //回收釋放操作
            freeArrays(ohashes, oarray, osize);
        }
        if (index < osize) {
            if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index)
                    + " to " + (index+1));
            //將index處（含index）及其之后的數(shù)據(jù)往后移
            System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
            System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
        }
        if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
            if (osize != mSize || index >= mHashes.length) {
                throw new ConcurrentModificationException();
            }
        }
        //將數(shù)據(jù)添加到index處
        mHashes[index] = hash;
        mArray[index<<1] = key;
        mArray[(index<<1)+1] = value;
        mSize++;
        return null;
    }
private void allocArrays(final int size) {
        if (mHashes == EMPTY_IMMUTABLE_INTS) {
            //擴容時如果mHashes 是不可變的，則拋出異常
            throw new UnsupportedOperationException("ArrayMap is immutable");
        }
        if (size == (BASE_SIZE*2)) {
            //如果擴容容量為8（BASE_SIZE=4）
            synchronized (ArrayMap.class) {
                if (mTwiceBaseCache != null) {
                    /**
                      如果當前有容量為8的int緩存可復用數(shù)組和容量為16的object緩存可復用數(shù)組，則復用這些數(shù)組，而不重新new
                     */
                    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) {
             //如果擴容容量為4（BASE_SIZE=4）
            synchronized (ArrayMap.class) {
                if (mBaseCache != null) {
                    /**
                      如果當前有容量為4的int緩存可復用數(shù)組和容量為8的object緩存可復用數(shù)組，則復用這些數(shù)組，而不重新new
                     */
                    final Object[] array = mBaseCache;
                    mArray = array;
                    mBaseCache = (Object[])array[0];
                    mHashes = (int[])array[1];
                    array[0] = array[1] = null;
                    mBaseCacheSize--;
                    if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes
                            + " now have " + mBaseCacheSize + " entries");
                    return;
                }
            }
        }
        mHashes = new int[size];
        mArray = new Object[size<<1];
    }
    private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
        if (hashes.length == (BASE_SIZE*2)) {
            //如果當前容量為8（BASE_SIZE=4）
            synchronized (ArrayMap.class) {
                if (mTwiceBaseCacheSize < CACHE_SIZE) {
                    //緩存當前數(shù)組，并將數(shù)組下標為2之后的數(shù)據(jù)設(shè)置為null
                    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) {
            //如果當前容量為4（BASE_SIZE=4）
            synchronized (ArrayMap.class) {
                //緩存當前數(shù)組，并將數(shù)組下標為2之后的數(shù)據(jù)設(shè)置為null
                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");
                }
            }
        }
    }

 @Override
  public V get(Object key) {
        //取得key的hashcode所在mHashes的下標,
        final int index = indexOfKey(key);
        /**
        根據(jù)mArray的數(shù)據(jù)存儲結(jié)構(gòu)，得知mHashes的 下標*2  (index << 1)便得到其對應(yīng)元素在mArray的起始下標，第一個是key，第二個是value
        */
        return index >= 0 ? (V)mArray[(index<<1)+1] : null;
  }
public int indexOfKey(Object key) {
        return key == null ? indexOfNull()
                : indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
}
int indexOf(Object key, int hash) {
        final int N = mSize;
        // Important fast case: if nothing is in here, nothing to look for.
        if (N == 0) {
            return ~0;
        }
        //二分法找到hash所在的下標
        int index = binarySearchHashes(mHashes, N, hash);
        // If the hash code wasn't found, then we have no entry for this key.
        if (index < 0) {
            //沒找到，直接返回
            return index;
        }
        // If the key at the returned index matches, that's what we want.
        if (key.equals(mArray[index<<1])) {
            //如果hash下標對應(yīng)mArray中的key與要找的key相等，直接返回當前下標
            return index;
        }
        //出現(xiàn)沖突處理方案
        //遍歷當前index之后元素，找到匹配的key所在的下標
        // Search for a matching key after the index.
        int end;
        for (end = index + 1; end < N && mHashes[end] == hash; end++) {
            if (key.equals(mArray[end << 1])) return end;
        }
        //遍歷當前index之前元素，找到匹配的key所在的下標
        // Search for a matching key before the index.
        for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
            if (key.equals(mArray[i << 1])) return i;
        }
        // Key not found -- return negative value indicating where a
        // new entry for this key should go.  We use the end of the
        // hash chain to reduce the number of array entries that will
        // need to be copied when inserting.
        return ~end;
}

遇到hash沖突使用追加的方式，沖突時候index累加的方式。

性能提升：空間和時間的選擇問題

到此這篇關(guān)于Android數(shù)據(jù)結(jié)構(gòu)優(yōu)化教程的文章就介紹到這了,更多相關(guān)Android數(shù)據(jù)結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: