LinkedHashMap就是在HashMap的基础之上,再将每个元素用双向链表连接起来,如此,可以设定两种连接顺序,一种是按照元素的插入的顺序进行连接,另一种是LRU算法(最近最少使用)次序,即对于没有访问过的元素将出现在链表的前面,而访问过的元素被调整到链表的后面
http://blog.csdn.net/turkeyzhou/article/details/3201513
LinkedHashMap中的entry是继承HashMap的entry,但是增加了before和after的指针
private static class Entry<K,V> extends HashMap.Entry<K,V> { //他有两个指针分别指向了before和after的Entry //<span style="color:#ff0000;">请注意,不要把next和他们混淆了,next的用处还是和HashMap中一</span>//样; 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) { LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; if (lm.accessOrder) { lm.modCount++; remove(); addBefore(lm.header); } } void recordRemoval(HashMap<K,V> m) { remove(); } }
因为LinkedHashMap是继承的HashMap,那么他们的增删改的操作基本一致,只是利用了模板模式具有了不同的实现;
我们来看一下put方法吧;
下面是HashMap的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<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++; addEntry(hash, key, value, i); return null; }
void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); }
在LinkedHashMap中被重载的方法是addEntry;
- void addEntry(int hash, K key, V value, int bucketIndex) {
- createEntry(hash, key, value, bucketIndex);
- Entry<K,V> eldest = header.after;
- if (removeEldestEntry(eldest)) {
- removeEntryForKey(eldest.key);
- } else {
- if (size >= threshold)
- resize(2 * table.length);
- }
- }
- void createEntry(int hash, K key, V value, int bucketIndex) {
- //和以前一样,首先操作了table序列的链表枝条;
- HashMap.Entry<K,V> old = table[bucketIndex];
- Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
- table[bucketIndex] = e;
- //关键在于这一步做了什么;我们知道他在header之前插入了Entry;
- e.addBefore(header);
- size++;
- }
Header元素在构造的时候被初始化,记得吗,这个方法是HashMap在构造函数中利用模板模式传下来的
- void init() {
- header = new Entry<K,V>(-1, null, null, null);
- header.before = header.after = header;
- }
开始的时候Header头尾都是指向自身的;
第二步的时候就是被e.addBefore(header);
- private void addBefore(Entry<K,V> existingEntry) {
- after = existingEntry;
- before = existingEntry.before;
- before.after = this;
- after.before = this;
- }
如果再put那么就是:
我们再来看一看他的keySet是如何得到的:
重载了newKeyIterator() 的方法:
- Iterator<K> newKeyIterator() { return new KeyIterator(); }
我们看一下迭代器是如何实现的:
- private abstract class LinkedHashIterator<T> implements Iterator<T> {
- //从开始的图3我们可见,第一次加入的节点是位于header.after的位置;
- Entry<K,V> nextEntry = header.after;
- Entry<K,V> lastReturned = null;
- int expectedModCount = modCount;
- //nextnEntry不是header就不是末尾
- public boolean hasNext() {
- return nextEntry != header;
- }
- public void remove() {
- if (lastReturned == null)
- throw new IllegalStateException();
- if (modCount != expectedModCount)
- throw new ConcurrentModificationException();
- LinkedHashMap.this.remove(lastReturned.key);
- lastReturned = null;
- expectedModCount = modCount;
- }
- Entry<K,V> nextEntry() {
- if (modCount != expectedModCount)
- throw new ConcurrentModificationException();
- if (nextEntry == header)
- throw new NoSuchElementException();
- //指针沿着after往下走
- Entry<K,V> e = lastReturned = nextEntry;
- //预先把nextEntry移动到了下一位
- nextEntry = e.after;
- return e;
- }
- }
把next方法抽象出去是因为values和keySet的迭代次序是一样的,就是返回的数值不同,所以可以把
Entry的遍历方式推到上层,而values和keys分别留给子类实现;
- private class KeyIterator extends LinkedHashIterator<K> {
- public K next() { return nextEntry().getKey(); }
- }
- private class KeyIterator extends LinkedHashIterator<K> {
- public K next() { return nextEntry().getKey(); }
- }
- private class ValueIterator extends LinkedHashIterator<V> {
- public V next() { return nextEntry().value; }
- }
- private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
- public Map.Entry<K,V> next() { return nextEntry(); }
- }
package tst; import java.util.HashMap; import java.util.LinkedHashMap; import java.util.Map; class CachedMap<K,V> extends LinkedHashMap<K,V> { private int maxEntres; /* * */ public CachedMap(int initCap, int maxEnt) { super(initCap); maxEntres = maxEnt; } @Override protected boolean removeEldestEntry(Map.Entry<K,V> eldest ) { boolean flag = false; if (size() > maxEntres ) { //System.out.println("rm "+eldest.getKey()); flag = true; } return flag; } } public class Tar { public static void iterClc(Map<String,String> mp) { for (Map.Entry<String, String> ent : mp.entrySet()) { System.out.print(ent.getKey() + ":" + ent.getValue()+" "); } System.out.println(); } public static void main(String[] args) throws Exception{ Map<String, String> mp1 = new HashMap<String,String>(); Map<String, String> cm = new CachedMap<String, String>(3, 5); mp1.put("1b", "dd"); mp1.put("34", "vc"); mp1.put("rt", "ae"); mp1.put("yu", "ao"); mp1.put("pu", "21"); //iterClc(mp1); System.out.println(); cm.put("1b", "dd"); cm.put("34", "vc"); cm.put("rt", "ae"); cm.put("yu", "ao"); cm.put("pu", "21"); //iterClc(cm); cm.put("py", "dd"); //iterClc(cm); cm.put("34", "vd"); // iterClc(cm); cm.put("oy", "87"); iterClc(cm); String val = cm.get("pu"); cm.remove("pu"); System.out.println("rm"); iterClc(cm); cm.put("nss", "caac"); iterClc(cm); } }
output:
rt:ae yu:ao pu:21 py:dd oy:87
rm
rt:ae yu:ao py:dd oy:87
rt:ae yu:ao py:dd oy:87 nss:caac
上面的例子重载了LinkedHashMap的removeEldestEntry函数,在原始定义中,
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
经过重载之后,我们的数据结构就成了一个cache,一旦原始个数超过给定的数目,就会把最先放入map的元素删除
值得注意的是,如果put一个key值相同的,原有的value就要被替换,但是这个entry的顺序不变化
在放入"34":"vd"之前,“34”:“vc”是最老的元素,放入之后,"34":"vd"成为最老的元素,所以再放入新元素,会把"34":"vd"给删除。