LinkedHashMap 继承了 HashMap, 他在 HashMap 的基础上增加了一个双向链表的结构, 链表默认维持 key 插入的顺序, 重复的 key 值插入不会改变顺序, 适用于使用者需要返回一个顺序相同的 map 对象的情况. 还可以生成 access-order 顺序的版本, 按照最近访问顺序来存储, 刚被访问的结点处于链表的末尾, 适合 LRU,put get compute merge 都算作一次访问, 其中 put key 值相同的结点也算作一次访问, replace 只有在换掉一个键值对的时候才算一次访问, putAll 产生的访问顺序取决于原本 map 的迭代器实现.
在插入键值对时, 可以通过对 removeEldestEntry 重写来实现新键值对插入时自动删除最旧的键值对
拥有 HashMap 提供的方法, 迭代器因为是通过遍历双向链表, 所以额外开销与 size 成正比与 capacity 无关, 因此选择过大的初始大小对于遍历时间的增加没有 HashMap 严重, 后者的遍历时间依赖与 capacity.
同样是非线程安全方法, 对于 LinkedHashMap 来说, 修改结构的操作除了增加和删除键值对外, 还有对于 access-order 时进行了 access 导致迭代器顺序改变, 主要是 get 操作, 对于插入顺序的来说, 仅仅修改一个已有 key 值的 value 值不是一个修改结构的操作, 但对于访问顺序, put 和 get 已有的 key 值会改变顺序. 迭代器也是 fail-fast 设计, 但是 fail-fast 只是一个调试功能, 一个设计良好的程序不应该出现这个错误
因为 HashMap 加入了 TreeNode, 所以现在 LinkedHashMap 也有这个功能
以下描述中的链表, 若无特别说明都是指 LinkedHashMap 的双向链表
先来看一下基本结构, 每个键值对加入了前后指针, 集合加入了头尾指针来形成双向链表, accessOrder 代表链表是以访问顺序还是插入顺序存储
- static class Entry<K,V> extends HashMap.Node<K,V> {
- Entry<K,V> before, after;// 增加了先后指针来形成双向链表
- Entry(int hash, K key, V value, Node<K,V> next) {
- super(hash, key, value, next);
- }
- }
- /**
- * The head (eldest) of the doubly linked list. 头部
- */
- transient LinkedHashMap.Entry<K,V> head;
- /**
- * The tail (youngest) of the doubly linked list. 尾部
- */
- transient LinkedHashMap.Entry<K,V> tail;
- //true 访问顺序 false 插入顺序
- final boolean accessOrder;
然后是几个内部方法. linkNodeLast 将 p 连接到链表尾部
- private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
- LinkedHashMap.Entry<K,V> last = tail;
- tail = p;
- if (last == null)
- head = p;// 原本链表为空则 p 同时为头部
- else {
- p.before = last;
- last.after = p;
- }
- }
transferLinks 用 dst 替换 src
- private void transferLinks(LinkedHashMap.Entry<K,V> src,
- LinkedHashMap.Entry<K,V> dst) {
- LinkedHashMap.Entry<K,V> b = dst.before = src.before;
- LinkedHashMap.Entry<K,V> a = dst.after = src.after;
- if (b == null)
- head = dst;
- else
- b.after = dst;
- if (a == null)
- tail = dst;
- else
- a.before = dst;
- }
reinitialize 在调用 HashMap 方法的基础上, 将 head 和 tail 设为 null
- void reinitialize() {
- super.reinitialize();
- head = tail = null;
- }
newNode 生成一个 LinkedHashMap 结点, next 指向 e, 插入到 LinkedHashMap 链表末端
- 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);// 新建一个键值对, next 指向 e
- linkNodeLast(p);//p 插入到 LinkedHashMap 链表末端
- return p;
- }
replacementNode 根据原结点生成一个 LinkedHashMap 结点替换原结点
- Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
- LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
- LinkedHashMap.Entry<K,V> t =
- new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);// 生成一个新的键值对 next 是给出的 next 参数
- transferLinks(q, t);// 用 t 替换 q
- return t;
- }
newTreeNode 生成一个 TreeNode 结点, next 指向 next, 插入到 LinkedHashMap 链表末端
- 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);// 生成一个 TreeNode,next 指向参数 next
- linkNodeLast(p);//p 插入到 LinkedHashMap 链表末端
- return p;
- }
replacementTreeNode 根据结点 p 生成一个新的 TreeNode,next 设为给定的 next, 替换原本的 p
- TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
- LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
- TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
- transferLinks(q, t);// 根据结点 p 生成一个新的 TreeNode,next 设为给定的 next, 替换原本的 p
- return t;
- }
afterNodeRemoval 从 LinkedHashMap 的链上移除结点 e
- void afterNodeRemoval(Node<K,V> e) {
- LinkedHashMap.Entry<K,V> p =
- (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
- p.before = p.after = null;
- if (b == null)
- head = a;
- else
- b.after = a;
- if (a == null)
- tail = b;
- else
- a.before = b;
- }
afterNodeInsertion 可能移除最旧的结点, 需要 evict 为 true 同时链表不为空同时 removeEldestEntry 需要重写
- void afterNodeInsertion(boolean evict) {
- LinkedHashMap.Entry<K,V> first;
- if (evict && (first = head) != null && removeEldestEntry(first)) {//removeEldestEntry 需要重写才从发挥作用, 否则一定返回 false
- K key = first.key;// 移除链表头部的结点
- removeNode(hash(key), key, null, false, true);
- }
- }
afterNodeAccess 在访问过后将结点 e 移动到链表尾部, 需要 Map 是 access-order, 若移动成功则增加 modCount
- void afterNodeAccess(Node<K,V> e) {
- LinkedHashMap.Entry<K,V> last;
- if (accessOrder && (last = tail) != e) {//Map 是 access-order 同时 e 不是链表的尾部
- LinkedHashMap.Entry<K,V> p =
- (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
- p.after = null;
- if (b == null)// 将结点 e 从链表中剪下
- 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;// 结点 e 移动到链表尾部
- ++modCount;// 因为有 access-order 下结点被移动, 所以增加 modCount
- }
- }
构造函数方面, accessOrder 默认是 false 插入顺序, 初始大小为 16, 负载因子为 0.75, 这里是同 HashMap. 复制构造也是调用了 HashMap.putMapEntries 方法
containsValue 遍历链表寻找相等的 value 值, 这个操作一定不会造成结构改变
- public boolean containsValue(Object value) {
- for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {// 检查同样是根据 LinkedHashMap 提供的链表顺序进行遍历
- V v = e.value;
- if (v == value || (value != null && value.equals(v)))
- return true;
- }
- return false;
- }
get 方法复用 HashMap 的 getNode 方法, 若找到结点且 Map 是访问顺序时, 要将访问的结点放到链表最后, 若没找到则返回 null. 而 getOrDefault 仅有的区别是没找到时返回 defaultValue
- public V get(Object key) {
- Node<K,V> e;
- if ((e = getNode(hash(key), key)) == null)// 复用 HashMap 的 getNode 方法
- return null;
- if (accessOrder)
- afterNodeAccess(e);//access-order 时将 e 放到队尾
- return e.value;
- }
- public V getOrDefault(Object key, V defaultValue) {
- Node<K,V> e;
- if ((e = getNode(hash(key), key)) == null)
- return defaultValue;// 复用 HashMap 的 getNode 方法, 若没有找到对应的结点则返回 defaultValue
- if (accessOrder)
- afterNodeAccess(e);//access-order 时将 e 放到队尾
- return e.value;
- }
clear 方法在 HashMap 的基础上要把 head 和 tail 设为 null
- public void clear() {
- super.clear();
- head = tail = null;
- }
removeEldestEntry 在 put 和 putAll 插入键值对时调用, 原本是一定返回 false 的, 如果要自动删除最旧的键值对要返回 true, 需要进行重写. 比如下面这个例子, 控制 size 不能超过 100
- private static final int MAX_ENTRIES = 100;
- protected boolean removeEldestEntry(Map.Entry eldest) {
- return size() > MAX_ENTRIES;
- }
下面两个方法和 HashMap 相似, 返回 key 的 Set 和 value 的 Collection 还有返回键值对的 Set, 这个是直接引用, 所以对它们的 remove 之类的修改会直接反馈到 LinkedHashMap 上
- public Set<K> keySet() {
- Set<K> ks = keySet;
- if (ks == null) {
- ks = new LinkedKeySet();
- keySet = ks;
- }
- return ks;// 返回 key 值的 set
- }
- public Collection<V> values() {
- Collection<V> vs = values;
- if (vs == null) {
- vs = new LinkedValues();
- values = vs;
- }
- return vs;// 返回一个包含所有 value 值的 Collection
- }
- public Set<Map.Entry<K,V>> entrySet() {
- Set<Map.Entry<K,V>> es;
- return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;// 返回一个含有所有键值对的 Set
- }
检查 HashMap 的 putVal 方法, 我们可以看到在找到了相同 key 值并修改 value 值时会调用 afterNodeAccess, 对于 access-order 会改变结点顺序
- if (e != null) { // 找到了相同的 key 则修改 value 值并返回旧的 value
- V oldValue = e.value;
- if (!onlyIfAbsent || oldValue == null)
- e.value = value;
- afterNodeAccess(e);
- return oldValue;
- }
来源: https://www.cnblogs.com/graywind/p/9484577.html