近期有朋友准备面试,在群上我们会讨论一些面试题,每次我都会受到暴击,很多题目都答不上来。平时开发中,谷歌、第三方用得很溜,貌似解决了问题,可回想起来,技术没什么长进。比如我知道图片是用三级缓存,用的是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