1. LinkedHashMap简介
LinkedHashMap继承自HashMap,实现了Map接口。
LinkedHashMap是HashMap的一种有序实现(多态,HashMap的有序态),可以说是HashMap的一种拓展,弥补了HashMap无序这一缺点,但它实现有序的代价是牺牲了时间和空间上的开销。
LinkedHashMap的有序是通过维护一条双向链表保证了元素的有序性,除了有序这一点之外,LinkedHashMap和HashMap差不多,也就没有太多需要描述的了。
2. LinkedHashMap实现
1. 核心参数
//内部Entry实体,继承自HashMap.Node 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); } } //头节点 transient LinkedHashMap.Entry<K,V> head; //尾节点 transient LinkedHashMap.Entry<K,V> tail; //排序方式,true:访问顺序,false:插入顺序 final boolean accessOrder;
从上面可以看出,LinkedHashMap核心属性都是继承自HashMap,只是在HashMap的基础上增加了前后节点来维护一个双向链表,head和tail为链表的头尾节点,而且它的排序方式有两种:访问顺序和插入顺序。
2. 构造函数
//无参构造,构造一个初始容量16、加载因子0.75的LinkedHashMap,默认按照插入顺序排序 public LinkedHashMap() { super(); accessOrder = false; } //构造一个指定初始容量、加载因子0.75的LinkedHashMap,默认按照插入顺序排序 public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } //构造一个指定初始容量、指定加载因子的LinkedHashMap,默认按照插入顺序排序 public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } //构造一个指定初始容量、指定加载因子的LinkedHashMap,指定顺序方式 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } //构建一个能够容纳传入map中元素的最小2次幂的初始容量(最小16)、加载因子0.75的LinkedHashMap,默认按照插入顺序排序 public LinkedHashMap(Map<? extends K, ? extends V> m) { super(); accessOrder = false; putMapEntries(m, false); }
LinkedHashMap的构造也是基于HashMap进行构造的,只是在构造时加了排序方式的设置。
3. 核心方法
LinkedHashMap的实现基本上调用HashMap的API实现存储、获取、删除、扩容等操作,只是在在这些操作的基础上增加了一些维护双向链表的逻辑,保证了有序性。
//将p节点放到链表尾部 private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { //取LinkedHashMap的尾节点赋值给last LinkedHashMap.Entry<K,V> last = tail; //将尾节点设为p tail = p; //如果不存在尾节点,说明链表是空的,把链表头部也设为p if (last == null) head = p; else { //否则则将p设为last的下一节点,last设为p的上一节点 p.before = last; last.after = p; } } //将节点src替换为dst节点 private void transferLinks(LinkedHashMap.Entry<K,V> src, LinkedHashMap.Entry<K,V> dst) { //将src的上一个节点设为dst的上一个节点并赋值给b LinkedHashMap.Entry<K,V> b = dst.before = src.before; //将src的下一个节点设为dst的下一个节点并赋值给a LinkedHashMap.Entry<K,V> a = dst.after = src.after; //如果b==null,说明src就是头节点,将dst设为头节点 if (b == null) head = dst; //否则将b的下一节点设为dst else b.after = dst; //如果哦a==null,说明src就是尾节点,将dst设为尾节点 if (a == null) tail = dst; //否则则将a的上一节点设为dst else a.before = dst; } /**下面的方法都是重写HashMap到的方法**/ //重置LinkedHashMap void reinitialize() { super.reinitialize(); head = tail = null; } //HashMap中的untreeify时调用,将树形节点替换成普通节点 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); transferLinks(q, t); return t; } //新建一个树形节点并追加到LinkedHashMap尾部,调用父类的TreeNode 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; } //HashMap中的treeifyBin时调用,将普通节点替换成树形节点 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); return t; } //HashMap中移除元素后调用,调整LinkedHashMap的链表结构 void afterNodeRemoval(Node<K,V> e) { // unlink、 //取出被移除的节点以及该节点的前后节点 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; } //HashMap中添加元素后调用,evict为false说明底层HashMap在初始化模式 void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; //removeEldestEntry方法直接返回false,没有具体实现,所以这个方法是用来给子类重写的 if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } } //访问一个元素后调用,包括put、replace、get等操作 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; } } //判断LinkedHashMap中是否包含value 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; } //根据key获取value public V get(Object key) { Node<K,V> e; //通过HashMap的getNode方法获取节点 if ((e = getNode(hash(key), key)) == null) return null; //如果是按照访问顺序排序,则将该元素放到链表尾部 if (accessOrder) afterNodeAccess(e); return e.value; } //根据key获取value,与get不同的是key不存在时会返回指定的默认值 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; } //清空LinkedHashMap public void clear() { //调用父类的清空方法 super.clear(); //将链表首尾节点都置空 head = tail = null; } //返回key的有序set集合 public Set<K> keySet() { Set<K> ks = keySet; if (ks == null) { ks = new LinkedKeySet(); keySet = ks; } return ks; } //返回value的有序集合 public Collection<V> values() { Collection<V> vs = values; if (vs == null) { vs = new LinkedValues(); values = vs; } return vs; } //返回key-value实体的有序set集合 public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es; return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es; }