C/C++教程
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值计算出下标。
上面的代码是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的结构图，网上找来的图
我们可以将数组里的每一个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的结构图如下：
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
-
MATLAB 中 A(7)=[];什么意思？-icode9专业技术文章分享11-26
-
UniApp 中如何实现使用输入法时保持页面列表不动的效果？-icode9专业技术文章分享11-26
-
在 UniApp 中怎么实现输入法弹出时禁止页面向上滚动？-icode9专业技术文章分享11-26
-
WebSocket是什么，怎么使用？-icode9专业技术文章分享11-26
-
页面有多个ref 要动态传入怎么实现？-icode9专业技术文章分享11-26
-
在 UniApp 中实现一个底部输入框的常见方法有哪些？-icode9专业技术文章分享11-26
-
RocketMQ入门指南：搭建与使用全流程详解11-26
-
RocketMQ入门教程：轻松搭建与使用指南11-26
-
手写RocketMQ：从入门到实践的简单教程11-26
-
【机器学习(二)】分类和回归任务-决策树(Decision Tree,DT)算法-Sentosa_DSML社区版11-25
-
增量更新怎么做？-icode9专业技术文章分享11-23
-
压缩包加密方案有哪些？-icode9专业技术文章分享11-23
-
用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享11-23
-
webman可以同步自己的仓库吗？-icode9专业技术文章分享11-23
-
在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享11-23
