LinkedHashMap源码分析
//LinkedHashMap继承HashMap
public class LinkedHashMap
extends HashMap
implements Map
{
/**
* The head of the doubly linked list.
*/
private transient Entry header;
/**
* The iteration ordering method for this linked hash map: true
* for access-order, false for insertion-order.
* LinkedHashMap迭代顺序：访问顺序为true; 插入顺序为false
*/
private final boolean accessOrder;
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
//默认负载因子：0.75
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
//默认大小：16,默认负载因子：0.75
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(Map m) {
super(m);
accessOrder = false;
}
//创建LinkedHashMap实例，可以指定排序模式
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
/**
* Called by superclass constructors and pseudoconstructors (clone,
* readObject) before any entries are inserted into the map. Initializes
* the chain.
*/
@Override
void init() {
header = new Entry<>(-1, null, null, null);
header.before = header.after = header;
}
/**将table中的元素拷贝到新的数组
* Transfers all entries to new table array. This method is called
* by superclass resize. It is overridden for performance, as it is
* faster to iterate using our linked list.
*/
@Override
void transfer(HashMap.Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry e = header.after; e != header; e = e.after) {
if (rehash)
e.hash = (e.key == null) ? 0 : hash(e.key);
//计算每个Entry所在的桶
int index = indexFor(e.hash, newCapacity);
//将e作为头节点，插入这个桶里的entry链表
e.next = newTable[index];
//将新的链表放在这个桶里
newTable[index] = e;
}
}
public boolean containsValue(Object value) {
// Overridden to take advantage of faster iterator
if (value==null) {
for (Entry e = header.after; e != header; e = e.after)
if (e.value==null)
return true;
} else {
for (Entry e = header.after; e != header; e = e.after)
if (value.equals(e.value))
return true;
}
return false;
}
public V get(Object key) {
Entry e = (Entry)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
//判断Entry链表上某个entry是否相等，1：hash code相同，2：key相同
final Entry getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
for (Entry 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;
}
public void clear() {
super.clear();
header.before = header.after = header;
}
private static class Entry extends HashMap.Entry {
// These fields comprise the doubly linked list used for iteration.
Entry before, after;
Entry(int hash, K key, V value, HashMap.Entry next) {
super(hash, key, value, next);
}
/**
* Removes this entry from the linked list.
*/
private void remove() {
before.after = after;
after.before = before;
}
/**
* Inserts this entry before the specified existing entry in the list.
*/
private void addBefore(Entry existingEntry) {
after = existingEntry; //after --> this.after
before = existingEntry.before; //before --> this.before
before.after = this;
after.before = this;
}
/**
* This method is invoked by the superclass whenever the value
* of a pre-existing entry is read by Map.get or modified by Map.set.
* If the enclosing Map is access-ordered, it moves the entry
* to the end of the list; otherwise, it does nothing.
*/
void recordAccess(HashMap m) {
LinkedHashMap lm = (LinkedHashMap)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
void recordRemoval(HashMap m) {
remove();
}
}
/**
* This override alters behavior of superclass put method. It causes newly
* allocated entry to get inserted at the end of the linked list and
* removes the eldest entry if appropriate.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed
Entry eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry old = table[bucketIndex];
Entry e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
//将节点e,添加到header的前面
e.addBefore(header);
size++;
}
}
