摘要:也是我們使用非常多的,它是基于哈希表的接口的實現,以的形式存在。源碼分析三個構造函數默認初始容量,默認加載因子構造一個帶指定初始容量和默認加載因子的空。該臨界點在當中元素的數量等于數組長度加載因子。
HashMap也是我們使用非常多的Collection,它是基于哈希表的 Map 接口的實現,以key-value的形式存在。在HashMap中,key-value總是會當做一個整體來處理,系統會根據hash算法來來計算key-value的存儲位置,我們總是可以通過key快速地存、取value。
HashMapHashMap.java源碼分析:?
三個構造函數:?
HashMap():默認初始容量capacity(16),默認加載因子factor(0.75)?
HashMap(int initialCapacity):構造一個帶指定初始容量和默認加載因子 (0.75) 的空 HashMap。?
HashMap(int initialCapacity, float loadFactor):構造一個帶指定初始容量和加載因子的空 HashMap。
/** * Constructs an empty HashMap with the default initial capacity * (16) and the default load factor (0.75). */ public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } //構建自定義初始容量的構造函數,默認加載因子0.75的HashMap public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } //構造一個帶指定初始容量和加載因子的空 HashMap public HashMap(int initialCapacity, float loadFactor) { ... ... }
HashMap內部是使用一個默認容量為16的數組來存儲數據的,而數組中每一個元素卻又是一個鏈表的頭結點,所以,更準確的來說,HashMap內部存儲結構是使用哈希表的拉鏈結構(數組+鏈表),如圖:?
這種存儲數據的方法叫做拉鏈法?
且每一個結點都是Entry類型,那么Entry是什么呢?我們來看看HashMap中Entry的屬性:
final K key; //key值 V value; //value值 HashMapEntrynext;//next下一個Entry int hash;//key的hash值
put(key,value);
public V put(K key, V value) { if (table == EMPTY_TABLE) {//判斷table空數組, inflateTable(threshold);//創建數組容量為threshold大小的數組,threshold在HashMap構造函數中賦值initialCapacity(指定初始容量); } //當key為null,調用putForNullKey方法,保存null與table第一個位置中,這是HashMap允許key為null的原因 if (key == null) return putForNullKey(value); int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key); //計算key的hash值 int i = indexFor(hash, table.length); //計算key hash 值在 table 數組中的位置 //從i出開始迭代 e,找到 key 保存的位置 for (HashMapEntrye = table[i]; e != null; e = e.next) { Object k; //判斷該條鏈上是否有hash值相同的(key相同) //若存在相同,則直接覆蓋value,返回舊value if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value;//舊值 = 新值 e.value = value; e.recordAccess(this); return oldValue;//返回覆蓋后的舊值 } } //修改次數增加1 modCount++; //將key、value添加至i位置處 addEntry(hash, key, value, i); return null; }
put過程分析:這篇文章http://www.cnblogs.com/chenssy/p/3521565.html總結的可以。
put過程結論:?
當我們想一個HashMap中添加一對key-value時,系統首先會計算key的hash值,然后根據hash值確認在table中存儲的位置。若該位置沒有元素,則直接插入。否則迭代該處元素鏈表并依此比較其key的hash值。如果兩個hash值相等且key值相等(e.hash == hash && ((k = e.key) == key || key.equals(k))),則用新的Entry的value覆蓋原來節點的value。如果兩個hash值相等但key值不等 ,則將該節點插入該鏈表的鏈頭。
void addEntry(int hash, K key, V value, int bucketIndex) { //獲取bucketIndex處的Entry Entrye = table[bucketIndex]; //將新創建的 Entry 放入 bucketIndex 索引處,并讓新的 Entry 指向原來的 Entry table[bucketIndex] = new Entry (hash, key, value, e); //若HashMap中元素的個數超過極限了,則容量擴大兩倍 if (size++ >= threshold) resize(2 * table.length); }
這個方法中有兩點需要注意:
一是鏈的產生。這是一個非常優雅的設計。系統總是將新的Entry對象添加到bucketIndex處。如果bucketIndex處已經有了對象,那么新添加的Entry對象將 指向原有的Entry對象,形成一條Entry鏈,但是若bucketIndex處沒有Entry對象,也就是e==null,那么新添加的Entry對象指向null,也就不會產生Entry鏈了。 二、擴容問題。 隨著HashMap中元素的數量越來越多,發生碰撞的概率就越來越大,所產生的鏈表長度就會越來越長,這樣勢必會影響HashMap的速度,為了保證HashMap的效率,系統必須要在某個臨界點進行擴容處理。該臨界點在當HashMap中元素的數量等于table數組長度*加載因子。但是擴容是一個非常耗時的過程,因為它需要重新計算這些數據在新table數組中的位置并進行復制處理。所以如果我們已經預知HashMap中元素的個數,那么預設元素的個數能夠有效的提高HashMap的性能。
讀取實現:get(key)?
相對于HashMap的存而言,取就顯得比較簡單了。通過key的hash值找到在table數組中的索引處的Entry,然后返回該key對應的value即可。
public V get(Object key) { // 若為null,調用getForNullKey方法返回相對應的value if (key == null) return getForNullKey(); // 根據該 key 的 hashCode 值計算它的 hash 碼 int hash = hash(key.hashCode()); // 取出 table 數組中指定索引處的值 for (Entrye = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; //若搜索的key與查找的key相同,則返回相對應的value if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }
在不斷的向HashMap里put數據時,當達到一定的容量限制時(這個容量滿足這樣的一個關系時候將會擴容:HashMap中的數據量>容量*加載因子,而HashMap中默認的加載因子是0.75),HashMap的空間將會擴大;擴大之前容量的2倍 :resize(newCapacity)
int newCapacity = table.length;//賦值數組長度 newCapacity <<= 1;//x2 if (newCapacity > table.length) resize(newCapacity);//調整HashMap大小容量為之前table的2倍
這也就是重點所在,為什么在Android上需要使用SparseArray和ArrayMap代替HashMap,主要原因就是Hashmap隨著數據不斷增多,達到最大值時,需要擴容,而且擴容的大小是之前的2倍.
SparseArraySparseArray.java 源碼?
SparseArray比HashMap更省內存,在某些條件下性能更好,主要是因為它避免了對key的自動裝箱(int轉為Integer類型),它內部則是通過兩個數組來進行數據存儲的,一個存儲key,另外一個存儲value,為了優化性能,它內部對數據還采取了壓縮的方式來表示稀疏數組的數據,從而節約內存空間,我們從源碼中可以看到key和value分別是用數組表示:
private int[] mKeys;//int 類型key數組 private Object[] mValues;//value數組
構造函數:?
SparseArray():默認容量10;?
SparseArray(int initialCapacity):指定特定容量的SparseArray
public SparseArray() { this(10); } public SparseArray(int initialCapacity) { if (initialCapacity == 0) {//判斷傳入容量值 mKeys = EmptyArray.INT; mValues = EmptyArray.OBJECT; } else {//不為0初始化key value數組 mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity); mKeys = new int[mValues.length]; } mSize = 0;//mSize賦值0 }
從上面創建的key數組:SparseArray只能存儲key為int類型的數據,同時,SparseArray在存儲和讀取數據時候,使用的是二分查找法;
/** * 二分查找,中間位置的值與需要查找的值循環比對 * 小于:范圍從mid+1 ~ h1 * 大于:范圍從0~mid-1 * 等于:找到值返回位置mid */ static int binarySearch(int[] array, int size, int value) { int lo = 0; int hi = size - 1; while (lo <= hi) { final int mid = (lo + hi) >>> 1; final int midVal = array[mid]; if (midVal < value) { lo = mid + 1; } else if (midVal > value) { hi = mid - 1; } else { return mid; // value found } } return ~lo; // value not present }
SparseArray的put方法:
public void put(int key, E value) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key);//二分查找數組mKeys中key存放位置,返回值是否大于等于0來判斷查找成功 if (i >= 0) {//找到直接替換對應值 mValues[i] = value; } else {//沒有找到 i = ~i;//i按位取反得到非負數 if (i < mSize && mValues[i] == DELETED) {//對應值是否已刪除,是則替換對應鍵值 mKeys[i] = key; mValues[i] = value; return; } if (mGarbage && mSize >= mKeys.length) {//當mGarbage == true 并且mSize 大于等于key數組的長度 gc(); //調用gc回收 // Search again because indices may have changed. i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } //最后將新鍵值插入數組,調用 GrowingArrayUtils的insert方法: mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); mSize++; } }
下面進去看看 GrowingArrayUtils的insert方法有什么擴容的;
public staticT[] insert(T[] array, int currentSize, int index, T element) { assert currentSize <= array.length; if (currentSize + 1 <= array.length) {//小于數組長度 System.arraycopy(array, index, array, index + 1, currentSize - index); array[index] = element; return array; } //大于數組長度需要進行擴容 T[] newArray = (T[]) Array.newInstance(array.getClass().getComponentType(), growSize(currentSize));//擴容規則里面就一句三目運算:currentSize <= 4 ? 8 : currentSize * 2;(擴容2倍) System.arraycopy(array, 0, newArray, 0, index); newArray[index] = element; System.arraycopy(array, index, newArray, index + 1, array.length - index); return newArray; }
SparseArray的get(key)方法:
public E get(int key) { return get(key, null);//調用get(key,null)方法 } public E get(int key, E valueIfKeyNotFound) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key);//二分查找key if (i < 0 || mValues[i] == DELETED) {//沒有找到,或者已經刪除返回null return valueIfKeyNotFound; } else {//找到直接返回i位置的value值 return (E) mValues[i]; } }
SparseArray在put添加數據的時候,會使用二分查找法和之前的key比較當前我們添加的元素的key的大小,然后按照從小到大的順序排列好,所以,SparseArray存儲的元素都是按元素的key值從小到大排列好的。?
而在獲取數據的時候,也是使用二分查找法判斷元素的位置,所以,在獲取數據的時候非常快,比HashMap快的多,因為HashMap獲取數據是通過遍歷Entry[]數組來得到對應的元素。
SparseArray應用場景:
雖說SparseArray性能比較好,但是由于其添加、查找、刪除數據都需要先進行一次二分查找,所以在數據量大的情況下性能并不明顯,將降低至少50%。
滿足下面兩個條件我們可以使用SparseArray代替HashMap:
數據量不大,最好在千級以內
key必須為int類型,這中情況下的HashMap可以用SparseArray代替:
ArrayMapArrayMap是一個
public class ArrayMapextends SimpleArrayMap implements Map {}
構造函數由父類實現:
public ArrayMap() { super(); } public ArrayMap(int capacity) { super(capacity); } public ArrayMap(SimpleArrayMap map) { super(map); }
HashMap內部有一個HashMapEntry[]對象,每一個鍵值對都存儲在這個對象里,當使用put方法添加鍵值對時,就會new一個HashMapEntry對象,而ArrayMap的存儲中沒有Entry這個東西,他是由兩個數組來維護的,mHashes數組中保存的是每一項的HashCode值,mArray中就是鍵值對,每兩個元素代表一個鍵值對,前面保存key,后面的保存value。
int[] mHashes;//key的hashcode值 Object[] mArray;//key value數組
SimpleArrayMap():創建一個空的ArrayMap,默認容量為0,它會跟隨添加的item增加容量。?
SimpleArrayMap(int capacity):指定特定容量ArrayMap;?
SimpleArrayMap(SimpleArrayMap map):指定特定的map;
public SimpleArrayMap() { mHashes = ContainerHelpers.EMPTY_INTS; mArray = ContainerHelpers.EMPTY_OBJECTS; mSize = 0; } ...
ArrayMap 的put(K key, V value):key 不為null
/** * Add a new value to the array map. * @param key The key under which to store the value. Must not be null. If * this key already exists in the array, its value will be replaced. * @param value The value to store for the given key. * @return Returns the old value that was stored for the given key, or null if there * was no such key. */ public V put(K key, V value) { final int hash; int index; //key 不能為null if (key == null) { //key == null,hash為0 hash = 0; index = indexOfNull(); } else {//獲取key的hash值 hash = key.hashCode(); index = indexOf(key, hash);//獲取位置 } //返回index位置的old值 if (index >= 0) { index = (index<<1) + 1; final V old = (V)mArray[index];//old 賦值 value mArray[index] = value; return old; } //否則按位取反 index = ~index; //擴容 System.arrayCopy數據 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; allocArrays(n);//申請數組 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); } freeArrays(ohashes, oarray, mSize);//重新收縮數組,釋放空間 } 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); } //最后 mHashs數組存儲key的hash值 mHashes[index] = hash; mArray[index<<1] = key;//mArray數組相鄰位置存儲key 和value值 mArray[(index<<1)+1] = value; mSize++; return null; }
從最后可以看出:ArrayMap的存儲中沒有Entry這個東西,他是由兩個數組來維護的,mHashes數組中保存的是每一項的HashCode值,mArray中就是鍵值對,每兩個元素代表一個鍵值對,前面保存key,后面的保存value。
ArrayMap 的get(Object key):從Array數組獲得value
/** * Retrieve a value from the array. * @param key The key of the value to retrieve. * @return Returns the value associated with the given key, * or null if there is no such key. */ public V get(Object key) { final int index = indexOfKey(key);//獲得key在Array的存儲位置 return index >= 0 ? (V)mArray[(index<<1)+1] : null;//如果index>=0 取(index+1)上的value值,否則返回null(從上面put知道array存儲是key(index) value(index+1)存儲的) }
ArrayMap 和 HashMap區別:
1.存儲方式不同
HashMap內部有一個HashMapEntry[]對象,每一個鍵值對都存儲在這個對象里,當使用put方法添加鍵值對時,就會new一個HashMapEntry對象 ArrayMap的存儲中沒有Entry這個東西,他是由兩個數組來維護的 mHashes數組中保存的是每一項的HashCode值, mArray中就是鍵值對,每兩個元素代表一個鍵值對,前面保存key,后面的保存value。
2.添加數據時擴容時的處理不一樣
HashMap使用New的方式申請空間,并返回一個新的對象,開銷會比較大 ArrayMap用的是System.arrayCopy數據,所以效率相對要高。
3、ArrayMap提供了數組收縮的功能,只要判斷過判斷容量尺寸,例如clear,put,remove等方法,只要通過判斷size大小觸發到freeArrays或者allocArrays方法,會重新收縮數組,釋放空間。
4、ArrayMap相比傳統的HashMap速度要慢,因為查找方法是二分法,并且當你刪除或者添加數據時,會對空間重新調整,在使用大量數據時,效率低于50%。可以說ArrayMap是犧牲了時間換區空間。但在寫手機app時,適時的使用ArrayMap,會給內存使用帶來可觀的提升。ArrayMap內部還是按照正序排列的,這時因為ArrayMap在檢索數據的時候使用的是二分查找,所以每次插入新數據的時候ArrayMap都需要重新排序,逆序是最差情況;
HashMap ArrayMap SparseArray性能測試對比(轉載 )直接看:http://www.jianshu.com/p/7b9a1b386265測試對比
1.插入性能時間對比?
數據量小的時候,差異并不大(當然了,數據量小,時間基準小,確實差異不大),當數據量大于5000左右,SparseArray,最快,HashMap最慢,乍一看,好像SparseArray是最快的,但是要注意,這是順序插入的。也就是SparseArray和Arraymap最理想的情況。
倒序插入:數據量大的時候HashMap遠超Arraymap和SparseArray,也前面分析一致。?
當然了,數據量小的時候,例如1000以下,這點時間差異也是可以忽略的。
SparseArray在內存占用方面的確要優于HashMap和ArrayMap不少,通過數據觀察,大致節省30%左右,而ArrayMap的表現正如前面說的,優化作用有限,幾乎和HashMap相同。
2.查找性能對比
如何選擇使用1.在數據量小的時候一般認為1000以下,當你的key為int的時候,使用SparseArray確實是一個很不錯的選擇,內存大概能節省30%,相比用HashMap,因為它key值不需要裝箱,所以時間性能平均來看也優于HashMap,建議使用!
2.ArrayMap相對于SparseArray,特點就是key值類型不受限,任何情況下都可以取代HashMap,但是通過研究和測試發現,ArrayMap的內存節省并不明顯,也就在10%左右,但是時間性能確是最差的,當然了,1000以內的如果key不是int 可以選擇ArrayMap。
參考:?
MVC,MVP 和 MVVM 模式如何選擇?
?一招教你讀懂JVM和Dalvik之間的區別
我的Android重構之旅:框架篇
NDK項目實戰—高仿360手機助手之卸載監聽
(Android)面試題級答案(精選版)
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/71252.html
摘要:導語智能手機發展到今天已經有十幾個年頭,手機的軟硬件都已經發生了翻天覆地的變化,特別是陣營,從一開始的一兩百到今天動輒,內存。恰好最近做了內存優化相關的工作,這里也對內存優化相關的知識做下總結。 導語 智能手機發展到今天已經有十幾個年頭,手機的軟硬件都已經發生了翻天覆地的變化,特別是Android陣營,從一開始的一兩百M到今天動輒4G,6G內存。然而大部分的開發者觀看下自己的異常上報系...
閱讀 1675·2021-11-15 11:37
閱讀 3408·2021-09-28 09:44
閱讀 1649·2021-09-07 10:15
閱讀 2784·2021-09-03 10:39
閱讀 2687·2019-08-29 13:20
閱讀 1291·2019-08-29 12:51
閱讀 2204·2019-08-26 13:44
閱讀 2125·2019-08-23 18:02