最近在公司的项目中,需要从后台获取 JSON,按循序拼接后使用 HMAC 加密校验,在这里要保证校验一致性,就需要保证各个字段加密顺序不能变。
为了方便处理,我用 JSONObject 类解析了 JSON 数据,通过查看 JSONObject 类内部实现,发现的确是用 LinkedHashMap 实现的,可以保证顺序。
JSONObject 部分代码
- private final LinkedHashMap<String, Object> nameValuePairs;
- public JSONObject() {
- nameValuePairs = new LinkedHashMap<String, Object>();
- }
以前只知道 LinkedHashMap 可以保证顺序,却不知道如何实现,怎么保证 HashMap 的有序性,通过查看源码发现 LinkedHashMap 还是继承了 HashMap,另外把 HashMap 中保存的 Entry 重写为双向链表的节点元素,维护链表来保证访问顺序。
- public class LinkedHashMap<K,V>
- extends HashMap<K,V>
- implements Map<K,V>
- {
- /**
- * 双向链表的头节点
- */
- private transient LinkedHashMapEntry<K,V> header;
- @Override
- void init() {
- header = new LinkedHashMapEntry<>(-1, null, null, null);
- header.before = header.after = header;
- }
和
- addEntry
方法
- createEntry
- void addEntry(int hash, K key, V value, int bucketIndex) {
- LinkedHashMapEntry < K,
- V > eldest = header.after;
- if (eldest != header) {
- boolean removeEldest;
- size++;
- try {
- // 删除最近最早使用元素的策略
- // 现在Android里removeEldestEntry一直返回false
- removeEldest = removeEldestEntry(eldest);
- } finally {
- size--;
- }
- if (removeEldest) {
- removeEntryForKey(eldest.key);
- }
- }
- // 父类的这个方法会调用createEntry方法
- super.addEntry(hash, key, value, bucketIndex);
- }
- void createEntry(int hash, K key, V value, int bucketIndex) {
- // 创建节点,并在双向链表的前面插入该节点
- HashMapEntry<K,V> old = table[bucketIndex];
- LinkedHashMapEntry<K,V> e = new LinkedHashMapEntry<>(hash, key, value, old);
- table[bucketIndex] = e;
- e.addBefore(header);
- size++;
- }
- //插入节点到链表前面
- private void addBefore(LinkedHashMapEntry < K, V > existingEntry) {
- after = existingEntry;
- before = existingEntry.before;
- before.after = this;
- after.before = this;
- }
画了一个简单的流程图,可以有更直观的感受
方法很有意思,如果 accessOrder 为 True, 可以把最近访问的元素移动到链表表头,这个方法在 LruCache 的实现中很有用。
- recordAccess
- public V get(Object key) {
- LinkedHashMapEntry < K,
- V > e = (LinkedHashMapEntry < K, V > ) getEntry(key);
- if (e == null) return null;
- e.recordAccess(this);
- return e.value;
- }
- void recordAccess(HashMap < K, V > m) {
- LinkedHashMap < K,
- V > lm = (LinkedHashMap < K, V > ) m;
- //如果accessOrder为True, 将自己从链表中移除,
- // 并重新插入到表头
- if (lm.accessOrder) {
- lm.modCount++;
- remove();
- addBefore(lm.header);
- }
- }
- Iterator<K> newKeyIterator() { return new KeyIterator(); }
- Iterator<V> newValueIterator() { return new ValueIterator(); }
- Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
以下是 Iterator 的几个关键函数实现,参照上面的链表图,我们可以知道遍历是从链表的最后面往前遍历的,与 List 一样,越后面 put 进去的元素越晚遍历到。
- private abstract class LinkedHashIterator < T > implements Iterator < T > {
- LinkedHashMapEntry < K,
- V > nextEntry = header.after;
- public boolean hasNext() {
- return nextEntry != header;
- }
- Entry < K,
- V > nextEntry() {
- if (modCount != expectedModCount) throw new ConcurrentModificationException();
- if (nextEntry == header) throw new NoSuchElementException();
- LinkedHashMapEntry < K,
- V > e = lastReturned = nextEntry;
- nextEntry = e.after;
- return e;
- }
LruCache 是使用最近最少使用算法实现的缓存类,在 Android 系统以及各个图片框架中基本上都有自己的 LruCache 实现,各个版本的实现基本大同小异,都是使用 LinkedHashMap 来实现的。
以下的分析代码是基于 Glide 中的 LruCache 实现
- public class LruCache<T, Y> {
- private final LinkedHashMap<T, Y> cache = new LinkedHashMap<T, Y>(100, 0.75f, true);
- public LinkedHashMap(int initialCapacity,
- float loadFactor,
- boolean accessOrder) {
- super(initialCapacity, loadFactor);
- this.accessOrder = accessOrder;
- }
这里 LinkedHashMap 构造函数的几个参数说明一下
- - initialCapacity
- LinkedHashMap初始申请的容量大小
- - loadFactor
- 负载因子, 超过后需要扩充容量,Android中这个值其实是固定的,一直是0.75f
- - accessOrder
- 访问顺序,设置为True后,调用LinkedHashMap的get方法会调整链表元素位置
- //设置LruCache的大小
- public LruCache(int size) {
- this.initialMaxSize = size;
- this.maxSize = size;
- }
- public Y put(T key, Y item) {
- final int itemSize = getSize(item);
- //超出大小后,不加入cache
- if (itemSize >= maxSize) {
- onItemEvicted(key, item);
- return null;
- }
- //直接调用LinkedHashMap的put方法保存数据
- // 新添加的数据会放在双向链表的表头
- final Y result = cache.put(key, item);
- if (item != null) {
- currentSize += getSize(item);
- }
- //如果元素已经存在Map中了,恢复currentSize
- if (result != null) {
- // TODO: should we call onItemEvicted here?
- currentSize -= getSize(result);
- }
- //移除最近最少使用的元素
- evict();
- return result;
- }
- private void evict() {
- //大小超过定义的最大值后,移除其中最近最少访问的元素
- trimToSize(maxSize);
- }
- //由于LinkedHashMap的accessOrder设置为True了,
- //访问get方法会将被访问元素移动到链表头
- public Y get(T key) {
- return cache.get(key);
- }
- protected void trimToSize(int size) {
- Map.Entry < T,
- Y > last;
- while (currentSize > size) {
- //从双向链表尾部的元素开始移除
- last = cache.entrySet().iterator().next();
- final Y toRemove = last.getValue();
- currentSize -= getSize(toRemove);
- final T key = last.getKey();
- cache.remove(key);
- onItemEvicted(key, toRemove);
- }
- }
来源: http://www.tuicool.com/articles/f67ZVbu