HashMapソース解析（JDK 8）
88391 ワード
前言
この時間は空いています。特に基礎を補いました。よく使う
概要 どん底部は、ハッシュバケットと呼ばれる配列を実現することによって、配列内に配置されたのは単一のチェーンテーブルである。 ハッシュバケットの容量は2の二乗であり、挿入位置を計算する際に、直接ビット演算と代替取外し動作とを用いて効率を向上させることが目的である。 デフォルトの拡張方式は容量*2、閾値*2であり、要素を追加するとチェーン長>=8に変換され、赤と黒のツリーに変換され、検索効率が向上し、拡張されると赤と黒のツリーの要素<=6に戻る。拡張後の元素の下の表示はhashと上の古い容量から計算します。もし==0ならば、低いレベルで表示されます。0は上位では元の下付き+元の容量を表します。 は、反復の順序が無秩序であることをサブジェネレータから分かります。バケツの下付きスケーリングは小さい時から大きい時まで、チェーンは前から後へ反復します。 keyのハッシュ値は 本文
続いて構造の方法、増加、削除、変更、調査、反復の順序によって説明します。ソースコードを見ると比較的に味気ないですが、大丈夫です。これから始めましょう。
作成方法構造方法は、負荷係数 拡張方法 は、新しい容量としきい値を計算し、デフォルトの容量16しきい値12を計算し、その後、拡張する方法は*2 である。は、新しいバケットを作成し、元の要素を新しいバケットに入れます。新しいバケットを挿入するときの下付きは、ハッシュ値と古い容量から導出され、下位の場合は下付きが不変で、上位の場合は下付き＋元の容量として表示されます。 増やす、直す
増と改は同じ方法です。ここで一緒に話します。 keyのハッシュ値は、 put要素の場合、まずこの位置に要素があるかどうかを判断し、直接挿入していないか、あるいはハッシュが衝突した場合、keyのハッシュ値が同じかどうかを比較し、keyが等しいかを比較し、同じデフォルトの場合はvalueを置換し、チェーンの末尾または赤と黒の木を挿入しなければ、チェーンの長さが8以上であれば、赤と黒の木になる。追加が完了したら、sizeが 削除
調べます
巡回は、キーペアのセットを
締め括りをつける どん底部は、ハッシュバケットと呼ばれる配列を実現することによって、配列内に配置されたのは単一のチェーンテーブルである。 ハッシュバケットの容量は2の二乗であり、挿入位置を計算する際に、直接ビット演算と代替取外し動作とを用いて効率を向上させることが目的である。 デフォルトの拡張方式は容量*2、閾値*2であり、要素を追加するとチェーン長>=8に変換され、赤と黒のツリーに変換され、検索効率が向上し、拡張されると赤と黒のツリーの要素<=6に戻る。拡張後の元素の下の表示はhashと上の古い容量から計算します。もし==0ならば、低いレベルで表示されます。0は上位では元の下付き+元の容量を表します。 は、反復の順序が無秩序であることをサブジェネレータから分かります。バケツの下付きスケーリングは小さい時から大きい時まで、チェーンは前から後へ反復します。 keyのハッシュ値は 注意深い学友はこれが総括して前の概説のcopyなことを発見するかもしれなくて、間違いなく私はこのように大胆に承認して、でもソースコードを見た後に更にこの総括を見にきてもっと多い体得があることができることを信じます。
この時間は空いています。特に基礎を補いました。よく使う
ArrayList、LinkedList、HashMap、LinkedHashMapのソースコードを見ました。LruCacheは比較的簡単です。単独で紹介しません。Listは2つのページを使って、それぞれMapと（HashMap+LruCache）を紹介します。LinkedHashMapはLruCacheで実現されるので、ルルと一緒に紹介します。概要
LinkedHashMapはキーペアを格納するための容器であり、key固有のvalueは繰り返してもよく、スレッドが安全ではなく、巡回中に無秩序である。HashMap方式で戻るだけでなく、shcodeの上位レベルも挿入バケットの下付きの計算に参加してハッシュ衝突を低減することができます。hashCode()方式でInt型の値を返しているので、Int取得範囲は2の32乗と上（私たちのバケット数−1）の計算に下付きの基準を挿入する方式です。デフォルトの場合は下位ビットのみ演算に参加します。hashCode()方法で戻ってきた値が唯一であっても、低ビット参加演算のみが衝突の可能性を大きく増大させるので、ハッシュ衝突の可能性を低減するために、摂動関数処理下において高いレベルにも参加させる必要がある。続いて構造の方法、増加、削除、変更、調査、反復の順序によって説明します。ソースコードを見ると比較的に味気ないですが、大丈夫です。これから始めましょう。
作成方法
static final int MAXIMUM_CAPACITY = 1 << 30;//
transient Node<K,V>[] table;//
final float loadFactor;// threshold = .length * loadFactor
int threshold;// resize()
static final float DEFAULT_LOAD_FACTOR = 0.75f;//
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)//
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)//
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))//
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;//
this.threshold = tableSizeFor(initialCapacity);// tableSizeFor ， threshold ， 。
}
// ， >=cap 2 n ，
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);// 0.75
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {// map map
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
hashCode()と容量を初期化することであることが分かります。一般的に、ローディング係数はデフォルトの0.75を使用しています。次に、第4の構成方法のloadFactor方法を参照してください。 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();// map size
if (s > 0) {//
if (table == null) { //
float ft = ((float)s / loadFactor) + 1.0F;//
int t = ((ft < (float)MAXIMUM_CAPACITY) ?//
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);// >=t 2 n
}
else if (s > threshold)// size threshold
resize();//
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {//for
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);//put map
}
}
}
putMapEntries()の拡大とresize()の増加、putVal()の後には、ここでは非常に重要な拡大方法putVal()を先に見ます。 final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//
int oldCap = (oldTab == null) ? 0 : oldTab.length;//
int oldThr = threshold;//
int newCap, newThr = 0;//
if (oldCap > 0) {//
if (oldCap >= MAXIMUM_CAPACITY) {//
threshold = Integer.MAX_VALUE;// Integer.MAX_VALUE,
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)// *2
newThr = oldThr << 1; // *2
}
else if (oldThr > 0) // ，
newCap = oldThr;// ， oldThr newCap ， 。
else {//
newCap = DEFAULT_INITIAL_CAPACITY;// 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);// 12
}
if (newThr == 0) {// else if newThr 0
float ft = (float)newCap * loadFactor;//
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);//
}
/**
* ， 16 12， *2。
*
*/
threshold = newThr;//
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//
table = newTab;//
if (oldTab != null) {//
for (int j = 0; j < oldCap; ++j) {//
Node<K,V> e;
if ((e = oldTab[j]) != null) {// null e
oldTab[j] = null;//
if (e.next == null)//
newTab[e.hash & (newCap - 1)] = e;// hash -1
else if (e instanceof TreeNode)//
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);//
else { //
Node<K,V> loHead = null, loTail = null;//
Node<K,V> hiHead = null, hiTail = null;//
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {//hash ==0 ，
if (loTail == null)// null
loHead = e;//
else
loTail.next = e;// e
loTail = e;// e
}
else {//
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);// null
if (loTail != null) {//
loTail.next = null;
newTab[j] = loHead;// j
}
if (hiTail != null) {//
hiTail.next = null;
newTab[j + oldCap] = hiHead;// j+
}
}
}
}
}
return newTab;
}
resize()で説明しました。簡単にまとめます。resize()と容量を初期化したものであり、構造方法においては、容量が最初はloadFactor変数に格納されているのがおかしいが、後にthresholdに値を与えて閾値を再計算するので問題ない。threshold実装は、2つのステップに分けることができます。増と改は同じ方法です。ここで一緒に話します。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
newCap方法を参照してください。 static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
static final int TREEIFY_THRESHOLD = 8;//
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i// tab， p， n， i
if ((tab = table) == null || (n = tab.length) == 0)// 0
n = (tab = resize()).length;//
if ((p = tab[i = (n - 1) & hash]) == null)//
tab[i] = newNode(hash, key, value, null);//
else {//
Node<K,V> e; K k;// e key
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))// key hash ， key 。
e = p;// p e
else if (p instanceof TreeNode)//
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// key hash ，key e
else {//
for (int binCount = 0; ; ++binCount) {//
if ((e = p.next) == null) {// null
p.next = newNode(hash, key, value, null);//
if (binCount >= TREEIFY_THRESHOLD - 1) // 8
treeifyBin(tab, hash);//
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))// key
break;
p = e;
}
}
if (e != null) { // key
V oldValue = e.value;//
if (!onlyIfAbsent || oldValue == null)// ，
e.value = value;// value
afterNodeAccess(e);
return oldValue;//
}
}
++modCount;// ++
if (++size > threshold)// size
resize();//
afterNodeInsertion(evict);
return null;
}
resize()方式によって取得されることに加えて、hash()は、高レベルでハッシュ衝突を低減することもできる。^ (h >>> 16)閾値以上であるかどうかを判断し、大きければ、拡張容量が大きくなる。 public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;// tab ，p ，n ，index
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {// ，
Node<K,V> node = null, e; K k; V v;//node
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))//
node = p;
else if ((e = p.next) != null) {//
if (p instanceof TreeNode)//
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);// key
else {//
do {//
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {// key
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {//
if (node instanceof TreeNode)//
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);//
else if (node == p)//
tab[index] = node.next;//
else//
p.next = node.next;//
++modCount;//
--size;// size
afterNodeRemoval(node);
return node;//
}
}
return null;
}
調べます
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {// ，
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))//
return first;//
if ((e = first.next) != null) {//
if (first instanceof TreeNode)//
return ((TreeNode<K,V>)first).getTreeNode(hash, key);//
do {//
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
巡回は、キーペアのセットを
hashCode()方法で取得したものである。 public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
...
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
...
}
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }// next nextNode()
}
abstract class HashIterator {//
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { //
do {} while (index < t.length && (next = t[index++]) == null);// null next
}
}
public final boolean hasNext() {// next
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {// next ， null
do {} while (index < t.length && (next = t[index++]) == null);// null next
}
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
締め括りをつける
^ (h >>> 16)はキーペアを格納するための容器であり、key固有のvalueは繰り返してもよく、スレッドが安全ではなく、巡回中に無秩序である。threshold方式で戻るだけでなく、shcodeの上位レベルも挿入バケットの下付きの計算に参加してハッシュ衝突を低減することができます。entrySet()方式でInt型の値を返しているので、Int取得範囲は2の32乗と上（私たちのバケット数−1）の計算に下付きの基準を挿入する方式です。デフォルトの場合は下位ビットのみ演算に参加します。HashMap方法で戻ってきた値が唯一であっても、低ビット参加演算のみが衝突の可能性を大きく増大させるので、ハッシュ衝突の可能性を低減するために、摂動関数処理下において高いレベルにも参加させる必要がある。