LruCache里为什么用LinkedHashMap,HashMap可以吗?

近期有朋友准备面试,在群上我们会讨论一些面试题,每次我都会受到暴击,很多题目都答不上来。平时开发中,谷歌、第三方用得很溜,貌似解决了问题,可回想起来,技术没什么长进。比如我知道图片是用三级缓存,用的是Lru算法,可是如果不用glide,手写一个图片缓存工具类,我发现自己思路并不清晰。以写内存缓存为例,我会想到用强引用缓存,软引用缓存去实现,那么强引用,软引用具体使用哪些类去实现缓存是最好的?这个我都要去查一下,知道可以用LruCache,LinkedHashMap去缓存数据,LruCache为什么选择LinkedHashMap,而不是选择其它的存储类?多问几个为什么,就发现自己什么都不知道。也明白为什么面试的时候,很多公司注重底层的实现原理和算法这些知识。只有明白实现原理,才学到了精髓,才能欣赏高手写的加载框架,才能在遇到问题的时候对症下药,而不是像无头苍蝇一样把每一个网上答案试一遍,改好了都还不知道为什么。
为了搞明白上述的一系列问题,我看了关于HashMap,LinkedHashMap,Lru,以及内存缓存实现的相关内容,现在将这些整理成文章。

说在前面的话

看有关于HashMap和LinkedHashMap底层原理的文章的之前,最好先把数组、单链表、双链表、哈希表、哈希函数、哈希算法这些基础的知识回顾一遍,这样对理解HashMap和LinkedHashMap有很大的帮助。本篇文章只是将HashMap、LinkedHashMap以及缓存的实现串起来讲了一遍,并没有全面的去讲解这些知识点,看完以后,你就知道为什么LruCache里用的是LinkedHashMap。

HashMap

HashMap是基于数组来实现哈希表的,主干是数组。数组中新增或查找某个元素,通过数组index(也就是索引),一次定位就可完成操作。
数组就相当于内存储空间,数组的index就好比内存的地址。HashMap的每个记录就是一个Entry<K, V>对象,每一个Entry包含一个key-value键值对,数组里存储的就是这些对象。现在我们看看是怎么样计算出每一个存储对象的内存地址的。

 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

Hash值=(hashcode)^(hashcode >>> 16),Hashcode予hashcode自己向右位移16位的异或运算,利用key的hashcode计算出Hash值。下一步就是利用Hash值计算出下标。

LruCache里为什么用LinkedHashMap,HashMap可以吗?

上面的代码是put键值对时候的源码,框起来红色部分的代码就是得到下标的代码,看起来有些难懂,重写一下

i = (n - 1) & hash;//hash是上一步计算出来的hash值,n是底层数组的长度,用&运算符计算出i的值 
p = tab[i];//用计算出来的i的值作为下标从数组中元素
if(p == null){//如果这个元素为null,用key,value构造一个Node对象放入数组下标为i的位置
     tab[i] = newNode(hash, key, value, null);
}

i就是我们通过hash值算出来的下标,也就是存储的位置。上面我们看到源码的if语句,当tab[i]为null的时候,就直接存储对象,那么不为null呢?相关的源码如下

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
      ......
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
             // 找到数组元素,hash相等同时key相等,则直接覆盖
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 该数组元素在链表长度>8后形成红黑树结构的对象
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 该数组元素hash相等,key不等,同时链表长度<8.进行遍历寻找元素,有就覆盖无则新建
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        // 新建链表中数据元素
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 链表长度>=8 结构转为 红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
复制代码

先忽略红黑树的转换,总结一下上面代码:

1.判断当前确定的索引位置,是否存在hashcode和key元素都相同的,如果存在相同的hashcode和相同的key的元素,那么新值覆盖原来的旧值,并返回旧值
2.如果存在相同的hashcode,那么他们确定的索引位置就相同,这时判断他们的key是否相同,如果不相同,这时就是产生了hash冲突
3.产生了hash冲突,就引入了单链表。进行遍历寻找元素,有就覆盖,没有就新建。

以上是存储entry,过程比较复杂。获取数据相对来说比较简单,基本流程如下:

1.通过key的hashCode和寻址算法得到数组下标,若数组元素中的key和hash相等,则直接返回。
2.如果不相等,同时存在链表元素,就遍历链表元素进行匹配返回

HashMap没有发生hash冲突,没有形成单链表,hashmap查找元素很快,get()方法能够直接定位到元素。出现单链表后,定位到的单个bucket 里存储的不是一个 Entry,而是一个 Entry 链,系统只能按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止。如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中),那系统必须循环到最后才能找到该元素。为了解决链表过长导致的性能问题,JDK1.8在JDK1.7的基础上增加了红黑树来进行优化。当链表超过8时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能,其中会用到红黑树的插入、删除、查找等算法。

放上一张HashMap的结构图,网上找来的图

LruCache里为什么用LinkedHashMap,HashMap可以吗?

 

我们可以将数组里的每一个index定位的位置看着是放着一个个的bucket,bucket里可能装着一个Entry,也可能装的是Entry链。
总结一下HashMap特性
1.HashMap存储键值对实现 快速存取,允许为null。

2.key值 不可重复。

3.底层是hash表, 不保证有序(比如插入的顺序)

LinkedHashMap

上面说到HashMap可以实现快速存取,但是是无序的,遍历HashMap所得到的元素顺序并不是它们最初放置到HashMap的顺序。在我们的实际应用中,需要做到快速存取,又需要是有序的,这个时候LinkedHashMap就是很好的选择。LinkedHashMap是HashMap子类,有序(插入顺序或者是访问顺序)、元素的增加、修改和删除效率都比较高。
LinkedHashMap存储的结构是用了双重链表。在数据的操作上和HashMap是一样的。差别比较大的就是Entry,来看看LinkedHashMap的Entry里面的属性

1、K key

2、V value

3、Entry<K, V> next

4、int hash

5、Entry<K, V> before

6、Entry<K, V> after
其中前面四个,红色部分是继承HashMap.Entry的;后面两个是LinkedHashMap独有的。next是用于维护HashMap指定table位置上连接的Entry的顺序的,before、after是用于维护Entry插入的先后顺序的。LinkedHashMap的结构图如下:

LruCache里为什么用LinkedHashMap,HashMap可以吗?

LinkedHashMap中没有什么操作数据结构的方法,也就是说LinkedHashMap操作数据结构(比如put一个数据),和HashMap操作数据的方法完全一样,就是细节上有一些的不同,在这里就不作详细的叙述,可以自行去看源码。如果这部分看得不是很明白,建议先去看双重链表的一些知识。LinkedHashMap是HashMap+LinkedList的实现方式,HashMap维护数据结构,LinkList的方式维护数据插入顺序。

图片缓存

上面的内容介绍HashMap主要是为了理解LinkedHashMap,用简单的话总结LinkedHashMap的优点,就是元素的增加、修改和删除效率都比较高,并且是有序的,顺序可以是插入顺序或者是访问顺序。LinkedHashMap被用在了LruCache类中,LruCache内部实现原理就是基于LinkedHashMap来实现的,核心就是Lru算法。软引用缓存也可以使用LinkedHashMap来存取数据。说一下图片缓存的简单思路,大家就明白LinkedHashMap的优势。

1.强引用缓存满的时候,根据LRU算法把最近没有被使用的图片转入软引用缓存

2.当软引用数量大于20(数量自己定)的时候,最旧的软引用将会被从链式哈希表中移出

因为LinkedHashMap是有序的,顺序是可以是插入顺序和访问顺序,所以把最近没有被使用的图片找出来是很简单的,只需要每次在强引用中访问并且找到了的图片,移到LinkedHashMap的最前面,这样越是前面的就越是最近被使用过的,当内存满时,从LinkedHashMap最后面取图片,就是最近没有被使用的图片。LinkedHashMap用来进行软引用的存储也是同理,可以很容易的将旧的软引用从链式哈希表中移出。 LruCache内部实现用LinkedHashMap,这样保证插入时候的数据和取出来的时候数据的顺序的一致性,并且能有不错的效率

现在图片缓存都有很强大的第三方帮我们解决,但是在这里还是想粘贴一下任玉刚大神写的内存缓存的代码,我个人觉得很有学习的必要。

public class ImageMemoryCache {
    private static final String TAG = "ImageMemoryCache";
    private static LruCache<String, Bitmap> mLruCache;//强引用缓存
    private static LinkedHashMap<String , SoftReference<Bitmap>> mSoftCache; //软引用缓存
    private static final int LRU_CACHE_SIZE = 4 * 1024 * 1024;//强引用缓存
    private static final int SOFT_CACHE_NUM = 20;//软引用缓存个数

    //在这里分别初始化强引用缓存和弱引用缓存
    public ImageMemoryCache(){
        mLruCache = new LruCache<String ,Bitmap>(LRU_CACHE_SIZE){
            @Override
            protected int sizeOf(String key, Bitmap value) {
                if (value != null){
                    return value.getRowBytes() * value.getHeight();
                }
                return 0;
            }

            @Override
            protected void entryRemoved(boolean evicted, String key, Bitmap oldValue, Bitmap newValue) {
                super.entryRemoved(evicted, key, oldValue, newValue);
                if (oldValue != null){
                    //强引用缓存容量满的时候,会根据LRU算法把最近没有被使用的图片转入此软引用缓存
                    Log.d(TAG,"LruCache is full,move to SoftReferenceCache");
                    mSoftCache.put(key,new SoftReference<Bitmap>(oldValue));
                }
            }
        };
        mSoftCache = new LinkedHashMap<String, SoftReference<Bitmap>>(SOFT_CACHE_NUM, 0.7f,true){
            private static final long serialVersionUID = 1L;
            //当软引用数量大于20的时候,最旧的软引用将会被从链式哈希表中移出

            @Override
            protected boolean removeEldestEntry(Entry<String, SoftReference<Bitmap>> eldest) {
                if (size() > SOFT_CACHE_NUM){
                    Log.d(TAG,"shoudle remove the eldest from SoftReference");
                    return true;
                }
                return false;
            }
        };
    }
    //从缓存中获取图片
    public Bitmap getBitmapFromMemory(String url){
        Bitmap bitmap;
        //先从强引用中获取
        synchronized (mLruCache){
            bitmap = mLruCache.get(url);
            if (bitmap != null){
                //如果找到的话,把元素移到LinkedHashMap的最前面,从而保证在LRU算法中是最后被删除
                mLruCache.remove(url);
                mLruCache.put(url,bitmap);
                Log.d(TAG,"get bmp from LruCache,url =" +url);
                return bitmap;
            }

        }
        //如果强引用缓存中找不到,到软引用缓存中找,找到后把它从软引用中移到强引用中
        synchronized (mSoftCache){
            SoftReference<Bitmap> bitmapReference = mSoftCache.get(url);
            if (bitmapReference != null){
                bitmap = bitmapReference.get();
                if (bitmap != null){
                    //将图片移回LruCache
                    mLruCache.put(url,bitmap);
                    mSoftCache.remove(url);
                    Log.d(TAG,"get bmp from SoftRefrenceCache, url = "+url);
                    return bitmap;
                }else {
                    mSoftCache.remove(url);
                }
            }
        }
     return null;
    }
    //添加图片到缓存
    public void addBitmapToMemory(String url,Bitmap bitmap){
        if (bitmap != null){
            synchronized (mLruCache){
                mLruCache.put(url,bitmap);
            }
        }
    }
    public void clearCache(){
        mSoftCache.clear();
    }

}
复制代码

总结

Android有很多的知识,像HashMap、LinkedHashMap这些会重复的去看有关的底层实现,但是过了一段时间又忘记了,如果结合实际的例子去理解,就会更容易理解它的优势。很多第三方给我们提供了很大的帮助,不止要会用,还要去理解是如何实现的,为什么选择这种方式实现?多想为什么并且去弄懂,也许做到这样,面试时候就能侃侃而谈了。


作者:honey饼
链接:https://juejin.cn/post/6844904120462245901
 

上一篇:05_LinkedHashMap


下一篇:Map-LinkedHashMap源码笔记