数据结构 —线性表，LruCache实现原理

逻辑结构和物理结构

物理结构：是指数据的逻辑结构在计算机中的存储形式

• 顺序存储结构

  
  顺序存储

• 链式存储结构

  
  链式存储

逻辑结构 ：是指数据对象中数据元素之间的相互关系

• 集合结构

  
  集合关系

• 线性结构

  
  线性关系

• 树形结构

  
  树形关系

• 图形结构

  
  图形关系

线性表：零个或多个元素的有序序列，逻辑结构是线性结构

表现方式：

• 数组：顺序存储+线性关系

• 链表：链式存储+线性关系

线性表	优点	缺点
数组（顺序线性表 ）	查找快，存储空间连续	增删慢，长度固定
链表（链式线性表）	增删快	查找慢，存储空间不连续

LRUCache

这是安卓的一个缓存类，有固定容量大小的队列（LinkedHashMap），如果一个元素被访问了，就会移动到队列的头部，如果向一个满的LRUCache中添加，队列的最后一个元素会被丢弃；

成员变量

    //  底层数据结构
    private final LinkedHashMap<K, V> map;

    /** Size of this cache in units. Not necessarily the number of elements. */
    private int size;
    private int maxSize;

构造

    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);
    }

put（）

    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);
            //  将K，V存到map里，如果此K之前已经存过，就返回给previous 变量
            previous = map.put(key, value);
            if (previous != null) {
                size -= safeSizeOf(key, previous);
            }
        }

        if (previous != null) {
            entryRemoved(false, key, previous, value);
        }
        //  清理内存
        trimToSize(maxSize);
        return previous;
    }


   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!");
                }
                //  如果队列的大小没有超过规定的容量
                if (size <= maxSize) {
                    break;
                }
                //   超过了，开始丢弃least recently  used
                Map.Entry<K, V> toEvict = null;
                //  获取最后 一个Entry
                for (Map.Entry<K, V> entry : map.entrySet()) {
                    toEvict = entry;
                }

                if (toEvict == null) {
                    break;
                }

                key = toEvict.getKey();
                value = toEvict.getValue();
                //  在map去除最后一个entry
                map.remove(key);
                size -= safeSizeOf(key, value);
                evictionCount++;
            }

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

get()

    public final V get(K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }

        V mapValue;
        synchronized (this) {
            //   移动到队列的头部在LinkedHashMap中实现
            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;
        }
    }

LruCache的特点：

• 底层是队列（LinkedHashMap）
• 线程安全的

LRU算法 + LruHashMap

1. 新数据插入到链表头部
2. 当缓存命中(即缓存数据被访问)，数据要移到表头
3. 当链表满的时候，将链表尾部的数据丢弃

public class LruLinkedList<T> {

    Node head;
    int size;
    int max = 5;

    public void lruAdd(T data){
        if (size >= 5 ){
            throw new IndexOutOfBoundsException("");
        }
        Node node = new Node(data);
        if (head == null){
            head = node;
        }else {
            node.next = head;
        }
        size++;
    }

    public T lruGet(int index){
        if (!(index>=0 && index<size)){
            throw new IndexOutOfBoundsException("");
        }
        Node temp = head;
        Node pre = head;
        for (int i = 0;i<index;i++){
            pre = temp;
            temp = temp.next;
        }
        // 移动到链表头
        pre.next = temp.next;
        temp.next = head;
        head = temp;

        return head.data;
    }

    public T lruRemove(){
        if (size<=0){
            throw new IndexOutOfBoundsException("");
        }
        Node temp = head;
        Node pre = head;
        while (temp.next!=null){
            pre = temp;
            temp = temp.next;
        }
        pre.next = null;

        return temp.data;
    }





    class Node{
        T data;
        Node  next;

        public Node(T data) {
            this.data = data;
        }
    }
}