Java 容器源码分析之Map-Set-List（10）

look_w

LinkedHashMap 的实现原理LinkedHashMap 概述HashMap 是无序的，HashMap 在 put 的时候是根据 key 的 hashcode 进行 hash 然后放入对应的地方。所以在按照一定顺序 put 进 HashMap 中，然后遍历出 HashMap 的顺序跟 put 的顺序不同（除非在 put 的时候 key 已经按照 hashcode 排序号了，这种几率非常小）
JAVA 在 JDK1.4 以后提供了 LinkedHashMap 来帮助我们实现了有序的 HashMap！
LinkedHashMap 是 HashMap 的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用 LinkedHashMap。
LinkedHashMap 是 Map 接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
LinkedHashMap 实现与 HashMap 的不同之处在于，LinkedHashMap 维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。
注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。
根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用 get 方法)的链表。默认是按插入顺序排序，如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。
小 Demo我在最开始学习 LinkedHashMap 的时候，看到访问顺序、插入顺序等等，有点晕了，随着后续的学习才慢慢懂得其中原理，所以我会先在进行做几个 demo 来演示一下 LinkedHashMap 的使用。看懂了其效果，然后再来研究其原理。
HashMap看下面这个代码：
[url=][/url]
public static void main(String[] args) {    Map<String, String> map = new HashMap<String, String>();    map.put("apple", "苹果");    map.put("watermelon", "西瓜");    map.put("banana", "香蕉");    map.put("peach", "桃子");    Iterator iter = map.entrySet().iterator();    while (iter.hasNext()) {        Map.Entry entry = (Map.Entry) iter.next();        System.out.println(entry.getKey() + "=" + entry.getValue());    }}[url=][/url]

一个比较简单的测试 HashMap 的代码，通过控制台的输出，我们可以看到 HashMap 是没有顺序的。
banana=香蕉apple=苹果peach=桃子watermelon=西瓜LinkedHashMap我们现在将 map 的实现换成 LinkedHashMap，其他代码不变：Map<String, String> map = new LinkedHashMap<String, String>();
看一下控制台的输出：
apple=苹果watermelon=西瓜banana=香蕉peach=桃子我们可以看到，其输出顺序是完成按照插入顺序的！也就是我们上面所说的保留了插入的顺序。我们不是在上面还提到过其可以按照访问顺序进行排序么？好的，我们还是通过一个例子来验证一下：
[url=][/url]
public static void main(String[] args) {    Map<String, String> map = new LinkedHashMap<String, String>(16,0.75f,true);    map.put("apple", "苹果");    map.put("watermelon", "西瓜");    map.put("banana", "香蕉");    map.put("peach", "桃子");    map.get("banana");    map.get("apple");    Iterator iter = map.entrySet().iterator();    while (iter.hasNext()) {        Map.Entry entry = (Map.Entry) iter.next();        System.out.println(entry.getKey() + "=" + entry.getValue());    }}[url=][/url]

代码与之前的都差不多，但我们多了两行代码，并且初始化 LinkedHashMap 的时候，用的构造函数也不相同，看一下控制台的输出结果：watermelon=西瓜peach=桃子banana=香蕉apple=苹果这也就是我们之前提到过的，LinkedHashMap 可以选择按照访问顺序进行排序。