JDK 1.8 LinkdhashMapソース分析
97061 ワード
ソースはそんなに長くないので、直接貼り付けます.は、Linked HashMapがHashMapから継承されているのを見られます.一方、mapインターフェースの最新のJDK 1.8 hashMapのデータ構造は、配列＋チェーン＋レッドツリーです. Linked HashMapはHashMapのデータ構造に基づいて、双方向チェーン を追加しました. hashMapは無秩序であり、Linked HashMapはこの欠点を補っています.デフォルトは挿入順序で、つまり最後に挿入されたkey-valueは双方向チェーンの末尾に追加されます.accessOrderがtrueであると定義されると、アクセス順であるputkey-valueの後に、getを呼び出して、replacacacacacaccessなどの方法は、ノードをリンクの末尾に配置します.よく使うデータはチェーンの最後にあります. ここでは、RemoveEldest Enterryインターフェースを実現することによって、自分のLRUアルゴリズム、すなわちput key-valueをカスタマイズした後、自分の業務のLRU需要に応じて、最も古いデータノード(すなわち、双方向リンクノードの先頭ノード)を削除することができます.
package java.util;
import java.util.function.Consumer;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.io.IOException;
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
//LinkedHashMap ，
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
// HashMap.Node before，after
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
private static final long serialVersionUID = 3801124242820219131L;
//
transient LinkedHashMapEntry<K,V> head;
//
transient LinkedHashMapEntry<K,V> tail;
// ( entrySet)：
//accessOrder=true
//access-order=false
final boolean accessOrder;
// p
private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
LinkedHashMapEntry<K,V> last = tail; //
tail = p; //
// null
// null
// p
if (last == null)
head = p;
// null
else {
//
p.before = last;
last.after = p;
}
}
// dst src
private void transferLinks(LinkedHashMapEntry<K,V> src,
LinkedHashMapEntry<K,V> dst) {
LinkedHashMapEntry<K,V> b = dst.before = src.before;
LinkedHashMapEntry<K,V> a = dst.after = src.after;
// dst null
if (b == null)
// dst
head = dst;
// dst null
else
// dst dst
b.after = dst;
// dst null
if (a == null)
// dst
tail = dst;
// dst null
else
// dst dst
a.before = dst;
}
// 。 clone readObject
void reinitialize() {
super.reinitialize();
head = tail = null;
}
// HashMap
//
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
//
LinkedHashMapEntry<K,V> p =
new LinkedHashMapEntry<K,V>(hash, key, value, e);
//
linkNodeLast(p);
return p;
}
// HashMap
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMapEntry<K,V> q = (LinkedHashMapEntry<K,V>)p;
//
LinkedHashMapEntry<K,V> t =
new LinkedHashMapEntry<K,V>(q.hash, q.key, q.value, next);
// ，
transferLinks(q, t);
return t;
}
// HashMap
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
//
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
//
// TreeNode LinkedHashMapEntry
// HashMap :
//TreeNode extends LinkedHashMap.LinkedHashMapEntry
linkNodeLast(p);
return p;
}
// HashMap
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
// newNode ， LinkedHashMapEntry
LinkedHashMapEntry<K,V> q = (LinkedHashMapEntry<K,V>)p;
TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
// ，
// TreeNode LinkedHashMapEntry
// HashMap :
//TreeNode extends LinkedHashMap.LinkedHashMapEntry
transferLinks(q, t);
return t;
}
// HashMap LinkedHashMap
//HashMap
void afterNodeRemoval(Node<K,V> e) {
// p = e
// b = p
// a = p
LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e,
b = p.before, a = p.after;
// p ， null
p.before = p.after = null;
// b null，
if (b == null)
// p
head = a;
// b null，
else
// b a
b.after = a;
// a null，
if (a == null)
// p
tail = b;
// a null，
else
// a b
a.before = b;
}
//HashMap
//evict = false ，
void afterNodeInsertion(boolean evict) { // possibly remove eldest
//
LinkedHashMapEntry<K,V> first;
// null removeEldestEntry true
//
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
//HashMap put、replace
// LinkedHashMap put，replace，get ，
//
void afterNodeAccess(Node<K,V> e) {
// last
LinkedHashMapEntry<K,V> last;
// accessOrder true e
if (accessOrder && (last = tail) != e) {
// p = e
// b = p
// a = p
LinkedHashMapEntry<K,V> p =(LinkedHashMapEntry<K,V>)e,
b = p.before, a = p.after;
// p ， p null
p.after = null;
// b null ， p
if (b == null)
// p
head = a;
else
// b a
b.after = a;
// a null，
if (a != null)
// a b
a.before = b;
else
// a null， p
// last b
last = b;
// null ， null
if (last == null)
// p
head = p;
else {
// p last
p.before = last;
//last p
last.after = p;
}
// p， e
tail = p;
++modCount; // 1
}
}
//------------------------------------------------------------
//
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
for (LinkedHashMapEntry<K,V> e = head; e != null; e = e.after) {
s.writeObject(e.key);
s.writeObject(e.value);
}
}
//
//initialCapacity：
//loadFactor：
// accessOrder false
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
//
//initialCapacity：
// accessOrder false
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
//
// accessOrder false
public LinkedHashMap() {
super();
accessOrder = false;
}
//
//m： map
// accessOrder false
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
//
//initialCapacity：
//loadFactor：
//accessOrder：
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
// value
// ， O(n)
public boolean containsValue(Object value) {
for (LinkedHashMapEntry<K,V> e = head; e != null; e = e.after) {
V v = e.value;
if (v == value || (value != null && value.equals(v)))
return true;
}
return false;
}
// get
// HashMap getNode
//getNode null accessOrder true ，
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;
}
// getOrDefault
// HashMap getNode
//getNode null accessOrder true ，
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;
}
// ，
public void clear() {
super.clear();
head = tail = null;
}
// ，
public Map.Entry<K, V> eldest() {
return head;
}
//LinkedHashMap false
// ， ， LinkedHashMap，
// removeEldestEntry
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
// key
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new LinkedKeySet();
keySet = ks;
}
return ks;
}
// KeySet
final class LinkedKeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { LinkedHashMap.this.clear(); }
// LinkedHashMap
public final Iterator<K> iterator() {
return new LinkedKeyIterator();
}
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator<K> spliterator() {
return Spliterators.spliterator(this, Spliterator.SIZED |
Spliterator.ORDERED |
Spliterator.DISTINCT);
}
// ： ->
public final void forEach(Consumer<? super K> action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
//
for (LinkedHashMapEntry<K,V> e = head; (e != null && modCount == mc); e = e.after)
action.accept(e.key);
// LinkedHashMap ( put, remove )，
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
//value
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new LinkedValues();
values = vs;
}
return vs;
}
// value
final class LinkedValues extends AbstractCollection<V> {
public final int size() { return size; }
public final void clear() { LinkedHashMap.this.clear(); }
// LinkedHashMap
public final Iterator<V> iterator() {
return new LinkedValueIterator();
}
public final boolean contains(Object o) { return containsValue(o); }
public final Spliterator<V> spliterator() {
return Spliterators.spliterator(this, Spliterator.SIZED |
Spliterator.ORDERED);
}
public final void forEach(Consumer<? super V> action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
//
for (LinkedHashMapEntry<K,V> e = head; (e != null && modCount == mc); e = e.after)
action.accept(e.value);
// LinkedHashMap ( put, remove )，
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
//
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}
//
final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { return size; }
public final void clear() { LinkedHashMap.this.clear(); }
// LinkedHashMap
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 (LinkedHashMapEntry<K,V> e = head; (e != null && mc == modCount); e = e.after)
action.accept(e);
// LinkedHashMap ( put, remove )，
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
// Map overrides
public void forEach(BiConsumer<? super K, ? super V> action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
for (LinkedHashMapEntry<K,V> e = head; modCount == mc && e != null; e = e.after)
action.accept(e.key, e.value);
// LinkedHashMap ( put, remove )，
if (modCount != mc)
throw new ConcurrentModificationException();
}
public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
if (function == null)
throw new NullPointerException();
int mc = modCount;
for (LinkedHashMapEntry<K,V> e = head; modCount == mc && e != null; e = e.after)
e.value = function.apply(e.key, e.value);
// LinkedHashMap ( put, remove )，
if (modCount != mc)
throw new ConcurrentModificationException();
}
//
abstract class LinkedHashIterator {
// next
LinkedHashMapEntry<K,V> next;
//
LinkedHashMapEntry<K,V> current;
//
// ( put, remove )
// ， expectedModCount != modCount，
int expectedModCount;
LinkedHashIterator() {
next = head; //
expectedModCount = modCount; //expectedModCount
current = null; // ， null
}
//
public final boolean hasNext() {
return next != null;
}
//
final LinkedHashMapEntry<K,V> nextNode() {
//
LinkedHashMapEntry<K,V> e = next;
// LinkedHashMap ( put, remove )
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
// null，
if (e == null)
throw new NoSuchElementException();
//
current = e;
//next
next = e.after;
return e;
}
//
public final void remove() {
//
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
// LinkedHashMap ( put, remove )
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
// null
current = null;
//
K key = p.key;
removeNode(hash(key), key, null, false, false);
//
expectedModCount = modCount;
}
}
//key
final class LinkedKeyIterator extends LinkedHashIterator
implements Iterator<K> {
public final K next() { return nextNode().getKey(); }
}
//value
final class LinkedValueIterator extends LinkedHashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
//Entry
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
}