建设 信用中国 网站,网站建设案例完整代码,企业在线注册,房屋装修效果图三室一厅LinkedHashMap 继承于 HashMap。在 HashMap 基础上, 维护了一条双向链表, 用来记录存入 Map 中的数据的顺序, 即存储到 Map 中的 key-value 是有序的。 解决了 HashMap 无法顺序访问的和保持插入顺序的问题。
1 LinkedHashMap 的结构定义
LinkedHashMap 是基于 HashMap 的实现…LinkedHashMap 继承于 HashMap。在 HashMap 基础上, 维护了一条双向链表, 用来记录存入 Map 中的数据的顺序, 即存储到 Map 中的 key-value 是有序的。 解决了 HashMap 无法顺序访问的和保持插入顺序的问题。
1 LinkedHashMap 的结构定义
LinkedHashMap 是基于 HashMap 的实现的, 所以整体的结构是类似的, 唯一不同的是: 链表和红黑树的节点多维持了一个前驱节点指针和后驱节点指针。 简单的理解就是 HashMap 双向链表。
大体的结构如下:
1.1 数组的定义
public class HashMapK,V {transient NodeK,V[] table;
}因为继承了 HashMap, 直接复用父级 HashMap 的 table 属性, 存储的数据类型依旧是 Node
1.2 链表的定义
public class LinkedHashMapK,V extends HashMapK,V implements MapK,V {static class EntryK,V extends HashMap.NodeK,V {// 继承 HashMap Node 节点的基础上, 追加了一个前驱指针和后驱指针EntryK,V before, after;Entry(int hash, K key, V value, NodeK,V next) {super(hash, key, value, next);}}
}1.3 红黑树的定义 (和 HashMap 的红黑树定义一样) public class HashMapK, V {// 继承了 LinkedHashMap.Entry, Entry 继承了 HashMap.Node 所以 TreeNode 具有 链表的特点/** * 红黑树的定义* LinkedHashMap.Entry 继承了 HashMap.Node 节点, 所以 TreeNode 是 Node 的子类, 也具备链表的特点*/ static final class TreeNodeK,V extends LinkedHashMap.EntryK,V {/*** 红黑树的根节点*/TreeNodeK,V parent;/*** 当前节点的左节点*/TreeNodeK,V left;/*** 当前节点的右节点*/TreeNodeK,V right;/*** 删除后需要解决连接的节点*/TreeNodeK,V prev; /*** 是否为红色节点*/boolean red;// ... 后面 省略 红黑树的操作}
}2 LinkedHashMap 中的几个重要属性
public class LinkedHashMapK,V {transient LinkedHashMap.EntryK,V head;transient LinkedHashMap.EntryK,V tail;final boolean accessOrder;
}2.1 head 和 tail
transient LinkedHashMap.EntryK,V head;
transient LinkedHashMap.EntryK,V tail;双向链表的头指针和尾指针
2.2 accessOrder
final boolean accessOrder;是否按照访问顺序调整节点的顺序, 声明 LinkedHashMap 的时候可以指定, 默认为 false, 既 LinkedHashMap 中的节点按照存入的顺序排列, 而 true 则是按照访问的顺序排列。 // 设置容量, 负载因子, 和 accessOrder 为 true
MapString, String map new LinkedHashMap(16, 0.75f, true);map.put(one, 1);
map.put(two, 2);
map.put(three, 3);// 一开始的
for (Map.EntryString, String entry : map.entrySet()) {// 输出结果 one two threeSystem.out.println(entry.getKey());
}// 获取 key 为 one
map.get(one);
for (Map.EntryString, String entry : map.entrySet()) {// 输出结果 two three oneSystem.out.println(entry.getKey());
}// 获取 key 为 two
map.get(two);
for (Map.EntryString, String entry : map.entrySet()) {// 输出结果 three one two System.out.println(entry.getKey());
}可以看出来将 accessOrder 设置为 true 的话, LinkedHashMap 会在按照插入顺序的基础上, 将每次访问的节点移动到最后面
3 LinkedHashMap 的构造方法
3.1 无参的构造函数
public LinkedHashMap() {// 调用父级 HashMap 的无参构造函数super();// 默认设置为 falseaccessOrder false;
}3.2 指定容量的构造函数
public LinkedHashMap(int initialCapacity) {// 调用父级 HashMap 指定容量的构造函数super(initialCapacity);accessOrder false;
}3.3 指定容量和负载因子的构造函数
public LinkedHashMap(int initialCapacity, float loadFactor) {// 调用父级 HashMap 指定容量和负载因子的构造函数super(initialCapacity, loadFactor);accessOrder false;
}3.4 指定容量, 负载因子和顺序访问的构造函数
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {// 调用父级指定容量和负载因子的构造函数super(initialCapacity, loadFactor);// 将访问顺序参数设置为用户指定的值this.accessOrder accessOrder;
}3.5 给定一个 Map 的构造函数
public LinkedHashMap(Map? extends K, ? extends V m) {// 调用父级无参的构造函数super();accessOrder false;putMapEntries(m, false);
}final void putMapEntries(Map? extends K, ? extends V m, boolean evict) {int s m.size();if (s 0) {// 存储数据的 table 数组为空, 当初始化if (table null) {// 计算容量float ft ((float)s / loadFactor) 1.0F;// 控制容量 不大于 最大值int t ((ft (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);// 计算出来的容量大于预设的容量, 重新计算新的容量, 并赋值给 thresholdif (t threshold)threshold tableSizeFor(t);} else if (s threshold)// 存入的 Collection 的容量大于 当前的阈值, 调用 进行扩容resize();// 依次遍历需要导入的 Map, for (Map.Entry? extends K, ? extends V e : m.entrySet()) {K key e.getKey();V value e.getValue();// 调用到父级的 putVal 方法, 这个方法涉及到添加数据的部分, 下面添加数据的部分讲解putVal(hash(key), key, value, false, evict);} }
}4 LinkedHashMap 的操作方法
4.1 添加数据
LinkedHashMap 本身没有提供出更多的添加数据的方法, 全部的添加数据的方法都是继承至 HashMap, 同时重写了添加数据中 HashMap 会调用的钩子方法, 达到自己添加数据后调整链表的效果 这里以 put(key, value) 为例
public class LinkedHashMapK, V extends HashMapK, V implements MapK, V {// 在 LinkedHashMap 中没有这个方法 这个方法是父类 HashMap 的, 只是为了方法讲解, 添加到这里public V put(K key, V value) {// 同样是计算 key 的 hashCode, 然后调用 putValreturn putVal(hash(key), key, value, false, true);}// 在 LinkedHashMap 中没有这个方法 这个方法是父类 HashMap 的, 只是为了方法讲解, 添加到这里final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;if ((tab table) null || (n tab.length) 0)n (tab resize()).length;if ((p tab[i (n - 1) hash]) null) // 将数组的 i 位置设置为 Node 节点// 在 HashMap 中 newNode 返回的是 Node 类型的数据// 但是 LinkedHashMap 则是 LinkedHashMap.Entry, 所以 LinkedHashMap 重写了这个方法// 这里会调用到自身的 newHode 方法tab[i] newNode(hash, key, value, null); else {NodeK,V e; K k;if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;else if (p instanceof TreeNode)e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount 0; ; binCount) {if ((e p.next) null) {p.next newNode(hash, key, value, null);if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}// 在当前的数据中找到 key 相同的数据if (e ! null) {V oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;// HashMap 中这个方法是空方法, 但是 LinkedHashMap 有需要移动修改节点的需求// 所以 LinkedHashMap 也是重写了这个方法 afterNodeAccess(e);return oldValue;}} modCount;if (size threshold)// 扩容的逻辑没有变动resize();// 插入节点后的行为调用, HashMap 空方法, LinkedHashMap 重写了afterNodeInsertion(evict);return null; }// LinkedHashMap 自身的创建节点方法NodeK,V newNode(int hash, K key, V value, NodeK,V e) {// 创建节点LinkedHashMap.EntryK,V p new LinkedHashMap.EntryK,V(hash, key, value, e);// 将新创建的节点设置到链表的尾部linkNodeLast(p);return p;}// LinkedHashMap 自身的方法, 将入参的节点设置到链表的尾部private void linkNodeLast(LinkedHashMap.EntryK,V p) {// 保存当前的尾结点LinkedHashMap.EntryK,V last tail;// 设置当前的尾结点为创建的节点tail p;if (last null)// 旧的尾结点为空, 没有数据// 设置头节点为新创建的节点head p;else {// 旧的尾结点不为空, 有数据 // 设置新节点的前置节点为上次的尾结点p.before last;// 设置上次的尾结点的后置节点为新创建的节点last.after p;}}// 新增节点时, 存在 key 已经有数据的情况, 这时除了替换旧的 value 外, 如果 accessOrder (按照访问顺序排序) 设置为 true, 还需要把这个节点放到最后面, 保持新增的顺序void afterNodeAccess(NodeK,V e) {LinkedHashMap.EntryK,V last;// accessOrder 为 true, 同时尾节点不等于入参的节点if (accessOrder (last tail) ! e) {// p 访问的节点 e, b 访问的节点e 的前置节点 a 访问的节点 e 的后置节点LinkedHashMap.EntryK,V p (LinkedHashMap.EntryK,V)e, b p.before, a p.after;// 设置 p 的后置节点为 nullp.after null;// p 的前置节点为 null,if (b null)// 设置头节点为 p 的后置节点head a;else// p 的前置节点存在// 设置 p 的前置节点的后置节点为 p 的后置节点b.after a;// p 的后置节点不为 null, if (a ! null)// 设置 p 的后置节点的前置节点为 p 节点的前置节点a.before b;else// p 的后置节点 a 为 null, 说明p 就是尾结点了// 设置链表的尾节点为 p 的前置节点last b;// 原本的尾节点为空 if (last null)// 设置头节点为 p 节点 head p;else {// 原本的为节点不为空// 设置 p 的前置节点为原本的尾节点p.before last;// 设置原本的尾节点的后置节点为 p last.after p;}// 设置尾节点为需要移动的节点tail p;// 修改次数 1modCount;}}// LinkedHashMap 自身的方法, 在插入新节点后, 调用, 判断是否需要删除最旧的节点 (第一个节点)在 LinkedHashMap 中默认为不会删除void afterNodeInsertion(boolean evict) {LinkedHashMap.EntryK,V first;// evict 在 putVal 方法调用中都是为 true, 构造方法中调用到这里一般都是 false// LinkedHashMap 的 removeEldestEntry 方法 一直都是返回 false, 但是子类可以重写这个方法, 让其返回 true, 就能走到下面的删除头节点的方法if (evict (first head) ! null removeEldestEntry(first)) {// 获取头节点的 keyK key first.key;// 删除节点, 这个涉及到删除数据, 后面删除数据的部分分析removeNode(hash(key), key, null, false, true);}}protected boolean removeEldestEntry(Map.EntryK,V eldest) {return false;}
}其他几个添加数据的方法类型, 就不展开了
4.2 获取数据
public class LinkedHashMapK, V extends HashMapK, V implements MapK, V {public V get(Object key) {NodeK,V e;// 调用 HashMap 的 getNode 方法获取节点数据if ((e getNode(hash(key), key)) null)return null;// 设置了按照访问顺序排序的属性, 将当前节点设置到链表的尾部if (accessOrder)afterNodeAccess(e);return e.value; }
}4.3 删除数据
通添加数据一样, LinkedHashMap 没有提供新的删除数据的方法, 都是继承父级 HashMap 的, 同时重写几个钩子函数
public class LinkedHashMapK, V extends HashMapK, V implements MapK, V {// HashMap 的 remove 方法public V remove(Object key) {NodeK,V e;return (e removeNode(hash(key), key, null, false, true)) null ? null : e.value;}// HashMap 的 删除节点final NodeK,V removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {NodeK,V[] tab; NodeK,V p; int n, index;if ((tab table) ! null (n tab.length) 0 (p tab[index (n - 1) hash]) ! null) {NodeK,V node null, e; K k; V v;if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))node p;else if ((e p.next) ! null) {if (p instanceof TreeNode)node ((TreeNodeK,V)p).getTreeNode(hash, key);else {do {if (e.hash hash ((k e.key) key ||(key ! null key.equals(k)))) {node e;break;}p e;} while ((e e.next) ! null);}}if (node ! null (!matchValue || (v node.value) value || (value ! null value.equals(v)))) {if (node instanceof TreeNode)((TreeNodeK,V)node).removeTreeNode(this, tab, movable);else if (node p)tab[index] node.next;elsep.next node.next;modCount;--size;// 此处调用到 LinkedHashMap 自身的 afterNodeRemoval 方法afterNodeRemoval(node);return node;}}return null;}// 调整删除节点后的左右节点的指针指向void afterNodeRemoval(NodeK,V e) {// p 删除的节点 b 删除节点的前置节点, a 删除节点的后置节点LinkedHashMap.EntryK,V p (LinkedHashMap.EntryK,V)e, b p.before, a p.after;// 设置删除节点 p 的前置节点和后置节点为 null, 便于垃圾回收p.before p.after null;// 如果 p 的前置节点为 null, p 为头节点if (b null)// 设置头节点为 p 的后置节点head a;else// p 的前置节点为 null, p 不是头节点// 设置 p 的前置节点的后置节点为 p 的后置节点b.after a;// p 的后置节点为 null, p 为尾节点if (a null)// 设置尾节点为 p 的前置节点tail b;else// p 的后置节点为 null, p 不是尾节点// 设置 p 的后置节点的前置节点为 p 的前置节点a.before b;}
}4.4 修改数据
LinkedHashMap 本身没提供修改数据的方法, 依旧是继承父级的
public class LinkedHashMapK, V extends HashMapK, V implements MapK, V {public V replace(K key, V value) {NodeK,V e;if ((e getNode(hash(key), key)) ! null) {V oldValue e.value;e.value value;// 调用到 LinkedHashMap 自身的 afterNodeAccess 方法, 尝试将这个节点设置到尾部afterNodeAccess(e);return oldValue;}return null;}}5 LinkedHashMap 的补充
