上一篇文章研究P时,将到cache机制,采用的是LRUCache。今天我们就来讲一下LRUCache:
LruCache是android提供的一个缓存工具类,其算法是最近最少使用算法。它把最近使用的对象用“强引用”存储在LinkedHashMap中,并且把最近最少使用的对象在缓存值达到预设定值之前就从内存中移除。
那我们来看看 LinkedHashMap:
LinkedHashMap = Linked + HashMap
之前对于Linked的理解,不是很深刻。在深入的看了LinkedHashMap之后,才知道,Linked是一种结构,这种结构是可以放到很多地方的,比如说 LinkedPeople、LinkedBill、、、等等。Linked只是一种数据的组织形式。Linked有固定的几套(单链表、循环链表、双向链表)写法(不同形式的链表结构),看源码基本就是增删改查的操作。
那为什么会有这种结构呢?
像普通的数据需要排列起来,比如:12345678,一个一个排列,我们称为线性表。如果删除其中的3,那么45678就得往前移一位。插入一位,也是需要后面的数往后移动一位的。这样整块数据移动对于系统的开销是很大的。那么有没有一种结构,可以允许表可以不连续存储呢?聪明的程序员便设计了更简单的一种数据结构,让删除和插入的操作更简单。那就是链表,链表由一系列不必在内存中相连的结构组成,每一个结构均含有表元素和指向包含该元素后继元的结构的指针。最后一个单元的的next指针指向NULL。
看LinkedHashMap的源码可以知道,它继承与HashMap
,基于散列表实现,区别是,LinkedHashMap内部多了一个双向循环链表的维护,该链表是有序的,可以按元素插入顺序或元素最近访问顺序(LRU)排列,
简单地说:LinkedHashMap=散列表+循环双向链表
我们看一下循环列表和双向链表的定义:
双向链表:即是这样一个有序的结点序列,每个链表元素既有指向下一个元素的指针,又有指向前一个元素的指针,其中每个结点都有两种指针,即left和right。left指针指向左边结点,right指针指向右边结点。
961648943-54ad33c503d42_articlex.png循环链表:指的是在单向链表和双向链表的基础上,将两种链表的最后一个结点指向第一个结点从而实现循环。
4182362326-54ad32f7a593b_articlex.png//再看HashMap 继承与AbstractMap,AbstractMap实现Map接口。
网友评论