java基础进阶篇(七)_LinkedHashMap------【java源码栈】
- 一.概述
- 二.特点
- 三.应用场合
- 四.构造方法
- 1.参数为空
- 2.accessOrder
- 五.源码结构分析
- 六.常见问题
- 1.如何实现的元素有序?
- 2.如何保证顺序的正确以及同步
- 3.如何实现两种顺序(插入顺序或者访问顺序)?
- 4.为什么重写containsValue()而不重写containsKey()?
- 七.常用方法
一.概述
??LinkedHashMap是HashMap的子类，关于HashMap可以看下前面的章节：
public class LinkedHashMap
extends HashMap
implements Map
二.特点
- 非线程安全
- LinkedHashMap 内部保证顺序; 分插入顺序和访问排序两种, 如果是访问顺序，那put和get操作已存在的Entry时，都会把Entry移动到双向链表的表尾(其实是先删除再插入)。 HashMap不保证插入顺序.
- LinkedHashMap存取数据，还是跟HashMap一样使用的Entry[]的方式，双向链表只是为了保证顺序。
- LinkedHashMap是继承于HashMap，是基于HashMap和双向链表来实现的。
- LinkedHashMap的插入顺序和访问顺序可以由开发者自己决定.
三.应用场合
??HashMap是无序的，当我们希望有顺序(保证插入顺序)地去存储key-value时，就需要使用LinkedHashMap了.
使用HashMap:
Map hashMap = new HashMap();
hashMap.put(1, "a1");
hashMap.put(3, "a3");
hashMap.put(2, "a2");
hashMap.put(0, "a0");
Set> set = hashMap.entrySet();
Iterator> iterator = set.iterator();
while (iterator.hasNext()) {
Entry entry = iterator.next();
Integer key = (Integer) entry.getKey();
String value = (String) entry.getValue();
System.out.println("key:" + key + ",value:" + value);
}
输出结果:
key:0,value:a0
key:1,value:a1
key:2,value:a2
key:3,value:a3
??HashMap 给key做了排序, 不能保证插入顺序, 当有插入顺序的需求时, 就轮到LinkedHashMap 登场了.
使用LinkedHashMap:
Map hashMap = new LinkedHashMap();
hashMap.put(1, "a1");
hashMap.put(3, "a3");
hashMap.put(2, "a2");
hashMap.put(0, "a0");
Set> set = hashMap.entrySet();
Iterator> iterator = set.iterator();
while (iterator.hasNext()) {
Entry entry = iterator.next();
Integer key = (Integer) entry.getKey();
String value = (String) entry.getValue();
System.out.println("key:" + key + ",value:" + value);
}
??输出结果:
key:1,value:a1
key:3,value:a3
key:2,value:a2
key:0,value:a0
??完美保证了插入时的顺序.
四.构造方法
??LinkedHashMap继承了HashMap，所以它们有很多相似的地方。
??在这儿我们只看参数为空 和修改排序模式的两种构造方法.
1.参数为空
/**
* Constructs an empty insertion-ordered LinkedHashMap instance
* with the default initial capacity (16) and load factor (0.75).
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
??默认初始容量是16, 负载因子是0.75. 这里调用了super() 即HashMap的构造方法.
accessOrder设置为false，表示不是访问顺序而是插入顺序存储的，这也是默认值，表示LinkedHashMap中存储的顺序是按照调用put方法插入的顺序进行排序的。LinkedHashMap也提供了可以设置accessOrder的构造方法.
2.accessOrder
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
??通过例子来看下参数accessOrder 在插入顺序和访问顺序上的作用.
true的情况:
Map hashMap = new LinkedHashMap(16,0.75f,true);
hashMap.put(1, "a1");
hashMap.put(3, "a3");
hashMap.put(2, "a2");
hashMap.put(0, "a0");
Set> set = hashMap.entrySet();
Iterator> iterator = set.iterator();
while (iterator.hasNext()) {
Entry entry = iterator.next();
Integer key = (Integer) entry.getKey();
String value = (String) entry.getValue();
System.out.println("key:" + key + ",value:" + value);
}
??输出结果:
key:1,value:a1
key:3,value:a3
key:2,value:a2
key:0,value:a0
??accessOrder 等于true: 保证了插入顺序. 前面的例子,默认为false的情况, 保证了访问顺序即对key进行了排序.
五.源码结构分析
??LinkedHashMap 实现了Map
??默认情况，遍历时的顺序是按照插入节点的顺序。这也是其与HashMap最大的区别。
??也可以在构造时传入accessOrder参数，使得其遍历顺序按照访问的顺序输出。
??LinkedHashMap的实现主要分两部分，一部分是哈希表，另外一部分是链表。
??可以理解为带链表的数组, 哈希表是由数组+链表组成的, 长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢? 一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。
??HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解，一个线性的数组怎么实现按键值对来存取数据呢？这里HashMap有做一些处理。
??首先HashMap里面实现一个静态内部类Entry，其重要的属性有 key , value, next，从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean，我们上面说到HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。
??下面是HashMap 的结构, 也可以理解成单向链表结构,(个人自定义的名称, 便于理解勿喷)
??而LinkedHashMap 的双向链表结构如下:(作者自涂鸦)
??红色箭头表示节点Entry 之间是双向的, 回到主题, 为什么LinkedHashMap不重写containsKey()?
??比如我们拥有 1 处 的key 和value, 从1 -> 2, 需要经历3个步骤
??1.把key 转换成hash 值
??2.把hash值转换成索引,方便在主干查找到对应的数组下标.(描述不准确,是这个意思)
??3.没完呢, 还得根据key 或者是转化后的hash去查找所在下标处的Entry.
三个步骤等于回到了ArrayList 的原始数组时代.
??再次重申,便于理解,高手请指教勿喷.
七.常用方法
??常用方法请参照前面的章节: [ java基础进阶篇(七)_LinkedHashMap------【java源码栈】][]