容器学习三：LinkedHashMap源码分析

一.LinkedHashMap的存储结构

1. LinkedHashMap是继承HashMap，也就继承了HashMap的结构，也就是图中的结构2，在下文中我用"Entry数组+next链表"来描述。而LinkedHashMap有其自己的变量header，也就是图中的结构1，下文中我用"header链表"来描述。
2. 结构1中的Entry和结构2中的Entry本是同一个，结构1中应该就只有一个header，它指向的是结构2中的e1 e2，但这样会使结构图难画。为了说明问题的方便，我把结构2里的e1 e2在结构1中多画一个。

 

二.LinkedHashMap成员变量

	// LinkedHashMap维护了一个链表，header是链表头。此链表不同于HashMap里面的那个next链表
	private transient Entry<K, V> header;

	// LRU:Least Recently Used最近最少使用算法
	// accessOrder决定是否使用此算法，accessOrder=true使用
	private final boolean accessOrder;

 

三.LinkedHashMap里的Entry对象

        // 继承了HashMap.Entry，其他几个方法边用边分析
	private static class Entry<K, V> extends HashMap.Entry<K, V> {
		// 增加了两个属性，每个Entry有before Entry和after Entry，就构成了一个链表
		Entry<K, V> before, after;

		Entry(int hash, K key, V value, HashMap.Entry<K, V> next) {
			super(hash, key, value, next);
		}

		private void addBefore(Entry<K, V> existingEntry) {
			.....
		}

		void recordAccess(HashMap<K, V> m) {
			.....
		}
		
		void recordRemoval(HashMap<K, V> m) {
			.....
		}
		
		private void remove() {
			.....
		}
	}

 

四.构造函数

	//默认accessOrder为false
	//调用HashMap构造函数
	public LinkedHashMap() {
		super();
		accessOrder = false;
	}

	//如果想实现LRU算法，参考这个构造函数
	public LinkedHashMap(int initialCapacity, float loadFactor,
			boolean accessOrder) {
		super(initialCapacity, loadFactor);
		this.accessOrder = accessOrder;
	}
	
	//模板方法模式，HashMap构造函数里面的会调用init()方法
	//初始化的时候map里没有任何Entry，让header.before = header.after = header
	void init() {
		header = new Entry<K, V>(-1, null, null, null);
		header.before = header.after = header;
	}

 

五.存数据

	//LinkedHashMap没有put(K key, V value)方法，只重写了被put调用的addEntry方法
	//1是HashMap里原有的逻辑，23是LinkedHashMap特有的
	void addEntry(int hash, K key, V value, int bucketIndex) {
		createEntry(hash, key, value, bucketIndex);

		Entry<K, V> eldest = header.after;
		//3.如果有必要，移除LRU里面最老的Entry，否则判断是否该resize
		if (removeEldestEntry(eldest)) {
			removeEntryForKey(eldest.key);
		} else {
			if (size >= threshold)
				resize(2 * table.length);
		}
	}
	
	void createEntry(int hash, K key, V value, int bucketIndex) {
		//1.同HashMap一样：在Entry数组+next链表结构里面加入Entry
		HashMap.Entry<K, V> old = table[bucketIndex];
		Entry<K, V> e = new Entry<K, V>(hash, key, value, old);
		table[bucketIndex] = e;
		//2.把新Entry也加到header链表结构里面去
		e.addBefore(header);
		size++;
	}
	
	//默认是false，我们可以重写此方法
	protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
		return false;
	}

	private static class Entry<K, V> extends HashMap.Entry<K, V> {
		//链表插入元素四个步骤，对着图看
		private void addBefore(Entry<K, V> existingEntry) {
			after = existingEntry;                //1
			before = existingEntry.before;     //2
			before.after = this;                   //3
			after.before = this;                   //4
		}
        }
      
         //如果走到resize，会调用这里重写的transfer
	//HashMap里面的transfer是n * m次运算，LinkedHashtable重写后是n + m次运算
	void transfer(HashMap.Entry[] newTable) {
		int newCapacity = newTable.length;
		//直接遍历header链表，HashMap里面是遍历Entry数组
		for (Entry<K, V> e = header.after; e != header; e = e.after) {
			int index = indexFor(e.hash, newCapacity);
			e.next = newTable[index];
			newTable[index] = e;
		}
	 }

     下面三个图是初始化LinkedHashMap------->添加Entry e1------>添加Entry e2时，LinkedHashMap结构的变化。

 

六.取数据

	//重写了get(Object key)方法
	public V get(Object key) {
		//1.调用HashMap的getEntry方法得到e
		Entry<K, V> e = (Entry<K, V>) getEntry(key);
		if (e == null)
			return null;
		//2.LinkedHashMap牛B的地方
		e.recordAccess(this);
		return e.value;
	}
 
        // 继承了HashMap.Entry
	private static class Entry<K, V> extends HashMap.Entry<K, V> {
		//1.此方法提供了LRU的实现
		//2.通过12两步，把最近使用的当前Entry移到header的before位置，而LinkedHashIterator遍历的方式是从header.after开始遍历，先得到最近使用的Entry
		//3.最近使用是什么意思：accessOrder为true时，get(Object key)方法会导致Entry最近使用；put(K key, V value)/putForNullKey(value)只有是覆盖操作时会导致Entry最近使用。它们都会触发recordAccess方法从而导致Entry最近使用
		//4.总结LinkedHashMap迭代方式：accessOrder=false时，迭代出的数据按插入顺序；accessOrder=true时，迭代出的数据按LRU顺序+插入顺序
		//  HashMap迭代方式：横向数组 * 竖向next链表
		void recordAccess(HashMap<K, V> m) {
			LinkedHashMap<K, V> lm = (LinkedHashMap<K, V>) m;
			//如果使用LRU算法
			if (lm.accessOrder) {
				lm.modCount++;
				//1.从header链表里面移除当前Entry
				remove();
				//2.把当前Entry移到header的before位置
				addBefore(lm.header);
			}
		}
		
		//让当前Entry从header链表消失
		private void remove() {
			before.after = after;
			after.before = before;
		}
        }

 

七.删数据

        // 继承了HashMap.Entry
	private static class Entry<K, V> extends HashMap.Entry<K, V> {
		//LinkedHashMap没有重写remove(Object key)方法，重写了被remove调用的recordRemoval方法
		//这个方法的设计也和精髓，也是模板方法模式
		//HahsMap remove(Object key)把数据从横向数组 * 竖向next链表里面移除之后（就已经完成工作了，所以HashMap里面recordRemoval是空的实现调用了此方法
		//但在LinkedHashMap里面，还需要移除header链表里面Entry的after和before关系
		void recordRemoval(HashMap<K, V> m) {
			remove();
		}
		
		//让当前Entry从header链表消失
		private void remove() {
			before.after = after;
			after.before = before;
		}
	}

 

八.LinkedHashMap EntrySet遍历

        private abstract class LinkedHashIterator<T> implements Iterator<T> {
		//从header.after开始遍历
		Entry<K, V> nextEntry = header.after;
		
		Entry<K, V> nextEntry() {
			if (modCount != expectedModCount)
				throw new ConcurrentModificationException();
			if (nextEntry == header)
				throw new NoSuchElementException();

			Entry<K, V> e = lastReturned = nextEntry;
			nextEntry = e.after;
			return e;
		}
	}

1. 上图中，遍历的结果是先e1然后e2。
2. accessOrder为true时，get(e1.key)或者put(e1.key, value)一下，则结构1变成e2------e1------header，遍历的结果就是先e2然后e1。

 

九.总结

1. LinkedHashMap继承HashMap，结构2里数据结构的变化交给HashMap就行了。
2. 结构1里数据结构的变化就由LinkedHashMap里重写的方法去实现。
3. 简言之：LinkedHashMap比HashMap多维护了一个链表。

 

评论

1 楼 jkguowen 2013-10-31  

非常谢谢作者，看完您的文章后，一切关于LinkedHashMap实现原理的疑惑，都豁然开朗了！然后又看到容器类的其他文章，非常高兴，可以一次过弄明他们的实现原理了