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é)點(diǎn)的頭尾指針即可,內(nèi)存不連續(xù),查找是輪詢的方式,使用的for循環(huán)耗時(shí)操作。查找修改慢
選擇方式:數(shù)據(jù)不進(jìn)行大量增刪,只按順序排列顯示用ArrayList如listview,recycleview;顯示的數(shù)據(jù)包含用戶可以進(jìn)行刪除操作,使用LinkedList;
HashMap:1.7之前Android24之前使用的數(shù)組保存,數(shù)組的構(gòu)造使用的鏈表,數(shù)組(ArrayList) + 鏈表,整體為一個(gè)數(shù)組,數(shù)組內(nèi)每一個(gè)元素,為鏈表,數(shù)組和鏈表共同構(gòu)成一個(gè)節(jié)點(diǎn);1.8之后,除了數(shù)組和鏈表外還有紅黑樹(二叉樹,平衡二叉樹),LinkedHaspMap雙向指針。
1.7:
transient Entry[] table = (Entry<K,V>[]) EMPTY_TABLE;
如何保證K:V唯一對(duì)應(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倍擴(kuò)容 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求模運(yùn)算,得到范圍0-length-1,求模運(yùn)算等價(jià)于位運(yùn)算,源碼中使用的是位運(yùn)算,更快,往JVM轉(zhuǎn)為字節(jié)碼時(shí)速度更快,這時(shí)得到下標(biāo)index即源碼中的i,通過下標(biāo)i找到要操作的位置,完成k的任務(wù)。然后進(jìn)行 addEntry(hash, key, value, i);調(diào)用了createEntry方法,先把下標(biāo)i記錄成e,然后使用HashMapEntry賦值,new一個(gè)新的節(jié)點(diǎn),新節(jié)點(diǎn)指向e,再把新節(jié)點(diǎn)賦值給table[bucketIndex]即頭插法,將新節(jié)點(diǎn)放到i的位置。
put: k:Object -> hashcode :int -> (hashcode % length) == (h & (length -1))-> :0~length-1 index;
哈希碰撞:得到index的過程是hash運(yùn)算的位移運(yùn)算(求模),求模是多對(duì)一的過程,多對(duì)一的過程,hashcode1 hashcode2 會(huì)得到相同的index,于是出現(xiàn)了哈希碰撞(哈希沖突),hashmap提供了解決碰撞的方法:鏈表法,將新加入的的節(jié)點(diǎn)作為下一個(gè)節(jié)點(diǎn)的next節(jié)點(diǎn)。
cpu:所有操作都是位運(yùn)算,其中最快的就是 位置,&或|運(yùn)算而不是+
查看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[]這個(gè)位置的鏈表。
擴(kuò)容問題:
加載因子:final float loadFactor = 0.75;(這個(gè)表超過百分之多少開始擴(kuò)容)
閾值: 0.75f*16(length)=12;element(所有存的元素)>12即擴(kuò)容,
默認(rèn)hashmap大?。?6,即new Hashmap()內(nèi)的table[16],大小需為2的次冪
擴(kuò)容的意義:0.6-0.75做加載因子最合適,數(shù)學(xué)家測(cè)試的結(jié)果。提升效率,當(dāng)一個(gè)表全部沖突的時(shí)候效率最低退化成單鏈表,增刪高效,查找低。避免沖突,長(zhǎng)度更大,沖突的可能性更低
addEntry時(shí)如果大于閾值2倍擴(kuò)容,調(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);//重新計(jì)算臨界值 }
擴(kuò)容的時(shí)候?qū)asp表進(jìn)行轉(zhuǎn)移transfer
void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; //遍歷舊表 for (Entry<K,V> e : table) { //將所有的節(jié)點(diǎn)進(jìn)行hash運(yùn)算 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; } } }
擴(kuò)容耗性能,避免擴(kuò)容,創(chuàng)建時(shí)應(yīng)該評(píng)估hash表的大小,(大小/0.75+1),如何保證大小為2的次冪,這就和put時(shí)有關(guān)。表空時(shí)調(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; }
會(huì)進(jìn)行運(yùn)算,轉(zhuǎn)為最近的2的次冪。hash表真正的初始化是在put的時(shí)候,而不是new的時(shí)候。
初始化:put時(shí)候,防止創(chuàng)建未用,再put時(shí),才真正初始化
大小為2的次冪原因:保證h & (length -1)運(yùn)算,如 16-1的二進(jìn)制位:1111,32-1為:11111,如果不是2的次冪,如length為10,length-1為9,二進(jìn)制為:1001,進(jìn)行與運(yùn)算后只有最高位和最低位起作用,2的次冪的話,起作用的值更多,碰撞的可能性更低
例子:
十進(jìn)制 | 二進(jìn)制(hash值) | 與運(yùn)算 | |
---|---|---|---|
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)存浪費(fèi) 空間換時(shí)間,尤其擴(kuò)容的時(shí)候,如果多1個(gè)節(jié)點(diǎn)就擴(kuò)容了兩倍。
安卓中出現(xiàn)了SparseArray:使用雙數(shù)組,一個(gè)存key 一個(gè)存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對(duì)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 { //沒有找到,對(duì)i取反,得到i= lo(ContainerHelpers.binarySearch) i = ~i; //如果i小于數(shù)組長(zhǎng)度,且mValues==DELETED(i對(duì)應(yīng)的Key被延遲刪除了) if (i < mSize && mValues[i] == DELETED) { //直接取代,實(shí)現(xiàn)真實(shí)刪除原鍵值對(duì) mKeys[i] = key; mValues[i] = value; return; } //數(shù)組中可能存在延遲刪除元素且當(dāng)前數(shù)組長(zhǎng)度滿,無法添加 if (mGarbage && mSize >= mKeys.length) { //真實(shí)刪除,將所有延遲刪除的元素從數(shù)組中清除; gc(); //清除后重新確定當(dāng)前key在數(shù)組中的目標(biāo)位置; // Search again because indices may have changed. i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } //不存在垃圾或者當(dāng)前數(shù)組仍然可以繼續(xù)添加元素,不需要擴(kuò)容,則將i之后的元素全部后移,數(shù)組中仍然存在被DELETED的垃圾key; mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); //新元素添加成功,潛在可用元素?cái)?shù)量+1 mSize++; } }
class ContainerHelpers {
// This is Arrays.binarySearch(), but doesn't do any argument validation. //第一個(gè)參數(shù)array為keys的數(shù)組,第二個(gè)為數(shù)組中元素個(gè)數(shù)(與keys的length不一定相等),第三個(gè)value為目標(biāo)的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]; // 目標(biāo)key在右部分 。。。。感覺這部分太簡(jiǎn)單了 if (midVal < value) { lo = mid + 1; } else if (midVal > value) { hi = mid - 1; } else { //相等,找到了,返回key對(duì)應(yīng)在array的下標(biāo); return mid; // value found } } //沒有找到該元素,對(duì)lo取反!?。。。『苤匾? return ~lo; // value not present }
尋找key使用二分查找,找到該插入的index后,后續(xù)的元素使用arraycopy。
內(nèi)存節(jié)約,速度不會(huì)慢,使用的二分查找,一個(gè)一個(gè)放for循環(huán)放入,亂序二分。越用越快,remove的時(shí)候,把移除的下標(biāo)標(biāo)記為delet,下次插入到這里,直接放,不要數(shù)組位移??臻g復(fù)用,效率更高。
public void delete(int key) { //查找對(duì)應(yīng)key在數(shù)組中的下標(biāo),如果存在,返回下標(biāo),不存在,返回下標(biāo)的取反; int i = ContainerHelpers.binarySearch(mKeys, mSize, key); //key存在于mKeys數(shù)組中,將元素刪除,用DELETED替換原value,起標(biāo)記作用; 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); }
缺點(diǎn):key只能是int值
ArrayMap:HashMap + SparseArray思想
@Override public V put(K key, V value) { //當(dāng)前容量 final int osize = mSize; //key的散列值 final int hash; //key的hash所在的下標(biāo) int index; if (key == null) { //key為空hash值為0 hash = 0; //找到key的hash值的下標(biāo) index = indexOfNull(); } else { //key的hash值 hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode(); // 找到key的hash值的下標(biāo) index = indexOf(key, hash); } if (index >= 0) { //當(dāng)前要添加的元素已經(jīng)存在,則直接進(jìn)行替換操作 index = (index<<1) + 1; final V old = (V)mArray[index]; mArray[index] = value; return old; } //取反得到要添加元素的位置 index = ~index; if (osize >= mHashes.length) { //擴(kuò)容新的容量 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; //擴(kuò)容操作 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) { //擴(kuò)容時(shí)如果mHashes 是不可變的,則拋出異常 throw new UnsupportedOperationException("ArrayMap is immutable"); } if (size == (BASE_SIZE*2)) { //如果擴(kuò)容容量為8(BASE_SIZE=4) synchronized (ArrayMap.class) { if (mTwiceBaseCache != null) { /** 如果當(dāng)前有容量為8的int緩存可復(fù)用數(shù)組和容量為16的object緩存可復(fù)用數(shù)組,則復(fù)用這些數(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) { //如果擴(kuò)容容量為4(BASE_SIZE=4) synchronized (ArrayMap.class) { if (mBaseCache != null) { /** 如果當(dāng)前有容量為4的int緩存可復(fù)用數(shù)組和容量為8的object緩存可復(fù)用數(shù)組,則復(fù)用這些數(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)) { //如果當(dāng)前容量為8(BASE_SIZE=4) synchronized (ArrayMap.class) { if (mTwiceBaseCacheSize < CACHE_SIZE) { //緩存當(dāng)前數(shù)組,并將數(shù)組下標(biāo)為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) { //如果當(dāng)前容量為4(BASE_SIZE=4) synchronized (ArrayMap.class) { //緩存當(dāng)前數(shù)組,并將數(shù)組下標(biāo)為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的下標(biāo), final int index = indexOfKey(key); /** 根據(jù)mArray的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu),得知mHashes的 下標(biāo)*2 (index << 1)便得到其對(duì)應(yīng)元素在mArray的起始下標(biāo),第一個(gè)是key,第二個(gè)是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所在的下標(biāo) 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下標(biāo)對(duì)應(yīng)mArray中的key與要找的key相等,直接返回當(dāng)前下標(biāo) return index; } //出現(xiàn)沖突處理方案 //遍歷當(dāng)前index之后元素,找到匹配的key所在的下標(biāo) // 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; } //遍歷當(dāng)前index之前元素,找到匹配的key所在的下標(biāo) // 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沖突使用追加的方式,沖突時(shí)候index累加的方式。
性能提升: 空間和時(shí)間的選擇問題
到此這篇關(guān)于Android數(shù)據(jù)結(jié)構(gòu)優(yōu)化教程的文章就介紹到這了,更多相關(guān)Android數(shù)據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Android實(shí)現(xiàn)動(dòng)態(tài)高斯模糊效果示例代碼
這篇文章主要介紹了Android快速實(shí)現(xiàn)動(dòng)態(tài)模糊效果示例代碼,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下。2017-01-01Flutter以兩種方式實(shí)現(xiàn)App主題切換的代碼
這篇文章主要介紹了Flutter以兩種方式實(shí)現(xiàn)App主題切換的代碼,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-04-04Android實(shí)現(xiàn)點(diǎn)擊圖片上傳SQLite數(shù)據(jù)庫(kù)
這篇文章主要為大家詳細(xì)介紹了Android實(shí)現(xiàn)點(diǎn)擊圖片上傳SQLite數(shù)據(jù)庫(kù),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-08-08Flutter之自定義Dialog實(shí)現(xiàn)版本更新彈窗功能的實(shí)現(xiàn)
這篇文章主要介紹了Flutter之自定義Dialog實(shí)現(xiàn)版本更新彈窗功能的實(shí)現(xiàn),本文通過實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-07-07取消Android Studio項(xiàng)目與SVN關(guān)聯(lián)的方法
今天小編就為大家分享一篇關(guān)于取消Android Studio項(xiàng)目與SVN關(guān)聯(lián)的方法,小編覺得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來看看吧2018-12-12Android Studio 2020新版本卡在Gradle downloading/sync failed/下載緩慢/
Android Studio 2020新版本 卡在Gradle downloading / sync failed / 下載緩慢 / 下載超時(shí) 親測(cè)有效解決辦法,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友參考下吧2020-12-12