# LruCache源码解析

Posted by jjx on August 14, 2016

/**
* @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;
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}


• LruCache所占的内存大小是可以自定义的。

/**
* Constructs a new {@code LinkedHashMap} instance with the specified
* capacity, load factor and a flag specifying the ordering behavior.
*
* @param initialCapacity
*            the initial capacity of this hash map.
* @param accessOrder
*            {@code true} if the ordering should be done based on the last
*            access (from least-recently accessed to most-recently
*            accessed), and {@code false} if the ordering should be the
*            order in which the entries were inserted.
* @throws IllegalArgumentException
*             when the capacity is less than zero or the load factor is
*             less or equal to zero.
*/
int initialCapacity, float loadFactor, boolean accessOrder) {
init();
this.accessOrder = accessOrder;
}


/**
* Constructs a new {@code HashMap} instance with the specified capacity and
*
* @param capacity
*            the initial capacity of this hash map.
* @throws IllegalArgumentException
*                when the capacity is less than zero or the load factor is
*                less or equal to zero or NaN.
*/
public HashMap(int capacity, float loadFactor) {
this(capacity);

}

/*
* Note that this implementation ignores loadFactor; it always uses
* a load factor of 3/4. This simplifies the code and generally
* improves performance.
*/
}


private void writeObject(ObjectOutputStream stream) throws IOException {
ObjectOutputStream.PutField fields = stream.putFields();
stream.writeFields();

stream.writeInt(table.length); // Capacity
stream.writeInt(size);
for (Entry<K, V> e : entrySet()) {
stream.writeObject(e.getKey());
stream.writeObject(e.getValue());
}
}


 /**
* The default load factor. Note that this implementation ignores the
* load factor, but cannot do away with it entirely because it's
* mentioned in the API.
*
* <p>Note that this constant has no impact on the behavior of the program,
* but it is emitted as part of the serialized form. The load factor of
* .75 is hardwired into the program, which uses cheap shifts in place of
* expensive division.
*/
static final float DEFAULT_LOAD_FACTOR = .75F;


The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

if (accessOrder)


private void makeTail(LinkedEntry<K, V> e) {
e.prv.nxt = e.nxt;
e.nxt.prv = e.prv;

e.prv = oldTail;
modCount++;
}


get()

/**
* 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.
*/
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) {
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.
*/

V createdValue = create(key);
if (createdValue == null) {
return null;
}

synchronized (this) {
createCount++;
mapValue = map.put(key, createdValue);

if (mapValue != null) {
// There was a conflict so undo that last put
map.put(key, mapValue);
} else {
size += safeSizeOf(key, createdValue);
}
}

if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
trimToSize(maxSize);
return createdValue;
}
}


/**
* Remove the eldest entries until the total of remaining entries is at or
* below the requested size.
*
* @param maxSize the maximum size of the cache before returning. May be -1
*            to evict even 0-sized elements.
*/
public 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!");
}

if (size <= maxSize) {
break;
}

Map.Entry<K, V> toEvict = map.eldest();
if (toEvict == null) {
break;
}

key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}

entryRemoved(true, key, value, null);
}
}


/**
* Returns the eldest entry in the map, or {@code null} if the map is empty.
* @hide
*/
public Entry<K, V> eldest() {
return eldest != header ? eldest : null;
}


• size >= 0
• !(map.isEmpty() && size != 0)
• size > maxSize
• map.isEmpty == true

put()

/**
* 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);
previous = map.put(key, value);
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}

if (previous != null) {
entryRemoved(false, key, previous, value);
}

trimToSize(maxSize);
return previous;
}