LinkedHahMap有两个属性：
private transient Entry header;
private final boolean accessOrder;
构造方法有以下几种：
1.public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
2. public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
3.public LinkedHashMap() {
super();
accessOrder = false;
}
4.public LinkedHashMap(Map m) {
super(m);
accessOrder = false;
}
5. public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
由于LinkedHashMap继承与HashMap，因此super()方法是
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
注意init()方法，LinkedHashMap中重写了init方法，如下：
void init() {
header = new Entry(-1, null, null, null);
header.before = header.after = header;
}
除了第五种，其他情况下，accessOrder 都默认为false，此时，会实现先入先出的方式输出；当我们以第五种方式实现，且accessOrder 为true时，则最不常用的数据先输出；因此LinkedHashMap常被用来实现LRU算法，将常用数据放入缓存，且可定量，当有新数据存入时，将最不常用数据移除；
下面分析源码中如何实现以上两种输出方式：
我们先看下LinkedHashMap的Entry结构与方法（Map存储数据，是以Entry数组来存储的，有些类似于List以Object数组）
private static class Entry extends HashMap.Entry {
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.
* 将调用者放到existingEntry的前面，将before，after关联起来，参考循环双端队列
*/
private void addBefore(Entry existingEntry) {
after = existingEntry;
before = existingEntry.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.
* 大体意思是，此方法会在Map.get或Map.set.(此处意思应该是put)时调用，
* 当accessOrder为true时，
* 将此entry移到链表的尾部
*/
void recordAccess(HashMap m) {
LinkedHashMap lm = (LinkedHashMap)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
void recordRemoval(HashMap m) {
remove();
}
}
有了Entry之后，再去看put()方法，由于LinkedHashMap自己没有重写put方法，因此调用父类的方法：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry 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++;
addEntry(hash, key, value, i);
return null;
}
putForNullKey(value)方法逻辑与此相同，不单独分析；当有相同的key值时，替换数据，且调用一个recordAccess(this)方法，下面再分析，如果没有相同的key值，则调用addEntry(hash, key, value, i)；此方法代码为：
void addEntry(int hash, K key, V value, int bucketIndex) {
createEntry(hash, key, value, bucketIndex);
Entry eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
if (size >= threshold)
resize(2 * table.length);
}
}
其中 createEntry(hash, key, value, bucketIndex)代码为：
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.addBefore(header);
size++;
}
createEntry()方法中，除了常规新增外，还调用了addBefore(header)方法，该方法是将新增的entry增加到header前一位；
addEntry()方法中，除了createEntry()外，还有根据removeEldestEntry(eldest)的返回值来分别执行方法，removeEldestEntry代码如下：
protected boolean removeEldestEntry(Map.Entry eldest) {
return false;
}
代码很简单，不过注释很长，注释中给了例子：
*
* private static final int MAX_ENTRIES = 100;
*
* protected boolean removeEldestEntry(Map.Entry eldest) {
* return size() > MAX_ENTRIES;
* }
*
可以看出，当我们重写此方法时，如果return size() > MAX_ENTRIES;则可实现当size大于我们设置的变量时，返回true，则可在addEntry方法中调用removeEntryForKey(eldest.key)；将我们需要的数据从map中移除。如果为false，则调用resize()方法，将数组大小翻倍，且重新对entry进行定位，resize方法调用父类方法，代码如下:
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);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
其中transfer(newTable)方法，LinkedHashMap进行了重写，代码与注释如下：
/**
* 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.
*/
void transfer(HashMap.Entry[] newTable) {
int newCapacity = newTable.length;
for (Entry e = header.after; e != header; e = e.after) {
int index = indexFor(e.hash, newCapacity);
e.next = newTable[index];
newTable[index] = e;
}
}
注释大概意思就是重新定位，用它比较快，由于Entry对象是队列连接，因此的确会比HashMap中的方法快一些。
我们平时获取map的值有几种方法，常用的就是map.values()，然后遍历这个集合，然而这个values实际上是一个null，我们去一步步研究下
transient volatileCollectionvalues=null;
public Collection values() {
Collection vs = values;
return (vs != null ? vs : (values = new Values()));
}
private final class Values extends AbstractCollection {
public Iterator iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMap.this.clear();
}
}
会发现，new Values()并没有插入值的操作，而我们调用foreach循环，实际调用的是iterator方法，而该方法返回 return newValueIterator();
可以简单看一下Iterable接口的注释：
/** Implementing this interface allows an object to be the target of
* the "foreach" statement.
比如我们写个简单的循环代码：
Map l = new LinkedHashMap();
for(Object o:l.values()){
System.out.println(o.toString());
}
通过查看字节码：
L0
LINENUMBER 36 L0
NEW java/util/LinkedHashMap
DUP
INVOKESPECIAL java/util/LinkedHashMap. ()V
ASTORE 1
L3
LINENUMBER 37 L3
ALOAD 1
INVOKEINTERFACE java/util/Map.values ()Ljava/util/Collection;
INVOKEINTERFACE java/util/Collection.iterator ()Ljava/util/Iterator;
ASTORE 2
L4
FRAME APPEND [java/util/Map java/util/Iterator]
ALOAD 2
INVOKEINTERFACE java/util/Iterator.hasNext ()Z
IFEQ L1
ALOAD 2
INVOKEINTERFACE java/util/Iterator.next ()Ljava/lang/Object;
ASTORE 3
可以看出 INVOKEINTERFACE java/util/Collection.iterator ()Ljava/util/Iterator;和 INVOKEINTERFACE java/util/Iterator.hasNext ()Z 实际上调用的是Iterator方法。
ValueIterator()方法为linkedHashMap重写的方法：
private class ValueIterator extends LinkedHashIterator {
public V next() { return nextEntry().value; }
}
因此我们得知，返回值为nextEntry().value;其中nextEntry()方法为
Entry nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
Entry e = lastReturned = nextEntry;
nextEntry = e.after;
return e;
}
其中nextEntry 初始化时为Entry nextEntry = header.after;
因此输出时按照从顶端到末端输出其中entry的value值，
总结一下就是：当put时，如果此key已存在(hash相同，可key.equals(已存在key))，根据初始化的accessOrder值是否为true来选择是否将此entry移到链表的尾端。如果key在map中不存在，则插入，
根据removeEldestEntry()方法的返回值是否为true，决定是否将header.next(即链表首端数据)移除，不重写此方法时，默认为false，则如果size大于理论容量threshold时，resize数组；
由此可看出，当我们需要容量大于设定值时，将最不常用数据从map中移除的功能时，需重写removeEldestEntry()方法，且需在构造方法中，定义accessOrder为true，否则实际功能是将最旧的数据移除，而不是最不常用数据。
回顾开头结论:当构造函数不明确定义accessOrder为true时，按照先入先出顺序删除，定义accessOrder为true时，按照不常用数据先出的规则输出
------------------------------------------------------------------------------------
放个大狗镇楼，未经允许，转载必究
网友评论