# 简介

LinkedHashSet 也是用了适配器模式，对 LinkedHashMap 进行包装，所以本文主要分析 LinkedHashMap 。

从名字上可以看出容器是 Linked list 和 HashMap 的混合体，可以将 LinkedHashMap 看作采用 linked list 增强的 HashMap。

	public class LinkedHashMap<K,V>
	extends HashMap<K,V>
	implements Map<K,V>
	{
	//...
	}

LinkedHashMap 是 HashMap 的直接子类，它的区别在于在 HashMap 的基础上采用双向链表将所有的数据节点都链接起来了，就是为了保证元素的迭代顺序和插入顺序相同。

还有个好处就是集合迭代时不需要遍历整个 table ，逮着双向链表的 header 遍历即可。

LinkedHashMap 为了性能，是非同步的，多线程下需要手动同步

	// 也可以打包成同步的
	Map m = Collections.synchronizedMap(new LinkedHashMap(...));

# 方法剖析

get 方法和 HashMap 里的没什么区别，不多说。

# put()

插入分为两部分：

将元素插入 table 中，如果有哈希冲突，头插法插入到头部。
将元素插入双向链表中，链表尾部。

其实就是在 HashMap 上加入链表的引用的修改。

LinkedHashMap 使用的节点是 Entrty ，该类继承了 HashMap 的 Node 类。

	static class Entry<K,V> extends HashMap.Node<K,V> {
	Entry<K,V> before, after;
	Entry(int hash, K key, V value, Node<K,V> next) {
	super(hash, key, value, next);
	}
	}

# remove()

删除也有两部分：

将元素从 table 中删除。
将元素从双向链表中删除。

# 经典用法

实现 FIFO 替换策略的缓存， LinkedHashMap 有一个方法，作用是告诉 Map 删除最老的 Entry ，也就是最早插入 Map 的 Entry。

	protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
	return false;
	}

每次插入新元素时 LinkedHashMap 都会询问该函数是否要删除最老的元素，

LinkedHashMap 并没有重写 put 方法，而是重写的 newNode 方法，因为 newNode 就是将要插入的键值对插放到新创建的节点中，在创建节点后马上将其加入到双向链表中即可。

只要在子类中重载该方法，当元素个数超过一定数量时让 removeEldestEntry 返回 true ，就能实现一个固定大小的 FIFO 策略的缓存。其实我们写个子类继承 LinkedList 并重写一下 add 方法也是可以实现的，只是说，是哟个 LinkedHashMap 更加方便。

	/** 一个固定大小的 FIFO 替换策略的缓存 */
	class FIFOCache<K, V> extends LinkedHashMap<K, V>{
	private final int cacheSize;
	public FIFOCache(int cacheSize){
	this.cacheSize = cacheSize;
	}

	// 当 Entry 个数超过 cacheSize 时，删除最老的 Entry
	@Override
	protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
	return size() > cacheSize;
	}
	}

# 参考

https://pdai.tech/md/java/collection/java-map-LinkedHashMap&LinkedHashSet.html
https://blog.csdn.net/u014203449/article/details/80194704

Java基础