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)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Android實現(xiàn)動態(tài)高斯模糊效果示例代碼
這篇文章主要介紹了Android快速實現(xiàn)動態(tài)模糊效果示例代碼,具有一定的參考價值,感興趣的小伙伴們可以參考一下。2017-01-01Flutter以兩種方式實現(xiàn)App主題切換的代碼
這篇文章主要介紹了Flutter以兩種方式實現(xiàn)App主題切換的代碼,本文通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-04-04Android實現(xiàn)點擊圖片上傳SQLite數(shù)據(jù)庫
這篇文章主要為大家詳細介紹了Android實現(xiàn)點擊圖片上傳SQLite數(shù)據(jù)庫,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-08-08Flutter之自定義Dialog實現(xiàn)版本更新彈窗功能的實現(xiàn)
這篇文章主要介紹了Flutter之自定義Dialog實現(xiàn)版本更新彈窗功能的實現(xiàn),本文通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-07-07取消Android Studio項目與SVN關(guān)聯(lián)的方法
今天小編就為大家分享一篇關(guān)于取消Android Studio項目與SVN關(guān)聯(lián)的方法,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧2018-12-12Android Studio 2020新版本卡在Gradle downloading/sync failed/下載緩慢/
Android Studio 2020新版本 卡在Gradle downloading / sync failed / 下載緩慢 / 下載超時 親測有效解決辦法,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友參考下吧2020-12-12