LinkedHashMap 源码介绍
一、介绍：
LinkedHashMap 和hashMap 功能类似，都是维护的键值对集合，连遍历 以及方法都类似，唯一的区别在于
hashMap 里面的元素是根据hash值来决定存放位置的，是无序的，而LinkedHashMap 维护的是一个按顺序存放的双向链表，是有序的。
所谓的双向链表其实是链表的一种。链表：相当于元素 A->B->C ,也就是我可以通过A 找到B ,从而找到C，可以单向移动。而双向链表：A<->B<->C ，也就是说我可以从B 找到 A 和 C，可以双向移动。
二、源码分析：
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
我们可以看到 这东西是继承的HashMap 的，说明拥有hashMap 的功能，那么我们具体来看看 不同在哪里呢？
1. 构造函数：
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
我们看到3个构造函数，其实都是访问的super(..),也就是hashMap 的构造，区别就在accessOrder
来看看它是什么？
//The iteration ordering method for this linked hash map: <tt>true</tt>
//for access-order, <tt>false</tt> for insertion-order.
// 简单说就是这个用来控制元素的顺序，
// true: 是访问的顺序，也就是谁最先访问，就排在第一位
// false:存放顺序，就是你put 元素的时候的顺序
private final boolean accessOrder;
这里稍后再看怎么用的，我们先来分析核心内部类 Entry 类，这几乎是所有map 都需要的东西。
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// These fields comprise the doubly linked list used for iteration.
// 这里我们看到，Entry<K,V> 类里面多了了两个属性，专门来方便我们进行链表的前后移动 // 的
Entry<K,V> before, after;
// 这里调用了hashMap 的entry 构造，说明还是用的HashMap 的Entry
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
// ..剩下的稍后说
}
继续来看这些属性怎么利用起来的。对于集合，我们肯定要关注他的 存放元素 和 取元素的方法啦： 当我们找遍整个类的时候发现，没有找到put 方法- -。但是LinkedHashMap 肯定是可以调用put的，因为继承了hashMap, 那我们把 hashMap 的put方法先取出来吧
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
// 这里都是调用 hashMap 计算位置什么的，前面hashMap 已经分析过啦
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
// 这里被重写了 A
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 这里被重写了 B
addEntry(hash, key, value, i);
return null;
}
从上面看出和hashMap 没啥区别，关键就看重写的方法啦，特别是e.recordAccess 这个方法 在hashMap 介绍中，不是提到不知道干什么的嘛，这里详细来看看。
private static class Entry<K,V> extends HashMap.Entry<K,V> {
/**
* This method is invoked by the superclass whenever the value
* of a pre-existing entry is read by Map.get or modified by Map.set.
* If the enclosing Map is access-ordered, it moves the entry
* to the end of the list; otherwise, it does nothing.
*/
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
// 如果参数为true,也就是根据访问顺序
if (lm.accessOrder) {
// 迭代控制的变量
lm.modCount++;
remove();
addBefore(lm.header);
}
}
// 这里我们发现 before和after 虽然定义了属性，是哪儿赋值的呢？为什么不为null呢？
// 请回到 构造函数，我们发现有一个init()方法，以前是没用的，这里也进行了重写，请看 // 后面init 方法
private void remove() {
// 先移除当前这个空节点
before.after = after;
after.before = before;
}
/**
* Inserts this entry before the specified existing entry in the list.
*/
private void addBefore(Entry<K,V> existingEntry) {
// 然后将这个空节点 赋值
after = existingEntry;
// 当前节点 ，赋值于标志位的前节点
before = existingEntry.before;
// 然后将复制后的节点的 两个属性，继续赋值为空，等待另一个节点的插入
before.after = this;
after.before = this;
}
// 整个
}
init() 方法：
/**
* The head of the doubly linked list.
*/
private transient Entry<K,V> header;
void init() {
// 这里默链表 表头是header,并让hash值为-1,其他都为null,仅仅是作为一个标志位
// 初始化这个节点
header = new Entry<K,V>(-1, null, null, null);
// 赋值在这里，默认这是起点，相当于还没有其他元素
header.before = header.after = header;
}
可能上面的文字描述很难理解，我们假设：这个双链表结构相当于 一条一节一节连起来的项链，当然每一节肯定有链接前before 和 after 这样的连接位置（属性），中间才是宝石（数据）。然后，一般项链都有一个明显的位置，方便你去下来的（header），那里其实是用来首位相连的，当我们觉得长度不够，需要添加一个宝石的时候，首先会从那里打开，也就是执行（remove）方法，然后把你需要的宝石连接在最后的位置(after = existingEntry,before = existingEntry.before;);，从程序上来说 就是把那个header 的位置，原先连接器的先取掉掉，那个位置就从新连接新的元素。
继续讲解put 方法，继续往下看 还有一个addEntry(hash, key, value, i)方法，也进行了重写
void addEntry(int hash, K key, V value, int bucketIndex) {
// 存放元素
createEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed, else grow capacity if appropriate
Entry<K,V> eldest = header.after;
// 这里始终返回的是false，也就是说 方便我们扩展，重写的- -！
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
if (size >= threshold)
resize(2 * table.length);
}
}
void createEntry(int hash, K key, V value, int bucketIndex) {
// 通过key 和长度 计算出的位置，去获得那个元素，可能为空
HashMap.Entry<K,V> old = table[bucketIndex];
// 然后在这个位置创建一个新元素，并让next 指向old
Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
// 把这个元素放进数组的这个位置
table[bucketIndex] = e;
// 然后把header 的after before属性，和元素节点从新连接起来
// 元素就在header 之前了，也就是可以保证最先访问(这里通过Set 集合遍历顺序是反的- -!)
e.addBefore(header);
size++;
}
上面可以看出，linkedHashMap，元素默认是放在链表前，也就是根据存放顺序放的，而实际情况还是用的hashMap 里面的table 数组，元素位置是随机存放的，只是linkedHashMap扩展，加入了属性，对每个元素存放的位置进行了像链表结构那样的链接。那么当我们设置accessOrder=true 的时候如何才控制根据访问顺序进行排列呢？首先请看get 方法：
} // 也进行了重写
public V get(Object key) {
// 调用父类的get方法
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
// 这里还是调用的刚才的方法，把当前元素放在header 之前，也就完成了 根据访问顺序排序
e.recordAccess(this);
return e.value;
}
上面对该集合实现双链表结构的原理 以及代码大概讲述了一下，可以去看看图例更加清晰，下面继续看看一些方法。
1.keySet()，entrySet（），values方法：
这里还是调用的父类的，但是它重写了几个方法：
// 这是重写的
Iterator<K> newKeyIterator() { return new KeyIterator(); }
Iterator<V> newValueIterator() { return new ValueIterator(); }
terator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
// 这里返回值方式类似，都是通过 nextEntry()返回不同的内容，但是继承对象变成了LinkedHashIterator，不是原来的 // HashIterator
private class KeyIterator extends LinkedHashIterator<K> {
public K next() { return nextEntry().getKey(); }
}
// 看看区别吧
private abstract class LinkedHashIterator<T> implements Iterator<T> {
// 后一个节点
Entry<K,V> nextEntry = header.after;
// 最后返回的节点
Entry<K,V> lastReturned = null;
// 迭代的那个变量控制
int expectedModCount = modCount;
// 如果下一个元素师头元素，说明已经到底呢，没有其他元素了
public boolean hasNext() {
return nextEntry != header;
}
// 获得下一个元素
Entry<K,V> nextEntry() {
// 这里就不明白了，当排序参数设置为true 是，有lm.modCount ++,这里进行.next 迭代的时候，老报错
// 不明白的意义了
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
// 这里元素迭代完了， 直接抛异常- -，不懂为什么这样设计
if (nextEntry == header)
throw new NoSuchElementException();
// 返回下一个元素，并且将nextEntry 指向下下一个元素
Entry<K,V> e = lastReturned = nextEntry;
nextEntry = e.after;
return e;
}
// 删除
public void remove() {
// 这里同上
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
// 这里看出lastReturned 作用就是记录遍历的当前位置，方便删除
// 这里直接调用removeEntryForKey 方法就好了，这个- - 看着不爽，反正又不要返回值
LinkedHashMap.this.remove(lastReturned.key);
lastReturned = null;
expectedModCount = modCount;
}
}
2.containsKey() 这里是访问hashMap 的方法，这里就不说了。
containsValue() 进行了重写
public boolean containsValue(Object value) {
// Overridden to take advantage of faster iterator
// 这里仅仅是通过链表的两个属性进行遍历，hashMap 是通过table 数组进行遍历，效果差不 // 多
if (value==null) {
for (Entry e = header.after; e != header; e = e.after)
if (e.value==null)
return true;
} else {
for (Entry e = header.after; e != header; e = e.after)
if (value.equals(e.value))
return true;
}
return false;
最近我不能直接在iteye 进行编辑，不知道为什么，老是卡死，都是记事本写了，复制过来，没图片和格式，望见谅！
总结：1.linkedhashMap 是继承于hashMap 也就是拥有了他一切功能
2.他是双链表结构，好处可以存取顺序
3.可以进行扩展，用来对那些最近访问元素的优先获得权
4.存放效率，如果构造参数设置为true ，由于要维护链表结构，效率比hashMap 低一点，但是默认是放在最后，能直接从header 进行操作，效率其实没多大影响。
5.get 元素类似。如果构造参数为true ,需要进行链表的操作，效率低于hashMap,否则效率一样。
6.通过Iterator.keySet().iterator() 这样迭代，数据3000000 的情况，数据默认一个数字，linkedhashMap 慢几十毫秒，基本没影响。如果构造参数为true ，则linkedHashMap 迭代异常。
// 我内存不够，i大了要内存溢出
public static void test(){
LinkedHashMap p = new LinkedHashMap(3000000,0.75f,false);
for(int i =0;i<3000000;i++){
p.put(i, 2);
}
long a = System.currentTimeMillis();
Iterator it1 = p.keySet().iterator();
while(it1.hasNext()){
Object o = it1.next();
p.get(o);
}
long b = System.currentTimeMillis();
System.out.println(b-a);// 250 毫秒
}
public static void test2(){
Map m = new HashMap(3000000);
for(int i =0;i<3000000;i++){
m.put(i, 2);
}
long a = System.currentTimeMillis();
Iterator it1 = m.keySet().iterator();
while(it1.hasNext()){
Object o = it1.next();
m.get(o);
}
long b = System.currentTimeMillis();
System.out.println(b-a);// 210 毫秒
}
相关推荐
本资料主要关注Java集合的基础定义以及相关的练习，帮助开发者深入理解和掌握这些概念。 首先，我们来详细讲解Java集合的定义。在Java中，集合是一种容器，可以用来存储一组对象。集合框架包括了接口（如List、Set...
"Java-Interview-超全集合github上评分最高的jiva面试题"就是一个这样的宝藏，它涵盖了Java编程语言、Git版本控制工具以及面试策略等多个方面的知识点。以下是这些内容的详细解析： 1. **Java基础** - **数据类型...
本文将深入探讨Java集合类的汇总，包括List、Set和Map这三大核心接口及其实现类。 首先，让我们从List接口开始。List是一种有序的集合，允许有重复元素，并且支持通过索引来访问元素。ArrayList和LinkedList是List...
本系列深入讲解了Java集合框架中的重要组成部分，包括HashMap、ArrayList、LinkedHashMap、HashSet以及LinkedHashSet。这五个文件分别揭示了这些数据结构的内部实现原理和它们在实际应用中的性能特点。 首先，我们...
教程从简单的编程示例开始，帮助读者快速入门Collections Framework，并逐步深入到集合的数学定义与Java中的Set、Map及Collection之间的差异等更复杂的概念。此外，教程还讨论了Java Collections Framework的历史...
本教程“Java基础第11天-04.Map集合-集合整理”由IT十八掌徐培成讲解，旨在深入解析Map集合的使用和特性。 首先，Map接口中的核心方法包括： 1. `put(key, value)`: 向Map中添加一个键值对。如果键已存在，则会...
在准备大数据面试的过程中，Java基础是必不可少的一部分，尤其聚焦于集合类、多线程和JVM这三大核心领域。下面将分别对这三个方面进行深入探讨。 **一、Java集合类** Java集合框架是处理对象组的重要工具，它包括...
这个"516.514.JAVA基础教程_集合-每天一考(516)"的压缩包很可能是针对Java集合框架的一个学习资源，旨在帮助初学者深入理解和掌握这一关键概念。Java集合框架包括了多种数据结构，如数组、链表、队列、栈、映射等，...
K,V> p) { } 这些方法是 HashMap 为 LinkedHashMap 提供的回调接口，用于在插入、访问和删除节点后执行特定的操作。LinkedHashMap 利用这些回调方法来维护其内部链表的顺序。 1. **afterNodeAccess(Node,V> p)**: ...
本学习笔记由黑马程序员提供，旨在帮助初学者深入理解Java中的集合框架及其使用方法。 首先，我们来探讨“集合”的基本概念。在Java中，集合是一个对象容器，可以容纳多个元素，这些元素可以是任意类型的数据。Java...
在本课程“【IT十八掌徐培成】Java基础第11天-03.Map集合-hash原理2”中，我们将深入探讨Map集合的内部机制，特别是哈希（Hash）原理的应用。这个课程的视频文件名为“Java基础第11天-03.Map集合-hash原理2.avi”。 ...
本文将深入探讨Java集合框架的基础知识，包括接口、类、以及它们在实际开发中的应用。 首先，Java集合框架由一系列接口和实现这些接口的类组成。主要的接口有`List`、`Set`和`Queue`，它们各自代表了不同特性的数据...
这篇博文将深入探讨Java集合框架，包括其基本概念、常见类、接口和实现方式，以及如何进行有效的集合操作。以下是对这些知识点的详细说明： 1. **集合框架**： Java集合框架是一组接口和类，它们提供了在程序中...
《ON JAVA中文版-精读PPT》是一个深入解析Java编程语言的资源，它通过精心设计的PPT形式，提炼了书籍中的核心知识点，旨在帮助读者高效地理解和掌握Java编程技术。作为一款软件/插件学习资料，这个PPT涵盖了Java语言...
在本课程“【IT十八掌徐培成】Java基础第11天-02.Map集合-hash原理”中，将深入探讨Map集合以及其背后的哈希原理。 Map接口不继承Collection接口，而是独立的一类数据结构，其核心方法包括put()用于添加键值对，get...
《Java面试宝典--牛客网》是一份针对Java开发者，特别是应届毕业生和在校生进行校招面试准备的重要参考资料。这份资源由知名在线学习...通过深入学习和实践，你可以全面提升自己的Java技术能力，为面试做好充分准备。