Java源码之LinkedHashMap
Java源码之LinkedHashMap
转载请注明出处：http://blog.csdn.net/itismelzp/article/details/50554412
一、LinkedHashMap概述
LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现与 HashMap 的不同之处在于，LinkedHashMap维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序（插入顺序）。注意，如果在映射中重新插入键，则插入顺序不受影响。（如果在调用 m.put(k, v) 前 m.containsKey(k) 返回了 true，则调用时会将键 k 重新插入到映射 m 中。）
注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。
二、数据结构
数组 + 双链表结构
/**
* 双链表结点Entry，继承自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);
}
}
三、LinkedHashMap源码
1.头文件
package java.util;
import java.util.function.Consumer;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.io.IOException;
2.继承与实现关系
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
3.属性
/**
* 双链表的头结点
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* 双链表的尾结点
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* 迭代顺序
* true:访问顺序
* false:插入顺序
*/
final boolean accessOrder;
4.构造方法
/**
* 构造方法一：
* 指定初始容量和装载因子
* 顺序规则：插入顺序
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
/**
* 构造方法二：
* 指定初始容量并使用默认装载因子（0.75）
* 顺序规则：插入顺序
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
/**
* 构造方法三：
* 使用默认初始容量（16）和默认装载因子（0.75）
* 顺序规则：插入顺序
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
/**
* 构造方法四：
* 使用指定Map来构造
* 顺序规则：插入顺序
*/
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
/**
* 构造方法五：
* 指定初始容量、装载因子和顺序规则构造
*
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
5.方法
(1) 存储数据
LinkedListHashMap并未重写HashMap中的put方法。
具体实现可参考【Java源码之HashMap】中put与putValue方法。
(2) 读取数据
/**
* 如果key存在返回对应的value
* 如果key不存在返回指定的null
*/
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
/**
* 如果key存在返回对应的value
* 如果key不存在返回指定的defaultValue
*/
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return defaultValue;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
6.迭代
集合中的类都有一个共同的迭代方式，就是先把这个集合转化成Set视图，然后再对这个Set视图进行迭代。
/**
* 返回一个包含此Map所有元素的Set视图（实际是LinkedEntrySet类）
* 改变Map也会改变视图
*/
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}
/**
* 内部类LinkedEntrySet
* 里面封闭了迭代方法
*/
final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { return size; }
public final void clear() { LinkedHashMap.this.clear(); }
public final Iterator<Map.Entry<K,V>> iterator() {
return new LinkedEntryIterator();
}
public final boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Node<K,V> candidate = getNode(hash(key), key);
return candidate != null && candidate.equals(e);
}
public final boolean remove(Object o) {
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Object value = e.getValue();
return removeNode(hash(key), key, value, true, true) != null;
}
return false;
}
public final Spliterator<Map.Entry<K,V>> spliterator() {
return Spliterators.spliterator(this, Spliterator.SIZED |
Spliterator.ORDERED |
Spliterator.DISTINCT);
}
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
action.accept(e);
if (modCount != mc)
throw new ConcurrentModificationException();
}
}