說說Android LRU緩存算法實現學習筆記(一)

在我們的手機應用開發時候，我們經常會遇到大數據訪問的時候，我們通常會考慮以下幾個方面的情況。一、手機內存的限制還必須保證應用反應的流暢；二、盡量小的流量消耗，不然，你的應用流暢度再好體驗再好，用戶還是會毫不猶豫的卸載掉你的應用。大數據量訪問的情況下，數據緩存是我們一定會考慮到的解決方案。而作為緩存，我們很重要的會考慮以下幾點：1.訪問速度；2.逐出舊的緩存策略；3.最好還能考慮到一定的並發度。這篇我們主要說說LRU策略的緩存算法實現，我們就用圖片緩存為例來談談Android應用開發中的緩存實現。

首先我們來看看谷歌官方的推薦的緩存：在Android3.0加入的LruCache和 DiskLruCache（硬盤緩存結構）類。我們從代碼的實現知道，LruCache和DiskLruCache緩存的實現都是基於JDK的LinkedHashMap集合來實現。下面我們來從LinkedHashMap的源碼的分析來開始學習。

通過源碼我們知道，LinkedHashMap是繼承HashMap,底層結構不僅使用HashMap來保存元素，同時通過繼承HashMapEntry 實現雙向鏈表的結構來關聯其他的元素。我們先來看LInkedHashMap的節點實現：

    /**
     * LinkedHashMap entry.
     */
    private static class Entry extends HashMap.Entry {
        // These fields comprise the doubly linked list used for iteration.
        Entry before, after;

我們再來看看LinkedHashMap的初始化，我們看到構造函數參數最多的情況：

/**
     * Constructs an empty LinkedHashMap instance with the
     * specified initial capacity, load factor and ordering mode.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @param  accessOrder     the ordering mode - true for
     *         access-order, false for insertion-order
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public LinkedHashMap(int initialCapacity,
			 float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder; //accessOrder指定排序，默認為false,為fasle的時候，插入順序排序，為true時候，訪問順序排序
    }

/**
     * Called by superclass constructors and pseudoconstructors (clone,
     * readObject) before any entries are inserted into the map.  Initializes
     * the chain.
     */
    void init() {
        header = new Entry(-1, null, null, null);
        header.before = header.after = header;
    }

/**
     * This override alters behavior of superclass put method. It causes newly
     * allocated entry to get inserted at the end of the linked list and
     * removes the eldest entry if appropriate.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        createEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed, else grow capacity if appropriate
        Entry eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        } else {
            if (size >= threshold)
                resize(2 * table.length);
        }
    }

    /**
     * This override differs from addEntry in that it doesn't resize the
     * table or remove the eldest entry.
     */
    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry old = table[bucketIndex];
	Entry e = new Entry(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
    }

 /**
         * Inserts this entry before the specified existing entry in the list.
         */
        private void addBefore(Entry existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

protected boolean removeEldestEntry(Map.Entry eldest) {
        return false;
    }

	   map.put("22", "xxx"); 

public V get(Object key) {
        Entry e = (Entry)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }

 /**
         * This method is invoked by the superclass whenever the value
         * of a pre-existing entry is read by Map.get or modified by Map.set.
         * If the enclosing Map is access-ordered, it moves the entry
         * to the end of the list; otherwise, it does nothing.
         */
        void recordAccess(HashMap m) {
            LinkedHashMap lm = (LinkedHashMap)m;
            if (lm.accessOrder) { //此處的判斷LinkedHashMap的排序順序
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

put.get("15");//我們假設key為15對應的value為"bbb"

private abstract class LinkedHashIterator implements Iterator {
        Entry nextEntry    = header.after;
        Entry lastReturned = null;

        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        int expectedModCount = modCount;

        public boolean hasNext() {
            return nextEntry != header;
        }

        public void remove() {
            if (lastReturned == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            LinkedHashMap.this.remove(lastReturned.key);
            lastReturned = null;
            expectedModCount = modCount;
        }

        Entry nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (nextEntry == header)
                throw new NoSuchElementException();

            Entry e = lastReturned = nextEntry;
            nextEntry = e.after; //此處我們可知我們的迭代器實現訪問節點的after引用指向的節點。
            return e;
        }
    }