Java之LinkedHashMap

LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变，LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用get方法)的链表。默认是按插入顺序排序，如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。可以重写removeEldestEntry方法返回true值指定插入元素时移除最老的元素。

如果我们设置这个LinkedHashMap是基于访问顺序，且重写它的removeEldestEntry，那就等于实现了LRU算法。

来看如下代码和实际效果

public static void test1() {
	int initialCapacity = 10;//初始化容量
	float loadFactor = 0.75f;//加载因子，一般是 0.75f
	boolean accessOrder = true; //排序方式 false 基于插入顺序  true  基于访问顺序
	Map<String, Integer> map = new LinkedHashMap<>(initialCapacity, loadFactor, accessOrder);
	for (int i = 0; i < 10; i++) {
		map.put(String.valueOf(i), i);
	}
	//访问前顺序
	for (Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator(); it.hasNext(); ) {
		Map.Entry<String, Integer> next = it.next();
		System.out.println("linkedMap--before-->" + next.getKey());
	}

	System.out.println("**********************************");

	// 模拟访问
	map.get("2");

	//访问后数据
	for (Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator(); it.hasNext(); ) {
		Map.Entry<String, Integer> next = it.next();
		System.out.println("linkedMap--after-->" + next.getKey());
	}
}

输出效果

linkedMap--before-->0
linkedMap--before-->1
linkedMap--before-->2
linkedMap--before-->3
linkedMap--before-->4
linkedMap--before-->5
linkedMap--before-->6
linkedMap--before-->7
linkedMap--before-->8
linkedMap--before-->9
**********************************
linkedMap--after-->0
linkedMap--after-->1
linkedMap--after-->3
linkedMap--after-->4
linkedMap--after-->5
linkedMap--after-->6
linkedMap--after-->7
linkedMap--after-->8
linkedMap--after-->9
linkedMap--after-->2

可以看到，当元素2被访问后，它的顺序发生了改变。

实现LRU算法，来看下removeEldestEntry方法介绍

This method typically does not modify the map in any way, instead allowing the map to modify itself as directed by its return value. It is permitted for this method to modify the map directly, but if it does so, it must return false (indicating that the map should not attempt any further modification). The effects of returning true after modifying the map from within this method are unspecified.
This implementation merely returns false (so that this map acts like a normal map - the eldest element is never removed).
Params:
eldest – The least recently inserted entry in the map, or if this is an access-ordered map, the least recently accessed entry. This is the entry that will be removed it this method returns true. If the map was empty prior to the put or putAll invocation resulting in this invocation, this will be the entry that was just inserted; in other words, if the map contains a single entry, the eldest entry is also the newest.
Returns:
true if the eldest entry should be removed from the map; false if it should be retained.

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

默认它是不会自动去移除的，如果直接返回false，如果需要实现自动移除，则重写该方法。

看如下代码和效果

public static void test2() {
	int initialCapacity = 10;//初始化容量
	float loadFactor = 0.75f;//加载因子，一般是 0.75f
	boolean accessOrder = true; //排序方式 false 基于插入顺序  true 基于访问顺序
	Map<String, Integer> map = new LinkedHashMap(initialCapacity, loadFactor, accessOrder) {
		protected boolean removeEldestEntry(Map.Entry eldest) {
			return size() > initialCapacity;
		}
	};
	for (int i = 0; i < 15; i++) {
		if(i == 12){
			// 模拟访问
			map.get("2");
		}
		map.put(String.valueOf(i), i);
	}
	//访问前顺序
	for (Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator(); it.hasNext(); ) {
		Map.Entry<String, Integer> next = it.next();
		System.out.println("linkedMap--before-->" + next.getKey());
	}
}

输出内容

linkedMap--before-->6
linkedMap--before-->7
linkedMap--before-->8
linkedMap--before-->9
linkedMap--before-->10
linkedMap--before-->11
linkedMap--before-->2
linkedMap--before-->12
linkedMap--before-->13
linkedMap--before-->14

因为这是一个定长的Map，而且我们重写了移除方法，移除方法内判断，如果当前Map的数量大于设定容量了，就返回true，此时就会发生移除。

在设置值时模拟访问了一下元素2，发现2访问后排在了11后面，因此它没有被移除。

推荐您阅读更多有关于“ map HashMap LinkedHashMap LRU 链表 ”的文章

猜你喜欢

• 2-11HTTP POST数据和数据接收
• 2-11常用SpringJPA主键生成策略，UUID和自增
• 2-11Apache Commons Jar包下载
• 2-11IIS服务器返回Bad Request (Invalid Hostname)解决办法
• 2-11SpringJPA 慎重 findAll() 切记分页