LinkedHashMap 实质是 HashMap+LinkedList, 提供了顺序访问的功能; 所以在看这篇博客之前最好先看一下我之前的两篇博客, HashMap 相关 和 LinkedList 相关;
一, 整体结构
1. 定义
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {}
从上述定义中也能看到 LinkedHashMap 其实就是继承了 HashMap, 并加了双向链表记录顺序, 代码和结构本身不难, 但是其中结构的组织, 代码复用这些地方十分值得我们学习; 具体结构如图所示:
2. 构造函数和成员变量
- public LinkedHashMap(int initialCapacity, float loadFactor) {}
- public LinkedHashMap(int initialCapacity) {}
- public LinkedHashMap() {}
- public LinkedHashMap(Map<? extends K, ? extends V> m) {}
- public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {}
- /**
- * The iteration ordering method for this linked hash map: <tt>true</tt>
- * for access-order, <tt>false</tt> for insertion-order.
- * @serial
- */
- final boolean accessOrder;
可以看到 LinkedHashMap 的 5 个构造函数和 HashMap 的作用基本是一样的, 都是初始化 initialCapacity 和 loadFactor, 但是多了一个 accessOrder, 这也是 LinkedHashMap 最重要的一个成员变量了;
当 accessOrder 为 true 的时候, 表示 LinkedHashMap 中记录的是访问顺序, 也是就没放 get 一个元素的时候, 这个元素就会被移到链表的尾部;
当 accessOrder 为 false 的时候, 表示 LinkedHashMap 中记录的是插入顺序;
3. Entry 关系
扎眼一看可能会觉得 HashMap 体系的节点继承关系比较混乱; 一所以这样设计因为
LinkedHashMap 继承至 HashMap, 其中的节点同样有普通节点和树节点两种; 并且树节点很少使用;
现在的设计中, 树节点是可以完全复用的, 但是 HashMap 的树节点, 会浪费双向链表的能力;
如果不这样设计, 则至少需要两条继承关系, 并且需要抽出双向链表的能力, 整个继承体系以及方法的复用会变得非常复杂, 不利于扩展;
二, 重要方法
上面我们已经讲了 LinkedHashMap 就是 HashMap + 链表, 所以我们只需要在结构有可能改变的地方加上链表的修改就可以了, 结构可能改变的地方只要有 put/get/replace, 这里需要注意扩容的时候虽然结构改变了, 但是节点的顺序仍然保持不变, 所以扩容可以完全复用;
1. put 方法
未找到 key 时, 直接在最后添加一个节点
- Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
- LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
- linkNodeLast(p);
- return p;
- }
- TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
- TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
- linkNodeLast(p);
- return p;
- }
- private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
- LinkedHashMap.Entry<K,V> last = tail;
- tail = p;
- if (last == null)
- head = p;
- else {
- p.before = last;
- last.after = p;
- }
- }
上面代码很简单, 但是很清晰的将添加节点到最后的逻辑抽离的出来;
找到 key, 则替换 value, 这部分需要联系 HashMap 相关 中的 put 方法部分;
- // HashMap.putVal
- ...
- // 如果找到 key
- if (e != null) { // existing mapping for key
- V oldValue = e.value;
- if (!onlyIfAbsent || oldValue == null)
- e.value = value;
- afterNodeAccess(e);
- return oldValue;
- }
- // 如果没有找到 key
- ++modCount;
- if (++size> threshold)
- resize();
- afterNodeInsertion(evict);
- return null;
- ...
在之前的 HashMap 源码分析当中可以看到有几个空的方法
- void afterNodeAccess(Node<K,V> p) {
- }
- void afterNodeInsertion(boolean evict) {
- }
- void afterNodeRemoval(Node<K,V> p) {
- }
这三个就是用来调整链表位置的事件方法, 可以看到 HashMap.putVal 中就使用了两个,
- void afterNodeAccess(Node<K,V> e) { // move node to last
- LinkedHashMap.Entry<K,V> last;
- if (accessOrder && (last = tail) != e) {
- LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
- p.after = null;
- if (b == null)
- head = a;
- else
- b.after = a;
- if (a != null)
- a.before = b;
- else
- last = b;
- if (last == null)
- head = p;
- else {
- p.before = last;
- last.after = p;
- }
- tail = p;
- ++modCount;
- }
- }
afterNodeAccess 可以算是 LinkedHashMap 比较核心的方法了, 当访问了一个节点的时候, 如果 accessOrder = true 则将节点放到最后, 如果 accessOrder = false 则不变;
- void afterNodeInsertion(boolean evict) { // possibly remove eldest
- LinkedHashMap.Entry<K,V> first;
- if (evict && (first = head) != null && removeEldestEntry(first)) {
- K key = first.key;
- removeNode(hash(key), key, null, false, true);
- }
- }
- protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
- return false;
- }
afterNodeInsertion 方法是插入节点后是否需要移除最老的节点, 这个方法和维护链表无关, 但是对于 LinkedHashMap 的用途有很大作用, 后天会举例说明;
2. get 方法
- public V get(Object key) {
- Node<K,V> e;
- if ((e = getNode(hash(key), key)) == null)
- return null;
- if (accessOrder)
- afterNodeAccess(e);
- return e.value;
- }
- public V getOrDefault(Object key, V defaultValue) {
- Node<K,V> e;
- if ((e = getNode(hash(key), key)) == null)
- return defaultValue;
- if (accessOrder)
- afterNodeAccess(e);
- return e.value;
- }
get 方法主要也是通过 afterNodeAccess 来维护链表位置关系;
以上就是 LinkedHashMap 链表位置关系调整的主要方法了;
3. containsValue 方法
- public boolean containsValue(Object value) {
- for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
- V v = e.value;
- if (v == value || (value != null && value.equals(v)))
- return true;
- }
- return false;
- }
可以看到 LinkedHashMap 还重写了 containsValue, 在 HashMap 中寻找 value 的时候, 需要遍历所有节点, 他是遍历每个哈希桶, 在依次遍历桶中的链表; 而在 LinkedHashMap 里面要遍历所有节点的时候, 就可以直接通过双向链表进行遍历了;
三, 应用
- public class Cache<K, V> {
- private static final float DEFAULT_LOAD_FACTOR = 0.75f;
- private final int MAX_CAPACITY;
- private LinkedHashMap<K, V> map;
- public Cache(int capacity, boolean accessOrder) {
- capacity = (int) Math.ceil((MAX_CAPACITY = capacity) / DEFAULT_LOAD_FACTOR) + 1;
- map = new LinkedHashMap(capacity, DEFAULT_LOAD_FACTOR, accessOrder) {
- @Override
- protected boolean removeEldestEntry(Map.Entry eldest) {
- return size()> MAX_CAPACITY;
- }
- };
- }
- public synchronized void put(K key, V value) {
- map.put(key, value);
- }
- public synchronized V get(K key) {
- return map.get(key);
- }
- @Override
- public String toString() {
- StringBuilder sb = new StringBuilder();
- for (Map.Entry entry : map.entrySet()) {
- sb.append(String.format("%s:%s", entry.getKey(), entry.getValue()));
- }
- return sb.toString();
- }
- }
以上是就是一个 LinkedHashMap 的简单应用,
当 accessOrder = true 时, 就是 LRUCache,
当
accessOrder = false
时, 就是 FIFOCache;
- // LRUCache
- Cache<String, String> cache = new Cache<>(3, true);
- cache.put("a", "1");
- cache.put("b", "2");
- cache.put("c", "3");
- cache.put("d", "4");
- cache.get("c");
- System.out.println(cache);
- // 打印: b:2 d:4 c:3
- // FIFOCache
- Cache<String, String> cache = new Cache<>(3, false);
- cache.put("a", "1");
- cache.put("b", "2");
- cache.put("c", "3");
- cache.put("d", "4");
- cache.get("c");
- System.out.println(cache);
- // 打印: b:2 c:3 d:4
总结
总体而言 LinkedHashMap 的代码比较简单, 但是我觉得里面代码的组织, 逻辑的提取等方面特别值得借鉴;
来源: https://www.cnblogs.com/sanzao/p/10297220.html