簡(jiǎn)介
- HashMap：數(shù)組+單向鏈表
- LinkedHashMap： HashMap + 雙向循環(huán)鏈表
- LruCache：基于
HashMap實(shí)現(xiàn)原理
Paste_Image.png
Paste_Image.png
具體參考這篇文章： HashMap實(shí)現(xiàn)原理分析
LinkedMap實(shí)現(xiàn)原理
-
原理圖解
第一張圖是LinkedHashMap的全部數(shù)據(jù)結(jié)構(gòu)，包含散列表和循環(huán)雙向鏈表，由于循環(huán)雙向鏈表線條太多了，不好畫，簡(jiǎn)單的畫了一個(gè)節(jié)點(diǎn)(黃色圈出來(lái)的)示意一下，注意左邊的紅色箭頭引用為Entry節(jié)點(diǎn)對(duì)象的next引用(散列表中的單鏈表)，綠色線條為Entry節(jié)點(diǎn)對(duì)象的before, after引用(循環(huán)雙向鏈表的前后引用)；
第二張圖專門把循環(huán)雙向鏈表抽取出來(lái)，直觀一點(diǎn)，注意該循環(huán)雙向鏈表的頭部存放的是最久訪問(wèn)的節(jié)點(diǎn)或最先插入的節(jié)點(diǎn)，尾部為最近訪問(wèn)的或最近插入的節(jié)點(diǎn)，迭代器遍歷方向是從鏈表的頭部開始到鏈表尾部結(jié)束，在鏈表尾部有一個(gè)空的header節(jié)點(diǎn)，該節(jié)點(diǎn)不存放key-value內(nèi)容，為L(zhǎng)inkedHashMap類的成員屬性，循環(huán)雙向鏈表的入口；
LinkedHashMap繼承于HashMap，但是它重新定義了數(shù)組中保存的元素Entry，該Entry除了保存當(dāng)前對(duì)象的引用外，還保存了其上一個(gè)元素before和下一個(gè)元素after的引用，從而在哈希表的基礎(chǔ)上又構(gòu)成了雙向鏈接列表, 它使用了一個(gè)雙向鏈表來(lái)存儲(chǔ)Map中的Entry順序關(guān)系，這種順序有兩種，一種是LRU順序，一種是插入順序。所以，對(duì)于get、put、remove等操作，LinkedHashMap除了要做HashMap做的事情，還做些調(diào)整Entry順序鏈表的工作。
特點(diǎn)：
可以按照從近期訪問(wèn)最少到近期訪問(wèn)最多的順序（即訪問(wèn)順序）來(lái)排序，也可以按照插入順序排序；這個(gè)特性有利于實(shí)現(xiàn)LruCache。按插入排序（默認(rèn)）
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
- 按訪問(wèn)排序
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
LruCache分析
LruCache中將LinkedHashMap的順序設(shè)置為L(zhǎng)RU順序來(lái)實(shí)現(xiàn)LRU緩存，每次調(diào)用get(也就是從內(nèi)存緩存中取圖片)，則將該對(duì)象移到鏈表的尾端。調(diào)用put插入新的對(duì)象也是存儲(chǔ)在鏈表尾端，這樣當(dāng)內(nèi)存緩存達(dá)到設(shè)定的最大值時(shí)，將鏈表頭部的對(duì)象（近期最少用到的）移除。
LruCache源碼解析
/*
* Copyright (C) 2011 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package android.support.v4.util;
import java.util.LinkedHashMap;
import java.util.Map;
/**
* Static library version of {@link android.util.LruCache}. Used to write apps
* that run on API levels prior to 12. When running on API level 12 or above,
* this implementation is still used; it does not try to switch to the
* framework's implementation. See the framework SDK documentation for a class
* overview.
*/
public class LruCache<K, V> {
private final LinkedHashMap<K, V> map;
/** Size of this cache in units. Not necessarily the number of elements. */
private int size; //當(dāng)前cache的大小
private int maxSize; //cache最大大小
private int putCount; //put的次數(shù)
private int createCount; //create的次數(shù)
private int evictionCount; //回收的次數(shù)
private int hitCount; //命中的次數(shù)
private int missCount; //未命中次數(shù)
/**
* @param maxSize for caches that do not override {@link #sizeOf}, this is
* the maximum number of entries in the cache. For all other caches,
* this is the maximum sum of the sizes of the entries in this cache.
*/
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
//將LinkedHashMap的accessOrder設(shè)置為true來(lái)實(shí)現(xiàn)LRU
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
/**
* Returns the value for {@code key} if it exists in the cache or can be
* created by {@code #create}. If a value was returned, it is moved to the
* head of the queue. This returns null if a value is not cached and cannot
* be created.
* 通過(guò)key獲取相應(yīng)的item，或者創(chuàng)建返回相應(yīng)的item。相應(yīng)的item會(huì)移動(dòng)到隊(duì)列的尾部，
* 如果item的value沒(méi)有被cache或者不能被創(chuàng)建，則返回null。
*/
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
mapValue = map.get(key);
if (mapValue != null) {
//mapValue不為空表示命中，hitCount+1并返回mapValue對(duì)象
hitCount++;
return mapValue;
}
missCount++; //未命中
}
/*
* Attempt to create a value. This may take a long time, and the map
* may be different when create() returns. If a conflicting value was
* added to the map while create() was working, we leave that value in
* the map and release the created value.
* 如果未命中，則試圖創(chuàng)建一個(gè)對(duì)象，這里create方法返回null,并沒(méi)有實(shí)現(xiàn)創(chuàng)建對(duì)象的方法
* 如果需要事項(xiàng)創(chuàng)建對(duì)象的方法可以重寫create方法。因?yàn)閳D片緩存時(shí)內(nèi)存緩存沒(méi)有命中會(huì)去
* 文件緩存中去取或者從網(wǎng)絡(luò)下載，所以并不需要?jiǎng)?chuàng)建。
*/
V createdValue = create(key);
if (createdValue == null) {
return null;
}
//假如創(chuàng)建了新的對(duì)象，則繼續(xù)往下執(zhí)行
synchronized (this) {
createCount++;
//將createdValue加入到map中，并且將原來(lái)鍵為key的對(duì)象保存到mapValue
mapValue = map.put(key, createdValue);
if (mapValue != null) {
// There was a conflict so undo that last put
//如果mapValue不為空，則撤銷上一步的put操作。
map.put(key, mapValue);
} else {
//加入新創(chuàng)建的對(duì)象之后需要重新計(jì)算size大小
size += safeSizeOf(key, createdValue);
}
}
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
//每次新加入對(duì)象都需要調(diào)用trimToSize方法看是否需要回收
trimToSize(maxSize);
return createdValue;
}
}
/**
* Caches {@code value} for {@code key}. The value is moved to the head of
* the queue.
*
* @return the previous value mapped by {@code key}.
*/
public final V put(K key, V value) {
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
putCount++;
size += safeSizeOf(key, value); //size加上預(yù)put對(duì)象的大小
previous = map.put(key, value);
if (previous != null) {
//如果之前存在鍵為key的對(duì)象，則size應(yīng)該減去原來(lái)對(duì)象的大小
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, value);
}
//每次新加入對(duì)象都需要調(diào)用trimToSize方法看是否需要回收
trimToSize(maxSize);
return previous;
}
/**
* @param maxSize the maximum size of the cache before returning. May be -1
* to evict even 0-sized elements.
* 此方法根據(jù)maxSize來(lái)調(diào)整內(nèi)存cache的大小，如果maxSize傳入-1，則清空緩存中的所有對(duì)象
*/
private void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName()
+ ".sizeOf() is reporting inconsistent results!");
}
//如果當(dāng)前size小于maxSize或者map沒(méi)有任何對(duì)象,則結(jié)束循環(huán)
if (size <= maxSize || map.isEmpty()) {
break;
}
//移除鏈表頭部的元素，并進(jìn)入下一次循環(huán)
Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++; //回收次數(shù)+1
}
entryRemoved(true, key, value, null);
}
}
/**
* Removes the entry for {@code key} if it exists.
*
* @return the previous value mapped by {@code key}.
* 從內(nèi)存緩存中根據(jù)key值移除某個(gè)對(duì)象并返回該對(duì)象
*/
public final V remove(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V previous;
synchronized (this) {
previous = map.remove(key);
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, null);
}
return previous;
}
/**
* Called for entries that have been evicted or removed. This method is
* invoked when a value is evicted to make space, removed by a call to
* {@link #remove}, or replaced by a call to {@link #put}. The default
* implementation does nothing.
*
* <p>The method is called without synchronization: other threads may
* access the cache while this method is executing.
*
* @param evicted true if the entry is being removed to make space, false
* if the removal was caused by a {@link #put} or {@link #remove}.
* @param newValue the new value for {@code key}, if it exists. If non-null,
* this removal was caused by a {@link #put}. Otherwise it was caused by
* an eviction or a {@link #remove}.
*/
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}
/**
* Called after a cache miss to compute a value for the corresponding key.
* Returns the computed value or null if no value can be computed. The
* default implementation returns null.
*
* <p>The method is called without synchronization: other threads may
* access the cache while this method is executing.
*
* <p>If a value for {@code key} exists in the cache when this method
* returns, the created value will be released with {@link #entryRemoved}
* and discarded. This can occur when multiple threads request the same key
* at the same time (causing multiple values to be created), or when one
* thread calls {@link #put} while another is creating a value for the same
* key.
*/
protected V create(K key) {
return null;
}
private int safeSizeOf(K key, V value) {
int result = sizeOf(key, value);
if (result < 0) {
throw new IllegalStateException("Negative size: " + key + "=" + value);
}
return result;
}
/**
* Returns the size of the entry for {@code key} and {@code value} in
* user-defined units. The default implementation returns 1 so that size
* is the number of entries and max size is the maximum number of entries.
*
* <p>An entry's size must not change while it is in the cache.
* 用來(lái)計(jì)算單個(gè)對(duì)象的大小，這里默認(rèn)返回1，一般需要重寫該方法來(lái)計(jì)算對(duì)象的大小
* xUtils中創(chuàng)建LruMemoryCache時(shí)就重寫了sizeOf方法來(lái)計(jì)算bitmap的大小
* mMemoryCache = new LruMemoryCache<MemoryCacheKey, Bitmap>(globalConfig.getMemoryCacheSize()) {
* @Override
* protected int sizeOf(MemoryCacheKey key, Bitmap bitmap) {
* if (bitmap == null) return 0;
* return bitmap.getRowBytes() * bitmap.getHeight();
* }
* };
*
*/
protected int sizeOf(K key, V value) {
return 1;
}
/**
* Clear the cache, calling {@link #entryRemoved} on each removed entry.
* 清空內(nèi)存緩存
*/
public final void evictAll() {
trimToSize(-1); // -1 will evict 0-sized elements
}
/**
* For caches that do not override {@link #sizeOf}, this returns the number
* of entries in the cache. For all other caches, this returns the sum of
* the sizes of the entries in this cache.
*/
public synchronized final int size() {
return size;
}
/**
* For caches that do not override {@link #sizeOf}, this returns the maximum
* number of entries in the cache. For all other caches, this returns the
* maximum sum of the sizes of the entries in this cache.
*/
public synchronized final int maxSize() {
return maxSize;
}
/**
* Returns the number of times {@link #get} returned a value.
*/
public synchronized final int hitCount() {
return hitCount;
}
/**
* Returns the number of times {@link #get} returned null or required a new
* value to be created.
*/
public synchronized final int missCount() {
return missCount;
}
/**
* Returns the number of times {@link #create(Object)} returned a value.
*/
public synchronized final int createCount() {
return createCount;
}
/**
* Returns the number of times {@link #put} was called.
*/
public synchronized final int putCount() {
return putCount;
}
/**
* Returns the number of values that have been evicted.
*/
public synchronized final int evictionCount() {
return evictionCount;
}
/**
* Returns a copy of the current contents of the cache, ordered from least
* recently accessed to most recently accessed.
*/
public synchronized final Map<K, V> snapshot() {
return new LinkedHashMap<K, V>(map);
}
@Override public synchronized final String toString() {
int accesses = hitCount + missCount;
int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0;
return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]",
maxSize, hitCount, missCount, hitPercent);
}
}
