HashMap、LinkedHashMap、三级缓存

2018-07-13 Android 阅读量

HashMap

HashMap在迭代器创建后，通过iterator的remove()方法之外的其他方式改变HashMap结构（增加或删除元素），都会抛出ConcurrentModificationException异常（fail-fast），因为HashMap不支持并发操作，预期在将来产生无法预料的后果，不如马上抛出错误。这种fail-fast的行为并不一定总是有效，因此在程序中不应该依赖这种行为。

HashMap中的树节点size是普通节点的两倍左右，所以在桶里的节点不多的时候（阈值为6，转换成树节点的阈值为8），会把树节点重新转换成普通节点。因为红黑树的平均查找长度是log（n），长度为8的时候，平均查找长度为3。。如果继续使用链表，平均查找长度为8/2=4。这才有转换为树的必要。。链表长度如果是6以内，6/2=3，速度也很快的。转化为树还有生成树的时间，并不明智。

红黑树和HashMap可以参考https://www.cnblogs.com/liwei2222/p/8013367.html，其实和算法这本书上说的差不多。

LinkedHashMap

关于LinkedHashMap可以参考：https://www.cnblogs.com/xiaoxi/p/6170590.html。LinkedHashMap相当于HashMap和LinkedList（循环双向链表）的结合，可以选择按照插入顺序或者访问顺序记录节点顺序。

三级缓存

使用缓存的好处：

加快数据的获取速度，降低开销；
减轻服务器的负担（访问网络地情况）；
在没网络的情况下获取数据；

关于LruCache参考：https://www.jianshu.com/p/b49a111147ee。LruCache采用LinkedHashMap实现，最新访问的节点放到尾部，头部的就是上次访问离现在最久的，缓存满的话删除头部的节点。

LinkedHashMap可以用来实现LruCache的关键两点：

LinkedHashMap是按Key-Value存储内容的，和Cache一致；
LinkedHashMap设置accessOrder为true时可以按照访问顺序记录元素的顺序，正好可以用来实现Lru算法。

Android的三级缓存：

网络缓存；
磁盘缓存DiskLruCache（Android不包含，需要到Github下载）；
内存缓存LruCache（Android 3.1支持）；

最重要的是后面两种。

LruCache

LruCache基本用法：

int cacheSize = 4 * 1024 * 1024; // 4MiB
LruCache<String, Bitmap> bitmapCache = new LruCache<String, Bitmap>(cacheSize) {
    protected int sizeOf(String key, Bitmap value) {
        return value.getByteCount();
    }
}}

cacheSize和sizeOf的单位要一致。

LruCache是线程安全的，比如get()方法中：

synchronized (this) {
            mapValue = map.get(key);
            if (mapValue != null) {
                hitCount++;
                return mapValue;
            }
            missCount++;
        }

另外，该类不允许null作为key和value。get,put和remove方法返回null均表示不存在该元素。

LruCache的size属性表示的值和单位有关不一定时元素的个数，比如图片的缓存size表示的可能是多少M。

trim表示修剪，trimToSize方法就表示把Map修剪到多大，这里指的是最大的size。

LruCache的put，get方法都可能调用trimToSize方法，pu好理解，get方法中之所以会调用该方法是因为在缓存中不存在Key对应的entry时会调用create方法（默认实现返回null），如果create成功size就会发生改变，所以需要调用trimToSize以免超出最大size。remove方法是删除元素的，所以不不需要调用该方法。

entryRemove被调用的三种情况：

缓存满了，移除元素；
调用remove方法移除元素；
put方法更新了元素；

entryRemove默认实现为空，可以重写来进行资源的显式释放，比如回收Bitmap。

DiskLruCache

DiskLruCache用于实现磁盘缓存，通过将缓存对象写入磁盘实现缓存的效果。DiskLruCache的使用过程如下。

创建

DiskLruCache不能通过LruCache创建。它提供了open方法创建自身。这一点在AOSP源码的external/glide/third_party/disklrucache/src/main/java/com/bumptech/glide/disklrucache/DiskLruCache.java中确实是这样，但是在external/okhttp/okhttp/src/main/java/com/squareup/okhttp/internal/DiskLruCache.java中未找到该方法，暂时就按glide中的来。open方法的声明如下：

 /**
   * Opens the cache in {@code directory}, creating a cache if none exists
   * there.
   * @param directory 应用的缓存目录，或者其他指定的目录，区别在于应用卸载后缓存会不会清空
   * @param appVersion 应用的版本，如前后版本改变，缓存会被清空，一般为1即可
   * @param valueCount 每个entry中value的个数，一般为1
   * @param maxSize 缓存总大下，比如50M
   * @throws IOException if reading or writing the cache directory fails
   */
public static DiskLruCache open(File directory, int appVersion, int valueCount, long maxSize)
      throws IOException

典型的缓存创建过程如下：

privata static final long DISK_CACHE_SIZE = 1024 * 0124  * 50;//50M
File diskCahceDir = getDiskCacheDir(mContext, "bitmap");
if (!diskCacheDir.exists()){
	diskCacheDir.mkdirs();
}
mDiskLruCache = DiskLruCache.open(diskCacheDir, 1, 1, DISK_CACHE_SIZE);

缓存添加

DiskLruCache的缓存添加是通过Editor完成的，Editor是一个缓存对象的编辑器对象（类似于SharedPreferences值得editor）。仍然以图片为例，添加缓存要经过以下步骤：

url转化成key，因为url中可能存在一些特殊字符，可能会影响url的使用，一般采用url的md5值；

获取Editor对象，如下所示：

String key = hashKeyFromUrl(url);
DiskLruCache.Editor editor = mDiskLruCache.edit(key);
if (editir != null) {
  //之前设置了一个节点只有一个数据，所以DISK_CACHE_INDEX为0即可
  OutputStream outputStream = editor.newOutputStream(DISK_CACHE_INDEX);
}

将数据写入editor的输出流；

使用editor的commit()方法提交数据，或者在出现问题时用abort()方法回退整个操作：

OutputStream outputStream = editor.newOutputStream(DISK_CACHE_INDEX);
if(downloadUrlToStream(url, outputStream)){
  editor.commit();
} else {
  editor.abort();
}
mDiskLruCache.flush;

缓存查找

和缓存的添加类似，先将url转化成key,然后通过DiskLruCache的get方法得到一个SnapShot对象，接着再通过SnapShot对象得到缓存文件的输入流，有了输入流就可以得到Bitmap了。为了避免oom，一般不直接加载原图，通过BitmapFactory.Options对象可以加载缩放后的对象，但是该方法对FileInputStream的缩放存在问题，因为FileInputStream是一种有序的文件流，而两次的decodeStream的调用会影响文件流的位置属性，导致第二次decodeStream得到的时null。为了解决这个问题，可以通过文件流来的到对应的文件描述符（getFD方法），然后通过BitmapFactory.decodeFileDescriptor方法来加载缩放后的图片。

DiskLruCahce的内容来自《Android开发艺术探索》12.2.2小节，相关代码可以参考该书内容。