Java 8 HashMapの下位原理の詳細
HashMapの実現原理 概要 属性 方法 getメソッド putメソッド removeメソッド hash方法 resizeメソッド
まとめ
概要
一言も言わずに、ソースコードをクリックすると、次のように紹介されています.Hash table based implementation of the Map interface.This implementation provides all of the optional map operations,and permits null values and the null key.(The HashMap class is roughly equivalent to Hashtable,except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular,it does not guarantethat the order will remain constant over time.翻訳すると、このハッシュテーブルはMapインタフェースに基づいて実現され、null値とnullキーを許可し、スレッドが同期しているのではなく、秩序も保証されていないということになります.
ツールバーの
方法
getメソッド
実装手順は、1、hash値によりkeyがマッピングされたバケツを取得する.2、桶の上のkeyは探しているkeyで、直接命中します.3、バケツのkeyが検索するkeyではない場合、後続ノードを表示します:(1)後続ノードがツリーノードである場合、ツリーを呼び出す方法でそのkeyを検索します.(2)後続ノードがチェーンノードである場合、そのkeyはループループループチェーンによって検索される.
putメソッド
put法は複雑で,実装手順は大体以下の通りである:1,まずhash値からkeyがどのバケツにマッピングされるかを計算する.2、バケツに衝突がない場合は、直接挿入します.3、衝突衝突が発生した場合、衝突を処理する必要がある:(1)バケツが赤黒ツリーを使用して衝突を処理する場合、赤黒ツリーのメソッド挿入を呼び出す.(2)そうでなければ従来のチェーン方式で挿入する.鎖の長さが臨界値に達すると,鎖を赤黒樹に変える.4.バケツに重複するキーがある場合は、そのキーに新しい値を置き換えます.5、sizeが閾値より大きい場合、拡張を行う.
removeメソッド
hashメソッド
getメソッドとputメソッドでは、keyがどのバケツにマッピングされるかを計算してから、その後の操作を行う必要があります.計算の主なコードは次のとおりです.
上のコードのnはハッシュテーブルのサイズを指し、hashはkeyのハッシュ値を指し、hashは次の方法で計算され、keyのhashCode方法はnative方法である二次ハッシュ方式を採用している.
このhashメソッドは、keyのhashCodeメソッドによってハッシュ値を取得し、このハッシュ値とその高い16ビットのハッシュ値とを異ならせるか、または操作して最後のハッシュ値を取得し、計算プロセスは下図を参照することができる.どうしてこんなことをするの?注記では、nが小さい場合、64と仮定すると、n−1は63(0 x 11111)であり、このような値はhashCode()と直接動作し、実際にはハッシュ値の下位6ビットのみが使用される.ハッシュ値の高位変化が大きく,低位変化が小さいと衝突しやすいため,ここでは高低位を利用してこの問題を解決した.この操作によって、HashMapの大きさが2のべき乗次数しか決められないのだから、考えてみれば、2のべき乗次数でなければ、何が起こるのか.HashMapを作成するときに初期サイズを指定しても、HashMapは構築時に次の方法を呼び出してサイズを調整します.
この方法の役割は直感的ではないかもしれないが,その実際の役割はcapを2以上のべき乗次数の最初の数にすることである.例えば、16か16か、13は16に調整され、17は32に調整されます.
resizeメソッド
HashMapは,拡張を行う際に用いられるrehash方式が非常に巧みである.拡張のたびに2倍になるため,元の計算(n−1)&hashの結果に比べてbitビットが1つ増えただけであるため,ノードは元の位置にあるか,「元の位置+旧容量」という位置に割り当てられる.例えば、元の容量が32であれば、hashと31(0 x 1111)を持って操作すべきである.64の容量に拡張した後、hashと63(0 x 11111)を持って操作すべきである.新しい容量は従来に比べて1つのbitビットだけ増加し、元の位置が23であると仮定すると、新規のbitビットの計算結果が0の場合、ノードは23になる.逆に、計算結果が1の場合、そのノードは23+31のバケツに割り当てられます.このような巧みなrehash方式だからこそ、rehashの後に各バケツのノード数が元のバケツのノード数以下になることを保証し、すなわちrehashの後により深刻な衝突が起こらないことを保証する.
ここで注意すべき点は、ハッシュテーブルのバケツが閾値を超えると拡張することを指摘する文章があり、これは間違っている.実際には,ハッシュテーブルのキー値対個数が閾値を超えると拡張される.
まとめ
赤と黒の木でハッシュの衝突を処理するのは初めて見ました!ハッシュを学んだことがあって、赤い黒い木を学んだことがあって、2つが結合してこのように使うことができるとは思わなかった!従来のファスナー法では衝突を解決し,1つのバケツでの衝突が深刻であればハッシュテーブルの効率をO(n)に低下させ,赤黒木により効率をO(logn)に改善できる.チェーン構造のノードに比べて、ツリー構造のノードは比較的多くの空間を占有するため、空間で時間を変える改良方式である.
また次回...
概要
一言も言わずに、ソースコードをクリックすると、次のように紹介されています.Hash table based implementation of the Map interface.This implementation provides all of the optional map operations,and permits null values and the null key.(The HashMap class is roughly equivalent to Hashtable,except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular,it does not guarantethat the order will remain constant over time.翻訳すると、このハッシュテーブルはMapインタフェースに基づいて実現され、null値とnullキーを許可し、スレッドが同期しているのではなく、秩序も保証されていないということになります.
ツールバーの
// 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 8
static final int TREEIFY_THRESHOLD = 8;
// 6
static final int UNTREEIFY_THRESHOLD = 6;
//
transient Node<K,V>[] table;
//
transient int size;
//
transient int modCount;
// capacity*load factor ， size ，
int threshold;
//
final float loadFactor;
// ， ，
static final int MIN_TREEIFY_CAPACITY = 64;
/** Node ， HashMap ，
Node 。 ，Node 4 ， key
value ， hash next 。hash key ，next
。*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() {
return key; }
public final V getValue() {
return value; }
public final String toString() {
return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
方法
getメソッド
//get getNode ， getNode
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;
// && key
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//
if (first.hash == hash && // always check first node
((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);
// ， ， key
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
}
実装手順は、1、hash値によりkeyがマッピングされたバケツを取得する.2、桶の上のkeyは探しているkeyで、直接命中します.3、バケツのkeyが検索するkeyではない場合、後続ノードを表示します:(1)後続ノードがツリーノードである場合、ツリーを呼び出す方法でそのkeyを検索します.(2)後続ノードがチェーンノードである場合、そのkeyはループループループチェーンによって検索される.
putメソッド
//put putVal ， putVal
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// ，
if ((tab = table) == null || (n = tab.length) == 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;
// key key ，
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// ， putTreeVal
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//
else {
// ， key
for (int binCount = 0; ; ++binCount) {
// key， HashMap
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// TREEIFY_THRESHOLD ，
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// ，
if (e != null) {
// existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
}
put法は複雑で,実装手順は大体以下の通りである:1,まずhash値からkeyがどのバケツにマッピングされるかを計算する.2、バケツに衝突がない場合は、直接挿入します.3、衝突衝突が発生した場合、衝突を処理する必要がある:(1)バケツが赤黒ツリーを使用して衝突を処理する場合、赤黒ツリーのメソッド挿入を呼び出す.(2)そうでなければ従来のチェーン方式で挿入する.鎖の長さが臨界値に達すると,鎖を赤黒樹に変える.4.バケツに重複するキーがある場合は、そのキーに新しい値を置き換えます.5、sizeが閾値より大きい場合、拡張を行う.
removeメソッド
//remove removeNode ， removeNode
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;
// key
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;
if (p.hash == hash &&
// key，
((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);
// ，
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// key value
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;
afterNodeRemoval(node);
return node;
}
}
return null;
}
hashメソッド
getメソッドとputメソッドでは、keyがどのバケツにマッピングされるかを計算してから、その後の操作を行う必要があります.計算の主なコードは次のとおりです.
(n - 1) & hash
上のコードのnはハッシュテーブルのサイズを指し、hashはkeyのハッシュ値を指し、hashは次の方法で計算され、keyのhashCode方法はnative方法である二次ハッシュ方式を採用している.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>>16);
このhashメソッドは、keyのhashCodeメソッドによってハッシュ値を取得し、このハッシュ値とその高い16ビットのハッシュ値とを異ならせるか、または操作して最後のハッシュ値を取得し、計算プロセスは下図を参照することができる.どうしてこんなことをするの?注記では、nが小さい場合、64と仮定すると、n−1は63(0 x 11111)であり、このような値はhashCode()と直接動作し、実際にはハッシュ値の下位6ビットのみが使用される.ハッシュ値の高位変化が大きく,低位変化が小さいと衝突しやすいため,ここでは高低位を利用してこの問題を解決した.この操作によって、HashMapの大きさが2のべき乗次数しか決められないのだから、考えてみれば、2のべき乗次数でなければ、何が起こるのか.HashMapを作成するときに初期サイズを指定しても、HashMapは構築時に次の方法を呼び出してサイズを調整します.
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;
}
この方法の役割は直感的ではないかもしれないが,その実際の役割はcapを2以上のべき乗次数の最初の数にすることである.例えば、16か16か、13は16に調整され、17は32に調整されます.
resizeメソッド
HashMapは,拡張を行う際に用いられるrehash方式が非常に巧みである.拡張のたびに2倍になるため,元の計算(n−1)&hashの結果に比べてbitビットが1つ増えただけであるため,ノードは元の位置にあるか,「元の位置+旧容量」という位置に割り当てられる.例えば、元の容量が32であれば、hashと31(0 x 1111)を持って操作すべきである.64の容量に拡張した後、hashと63(0 x 11111)を持って操作すべきである.新しい容量は従来に比べて1つのbitビットだけ増加し、元の位置が23であると仮定すると、新規のbitビットの計算結果が0の場合、ノードは23になる.逆に、計算結果が1の場合、そのノードは23+31のバケツに割り当てられます.このような巧みなrehash方式だからこそ、rehashの後に各バケツのノード数が元のバケツのノード数以下になることを保証し、すなわちrehashの後により深刻な衝突が起こらないことを保証する.
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;
return oldTab;
}
//
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {
// zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// resize
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) {
oldTab[j] = null;
// ，
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// ，
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// preserve order
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) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
ここで注意すべき点は、ハッシュテーブルのバケツが閾値を超えると拡張することを指摘する文章があり、これは間違っている.実際には,ハッシュテーブルのキー値対個数が閾値を超えると拡張される.
まとめ
赤と黒の木でハッシュの衝突を処理するのは初めて見ました!ハッシュを学んだことがあって、赤い黒い木を学んだことがあって、2つが結合してこのように使うことができるとは思わなかった!従来のファスナー法では衝突を解決し,1つのバケツでの衝突が深刻であればハッシュテーブルの効率をO(n)に低下させ,赤黒木により効率をO(logn)に改善できる.チェーン構造のノードに比べて、ツリー構造のノードは比較的多くの空間を占有するため、空間で時間を変える改良方式である.
また次回...