LinkedHashMap源码分析。
/**
* Map 接口的哈希表和链接列表实现,具有可预知的迭代顺序。此实现与 HashMap 的不同之处在于,
* 后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,
* 该迭代顺序通常就是将键插入到映射中的顺序(插入顺序)。注意,如果在映射中重新插入 键,则插入顺序不受影响。
* (如果在调用 m.put(k, v) 前 m.containsKey(k) 返回了 true,
* 则调用时会将键 k 重新插入到映射 m 中。)
* 此实现可以让客户避免未指定的、由 HashMap(及 Hashtable)所提供的通常为杂乱无章的排序工作,
* 同时无需增加与 TreeMap 相关的成本。使用它可以生成一个与原来顺序相同的映射副本,而与原映射的实现无关:
* void foo(Map m) {
* Map copy = new LinkedHashMap(m);
* ...
* }
* 如果模块通过输入得到一个映射,复制这个映射,然后返回由此副本确定其顺序的结果,这种情况下这项技术特别有用。
* (客户通常期望返回的内容与其出现的顺序相同。)
* 提供特殊的构造方法来创建链接哈希映射,该哈希映射的迭代顺序就是最后访问其条目的顺序,
* 从近期访问最少到近期访问最多的顺序(访问顺序)。这种映射很适合构建 LRU 缓存。
* 调用 put 或 get 方法将会访问相应的条目(假定调用完成后它还存在)。
* putAll 方法以指定映射的条目集迭代器提供的键-值映射关系的顺序,为指定映射的每个映射关系生成一个条目访问。
* 任何其他方法均不生成条目访问。特别是,collection 视图上的操作不 影响底层映射的迭代顺序。
* 可以重写 removeEldestEntry(Map.Entry) 方法来实施策略,
* 以便在将新映射关系添加到映射时自动移除旧的映射关系。
* 此类提供所有可选的 Map 操作,并且允许 null 元素。
* 与 HashMap 一样,它可以为基本操作(add、contains 和 remove)提供稳定的性能,
* 假定哈希函数将元素正确分布到桶中。由于增加了维护链接列表的开支,其性能很可能比 HashMap 稍逊一筹,
* 不过这一点例外:LinkedHashMap 的 collection 视图迭代所需时间与映射的大小 成比例。
* HashMap 迭代时间很可能开支较大,因为它所需要的时间与其容量 成比例。
* 链接的哈希映射具有两个影响其性能的参数:初始容量和加载因子。它们的定义与 HashMap 极其相似。
* 要注意,为初始容量选择非常高的值对此类的影响比对 HashMap 要小,因为此类的迭代时间不受容量的影响。
* 注意,此实现不是同步的。如果多个线程同时访问链接的哈希映射,而其中至少一个线程从结构上修改了该映射,
* 则它必须 保持外部同步。这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象,
* 则应该使用 Collections.synchronizedMap 方法来“包装”该映射。
* 最好在创建时完成这一操作,以防止对映射的意外的非同步访问:
* Map m = Collections.synchronizedMap(new LinkedHashMap(...));
* 结构修改是指添加或删除一个或多个映射关系,或者在按访问顺序链接的哈希映射中影响迭代顺序的任何操作。
* 在按插入顺序链接的哈希映射中,仅更改与映射中已包含键关联的值不是结构修改。
* 在按访问顺序链接的哈希映射中,仅利用 get 查询映射不是结构修改。)
* Collection(由此类的所有 collection 视图方法所返回)的 iterator 方法返回的迭代器
* 都是快速失败 的:在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器自身的 remove 方法,
* 其他任何时间任何方式的修改,迭代器都将抛出 ConcurrentModificationException。
* 因此,面对并发的修改,迭代器很快就会完全失败,而不冒将来不确定的时间任意发生不确定行为的风险。
* 注意,迭代器的快速失败行为无法得到保证,因为一般来说,不可能对是否出现不同步并发修改做出任何硬性保证。
* 快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。
* 因此,编写依赖于此异常的程序的方式是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误。
* @param <K> 由此映射维护的键的类型
* @param <V> 映射值的类型
*/
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
private static final long serialVersionUID = 3801124242820219131L;
// 双链表的头。
private transient Entry<K,V> header;
// 这个链接哈希映射的迭代排序方法:true for 访问顺序(access-ordered), false for 插入顺序(insertion-order)。
private final boolean accessOrder;
/**
* 构造一个带指定初始容量和加载因子的空插入顺序 LinkedHashMap 实例。
* @param initialCapacity 初始容量
* @param loadFactor 加载因子
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
/**
* 构造一个带指定初始容量和默认加载因子 (0.75) 的空插入顺序 LinkedHashMap 实例。
* @param initialCapacity 初始容量
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
/**
* 构造一个带默认初始容量 (16) 和加载因子 (0.75) 的空插入顺序 LinkedHashMap 实例。
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
/**
* 构造一个映射关系与指定映射相同的插入顺序 LinkedHashMap 实例。
* 所创建的 LinkedHashMap 实例具有默认的加载因子 (0.75) 和足以容纳指定映射中映射关系的初始容量。
* @param m 要将其映射关系存放在此映射中的映射
*/
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super(m);
accessOrder = false;
}
/**
* 构造一个带指定初始容量、加载因子和排序模式的空 LinkedHashMap 实例。
* @param initialCapacity 初始容量
* @param loadFactor 加载因子
* @param accessOrder 排序模式 - 对于访问顺序,为 true;对于插入顺序,则为 false
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
/**
* 由超类构造函数和伪构造函数(clone、readObject)在将任何条目(entry)插入映射之前调用。初始化链。
*/
@Override
void init() {
header = new Entry<>(-1, null, null, null);
header.before = header.after = header;
}
/**
* 将所有项传输到新表数组。此方法由超类resize()方法调用。为了提高性能,它被重写,因为使用链表迭代更快。
* @param newTable 与当前对象相关联的新table[]
* @param rehash 是否计算条目(entry)的哈希值
*/
@Override
void transfer(HashMap.Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e = header.after; e != header; e = e.after) {// 遍历链表
if (rehash)// 是否计算条目(entry)的哈希值
e.hash = (e.key == null) ? 0 : hash(e.key);
int index = indexFor(e.hash, newCapacity);// 返回哈希码e.hash在表中的索引。
e.next = newTable[index];
newTable[index] = e;
}
}
/**
* 如果此映射将一个或多个键映射到指定值,则返回 true。
* 覆盖:类 HashMap<K,V> 中的 containsValue
* @param value 其在此映射中的存在已经测试的值
* @return 如果此映射将一个或多个键映射到指定值,则返回 true
*/
public boolean containsValue(Object value) {
// 重写以利用更快的迭代器
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;
}
/**
* 返回此映射到指定键的值。如果此映射中没有该键的映射关系,则返回 null 。
* 更确切地讲,如果此映射包含满足 (key==null ? k==null : key.equals(k))
* 的从键 k 到值 v 的映射关系,则此方法返回 v;否则,返回 null。
* (最多只能有一个这样的映射关系。)
* 返回 null 值并不 一定 表明此映射不包含该键的映射关系;也可能此映射将该键显式地映射为 null。
* 可使用 containsKey 操作来区分这两种情况。
* 覆盖:类 HashMap<K,V> 中的 get
* @param key 要返回其关联值的键
* @return V 指定键所映射的值;如果此映射不包含该键的映射关系,则返回 null
*/
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this); // 记录存取
return e.value;
}
/**
* 从该映射中移除所有映射关系。此调用返回后映射将为空。
* 覆盖:类 HashMap<K,V> 中的 clear
*/
public void clear() {
super.clear();// 调用HashMap.clear()方法
header.before = header.after = header;
}
/**
* LinkedHashMap entry.
*/
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// 这些字段包含用于迭代的双链表。
Entry<K,V> before, after;
/**
* 创建新条目
* @param hash 哈希值
* @param key 键
* @param value 值
* @param next 下一个条目
*/
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
/**
* 从链表中移除此条目(entry)。
* 即:上一个条目的after指向当前条目的after,下一个条目的before指向当前条目的before。
*/
private void remove() {
before.after = after;
after.before = before;
}
/**
* 将此条目插入到列表中指定的现有条目之前。
*/
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
/**
* 每当Map.get()读取已存在条目的值时,超类就会调用此方法。通过Map.set获取或修改。
* 如果所包围的映射是访问顺序(access-ordered)的,则将该条目移动到列表的末尾;否则,它什么也做不了。
*/
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {// 如果是访问顺序
lm.modCount++;
remove();// 从链表中移除此条目(entry)。
addBefore(lm.header);// 将此条目插入到列表中指定的现有条目(lm.header)之前。
}
}
/**
* 从链表中移除此条目(entry)。
* @param m
*/
void recordRemoval(HashMap<K,V> m) {
remove();
}
}
private abstract class LinkedHashIterator<T> implements Iterator<T> {
Entry<K,V> nextEntry = header.after;
Entry<K,V> lastReturned = null;
/**
* 迭代器认为支持列表应该具有的modCount值。如果违反了此期望,迭代器将检测到并发修改。
*/
int expectedModCount = modCount;
/**
* 如果仍有元素可以迭代,则返回 true。
*/
public boolean hasNext() {
return nextEntry != header;
}
/**
* 从迭代器指向的 collection 中移除迭代器返回的最后一个元素(可选操作)。
*/
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
// 调用HashMap.remove()方法,
LinkedHashMap.this.remove(lastReturned.key);
lastReturned = null;
expectedModCount = modCount;
}
/**
* 返回下一个条目
* @return
*/
Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
Entry<K,V> e = lastReturned = nextEntry;
nextEntry = e.after;
return e;
}
}
/**
* key迭代器
*/
private class KeyIterator extends LinkedHashIterator<K> {
public K next() { return nextEntry().getKey(); }
}
/**
* value迭代器
*/
private class ValueIterator extends LinkedHashIterator<V> {
public V next() { return nextEntry().value; }
}
/**
* 条目迭代器
*/
private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() { return nextEntry(); }
}
// 这些重写改变了超类视图的iterator()方法的行为
Iterator<K> newKeyIterator() { return new KeyIterator(); }
Iterator<V> newValueIterator() { return new ValueIterator(); }
Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
/**
* 此重写更改超类.put()方法的行为。它使新分配的项插入到链表的末尾,并在适当的情况下删除最年长的条目(the eldest entry)。
* @param hash 根据键计算的哈希值
* @param key 指定值将要关联的键
* @param value 指定键将要关联的值
* @param bucketIndex 在table[]数组上的索引
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);
// 如果有指令,则删除最年长的(eldest )条目(entry)
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {// 如果此映射移除其最旧的条目(eldest),则返回 true。
removeEntryForKey(eldest.key);// 调用HashMap.removeEntryForKey(),删除并返回与LinkedHashMap中指定键关联的条目。
}
}
/**
* 此重写与addEntry()的不同之处在于,它不会调整表的大小或删除最老的条目(the eldest entry)。
* @param hash 根据键计算的哈希值
* @param key 指定值将要关联的键
* @param value 指定键将要关联的值
* @param bucketIndex 在table[]数组上的索引
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);// 将此条目插入到列表中指定的现有条目(header)之前。
size++;
}
/**
* 如果此映射移除其最旧的条目,则返回 true。在将新条目插入到映射后,put 和 putAll 将调用此方法。
* 此方法可以提供在每次添加新条目时移除最旧条目的实现程序。
* 如果映射表示缓存,则此方法非常有用:它允许映射通过删除旧条目来减少内存损耗。
* 示例用法:此重写允许映射增加到 100 个条目,然后每次添加新条目时删除最旧的条目,始终维持 100 个条目的稳定状态。
* private static final int MAX_ENTRIES = 100;
* protected boolean removeEldestEntry(Map.Entry eldest) {
* return size() > MAX_ENTRIES;
* }
* 此方法通常不以任何方式修改映射,相反允许映射在其返回值的指引下进行自我修改。
* 使用此方法直接修改映射是 允许的,但是如果它执行了此操作,则一定 返回 false(表示该映射不应进行任何进一步的修改)。
* 在此方法中修改映射后是否返回 true 是不确定的。
* 此实现仅返回 false(这样,此映射的行为将类似于正常映射,即永远不能移除最旧的元素)。
* @param eldest 在映射中最早插入的条目;如果是访问顺序映射,则为最早访问的条目。
* 如果此方法返回 true,则此为将移除的条目。如果导致此调用的 put 或 putAll 调用之前映射为空,
* 则该条目就是刚刚插入的条目;换句话说,如果映射只包含单个条目,则最旧的条目也是最新的条目。
* @return 如果应该从映射移除最旧的条目,则返回 true;如果应该保留,则返回 false。
*/
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
}
参考:JDK 1.6 API
还没有评论,来说两句吧...