Java 集合 | LinkedHashMap源码分析(JDK 1.7)
一、基本图示
二、基本介绍
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
结构
- LinkedHashMap 继承了 HashMap
- LinkedHashMap 实现了 Map 接口
特性
- 底层使用拉链法处理冲突的散列表
- 元素是有序的，即遍历得到的元素顺序和放进去的元素属性一样
- 是线程不安全的
- key 和 value 都允许为 null
- 1 个 key 只能对应 1 个 value，1 个 value 对应多个 key
三、基本结构
// 指向双向链表的头节点
transient LinkedHashMap.Entry<K,V> head;
// 判断是否进行重排序
final boolean accessOrder;
LinkedList 的基本结构是继承 HashMap 的 Entry，因此 hash，key，value，next 都是继承自 HashMap 的 Entry 类的，而 before，after 则是 LinkedHashMap 特有的
需要注意的是，next 用于指定位置的哈希数组对应的链表，而 before 和 after 则用于循环双向链表中元素的指向
private static class Entry<K,V> extends HashMap.Entry<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
...
}
四、构造函数
需要注意这里的 accessOrder 变量，该变量是用来判断是按照插入顺序进行排序(false)，还是按照访问顺序进行排序(false)，具体的后面会介绍。如果不特别指定该变量为 true，默认都是 false，即元素放进去什么顺序，遍历出来就是什么顺序；如果指定为 true，则情况就不同了
注意这里的构造函数，都是调用父类的构造函数
public LinkedHashMap() {
// 调用 HashMap 的 构造函数
super();
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
// 需要注意这个构造函数，可以自己定义 accessOrder
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
五、增加函数
整体还是继承的 HashMap 的 put 方法，但是里面的 addEntry 方法进行了重写
// HashMap 的 put 方法
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// LinkedHashMap 重写的方法
addEntry(hash, key, value, i);
return null;
}
LinkedHashMap 中重写了的 addEntry 方法，里面还是调用了父类 HashMap 的 addEntry 方法。在 HashMap 的 addEntry 方法中，createEntry 方法已经被子类重写了，因此这里的 createEntry 方法调用的是子类中重写的方法
// LinkedHashMap 中重写了的方法
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
// 父类 HashMap 的中的方法
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// 这里调用的是子类 LinkedHashMap 的重写后的方法
createEntry(hash, key, value, bucketIndex);
}
LinkedHashMap 中重写后的方法，其中前面三步和 HashMap 中该方法的实现一样，唯一的区别在于 LinkedHashMap 中的 addBefore 方法
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
// 将新的键值对 e，放到 header 节点之前，即在循环双向链表最后一个元素后插入
e.addBefore(header);
size++;
}
LinkedHashMap 的 Entry 继承 HashMap 的 Entry 类，因此除了之前的特性，还加上了 before 和 after 的属性，用于指向循环链表中元素
private static class Entry<K,V> extends HashMap.Entry<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
private void remove() {
before.after = after;
after.before = before;
}
// 将新的 Entry 键值对插入到 existingEntry 键值对之前
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
...
}
直接看图示就明白了
接下来再看 LinkedHashMap 中的扩容方法。同样是调用父类 HashMap 中的扩容方法 resize，但是具体的实现就有些不同了
先看 HashMap 中的 resize 方法，其中的 transfer 方法在 LinkedHashMap 中重写了，因此这里调用 LinkedHashMap 的此方法
// 当键值对的个数 ≥ 阀值，并且哈希数组在所放入的位置不为 null，则对哈希表进行扩容
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
// 子类重写了该方法，因此调用子类的这个方法
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
HashMap 中的 transfer 方法是先遍历旧的哈希数组 table，然后再遍历 table 中对应位置的单链表，计算每个元素在新的哈希数组中的位置，然后将元素进行转移
LinkedHashMap 中的 transfer 方法，则是直接遍历循环双向链表，计算每个元素在新的哈希数组中的位置，然后将元素进行转移
void transfer(HashMap.Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 遍历双向链表，e 是双向链表的第一个元素
for (Entry<K,V> e = header.after; e != header; e = e.after) {
if (rehash)
e.hash = (e.key == null) ? 0 : hash(e.key);
// 计算该元素在新哈希数组中的位置
int index = indexFor(e.hash, newCapacity);
e.next = newTable[index];
newTable[index] = e;
}
}
在转移前后，改变的是哈希数组中元素的位置，而双向链表中元素的位置是不变的
六、元素的获取
在 LinkedHashMap 中重写了 get 方法，但是在根据 key 找到 Entry 键值对的过程中，是通过调用 HashMap 的 getEntry 方法实现的，而在该方法中，先找到哈希数组的位置，然后在遍历对应位置的单链表。可见，LinkedHashMap 的 get 方法不是遍历双向链表，依然还是遍历哈希表来获取元素的
// LinkedHashMap 中的 get 方法
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
// HashMap 中的方法，先找到指定数组下标，然后遍历对应位置的单链表
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
七、双向链表的重新排序
成员变量中，有这么一个变量 accessOrder，它有两个作用
- false，按照元素插入的顺序排序
- true，按照元素访问的顺序排序
private final boolean accessOrder;
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
而在 LinkedHashMap 的 get 和 put 方法中，都调用了同一个方法 recordAccess
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
// 如果需要覆盖 key 和 hash 相同的元素，则会调用该方法
// this 调用 put 方法的对象，因此 this 就是 linkedList 对象
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
// 调用了 recordAccess 方法
e.recordAccess(this);
return e.value;
}
该方法的作用，是把访问过的元素，这里的访问，有两层含义：
- put，根据 key 修改对应元素的 value
- get，根据 key 获取对应元素的 value
每访问一次，都会通过 recordAccess 方法把访问过的元素放到双向链表的最后一位。该方法在 HashMap 中是空实现，但是在 LinkedHashMap 中，是在 Entry 类中的方法，每次是通过 Entry 对象来调用该方法的
private static class Entry<K,V> extends HashMap.Entry<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
private void remove() {
before.after = after;
after.before = before;
}
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
void recordAccess(HashMap<K,V> m) {
// 获取传入的 HashMap 对象，向下转型为 LinkedHashMap 对象
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
// 如果 accessOrder 为 true
if (lm.accessOrder) {
lm.modCount++;
// 将访问后的元素删除
remove();
// 将访问后的元素移到最后一位
addBefore(lm.header);
}
}
...
}
我们可以通过例子和图示来看一下整个过程
@Test
public void test3() {
LinkedHashMap<String, Integer> linkedHashMap = new LinkedHashMap<>(16,0.75f, true);
linkedHashMap.put("语文", 1);
linkedHashMap.put("英语", 2);
linkedHashMap.put("数学", 3);
print(linkedHashMap);
linkedHashMap.get("语文");
print(linkedHashMap);
linkedHashMap.put("英语", 4);
print(linkedHashMap);
}
public static void print(LinkedHashMap<String, Integer> linkedHashMap) {
for (Map.Entry entry: linkedHashMap.entrySet()) {
System.out.print(entry + " ");
}
System.out.println();
}
结果是
语文=1 英语=2 数学=3
英语=2 数学=3 语文=1
数学=3 语文=1 英语=4
可以看到，每访问一个元素，该元素就被放到了最后一位，通过图示在来看一下把
通过代码，可以看到，recordAccess 方法先调用查询到键值对的 remove 方法将查询到的元素删除
然后在调用该键值对的 addBefore 方法将删除的元素置于链表的最后一位
这里我就画了 get 方法调用 recordAccess 的例子，put方法也是一样的。其实就做了两个步骤，将查询到的元素删除，然后将其置于最后一位
需要注意的是，无论是 get 还是 put，都是使用对象 e 来指向查询到的元素的，对象 e 也是 Entry 的对象，因此在调用 recordAccess 方法的时候，其实是用实例过后的 e 来调用的。之后 recordAccess 方法里的 remove 和 addBefore 方法，调用他们的对象都是对象 e，即那个查询到的键值对。了解这一点后，就能看懂了
八、参考
https://www.jianshu.com/p/8f4f58b4b8ab
https://www.cnblogs.com/xrq730/p/5052323.html