HashMap実装の詳細
6631 ワード
HashMapは、keyがnullであることを可能にし、valueがnullであることを可能にするハッシュテーブルのMap非スレッドセキュリティバージョンの実装である.ハッシュテーブルとは、ハッシュ関数によってkeyのハッシュ値を計算し、そのハッシュ値を使用して対応するvalueが存在する位置を特定することである.ハッシュ値の競合(複数のkeyが同じハッシュ値を生成する)が発生した場合、一定の競合処理方法で正の真のvalue位置に位置決めされ、検索されたvalue値に戻ります.一般的なハッシュテーブルの内部では、ハッシュ関数を使用してkey対応配列の位置を計算し、処理バースト法を使用して真のvalueを見つけ、返します.したがって、ハッシュテーブルを実現する最も主要な問題は、ハッシュ関数と衝突処理方法を選択することであり、良いハッシュ関数はデータ分布をよりばらばらにすることができ、それによって衝突の可能性を減らすことができ、良い衝突処理方法は衝突処理をより速くすることができ、できるだけデータ分布をよりばらばらにすることができ、将来の衝突処理方法に影響を与えない.
厳蔚敏、呉偉明バージョンの「データ構造(C言語版)」で提供されるハッシュ関数は:1.直接アドレス法(線形関数法);2.デジタル分析法;3.平方取中法;4.折りたたみ法5.除算剰余法6.乱数法.JDKのHashMapではシフトイソOR法を用いて残留数(および2のn乗則'&'操作)を除いた.HashMap内部のデータ構造はEntry
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}
上記の説明から、新しいキー値ペアの追加は、keyを使用して内部配列のインデックス値(index)を計算する2つの部分に分けられることがわかります.2.インデックスの配列bucketにEntryチェーンが既に存在し、チェーンに新しく追加されたkeyの値が既に存在する場合、既存の値を新しく追加された値に設定し、古い値を返します.3.それ以外の場合、新しいEntryインスタンスを作成し、そのインスタンスを元のチェーンのヘッダに挿入します.4.Entryインスタンスを新たに追加すると、現在のsizeがバルブ値(capacity*loadFactor)を超えると、配列容量が自動的に2倍に拡大し、配列拡張時に元の存在するすべてのEntryがインデックス値を再計算し、Entryチェーンの順序も逆転します(同じチェーンにある場合).新しく追加したEntryのインデックス値も再計算されます.5.keyがnullの場合、デフォルト配列のインデックス値は0であり、他の論理は変わらない.
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
検索と追加は類似しており、まずkeyに基づいて配列のインデックス値(keyがnullの場合、インデックス値は0)を計算し、そのインデックス値に対応するEntryチェーンを順番に検索し、Entryチェーンで等しいkeyが見つかった場合、対応するEntryレコードが見つかったことを示し、そうでない場合、見つからなかったことを示し、nullを返す.get()操作に対してEntryのValue値を返し、containsKey()操作に対してレコードがあるかどうかを判断し、両方の方法でgetEntry()メソッドを呼び出します.
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
一方、containsValue()操作のようなvalue検索では、テーブル全体(配列遍歴と配列内のEntryチェーン遍歴)が必要であるため、この検索の効率が低く、コード実装も簡単である.
除去除去除去操作(remove()も、key値によって配列内のインデックス番号(keyがnullの場合はインデックス番号0)を先に計算し、Entryチェーンを見つけ、Entryチェーン内のEntryを検索し、そのEntryを削除します.
HashMapでは、まず配列を巡回し、null以外のEntryインスタンスを検索し、Entryが存在する配列インデックスを記録し、次のnext()操作で次のnull以外のEntryを検索し続け、前に検索したnull以外のEntryを返します.遍歴時にHashMapの内容を変更することはできません(既存のレコードの値を更新できますが、既存のレコードを追加、削除することはできません)、HashMapはmodCountフィールドを記録し、追加または削除操作が有効になるたびにmodCountを自己増加させ、HashIteratorの作成時に現在のmodCount値(expectedModCount)を記録します.遍歴中(next()、remove()操作の場合、HashMapのmodCountは格納されているexpectedModCountとは異なり、HashMapが修正されたことを示し、ConcurrentModificationExceptionを放出します.いわゆるfail fastの原則です.HashMapで返されるkey,value,Entryの集合は,いずれもこのIteratorに基づいて実現されており,実現は比較的簡単で,詳しくは述べない.
注意:1.clear()操作によるメモリの問題-clear()操作は配列内のすべての項目をnullに設定するだけで、配列自体のサイズは変更されません.したがって、HashMapが大きなデータを格納している場合、clear()を呼び出すのは良い方法ではありません.2.Bucketsはコード内のtable配列であり、各要素はEntryチェーンであるためbucketsと呼ぶ
まとめ
HashMap.hash(int n)は、keyのオブジェクトとして提供されるhashCode()をさらに混同し、その「ランダム度」を高め、hash mapを挿入する際のhash衝突を減らそうとするものである.「hash衝突」とは次のindexFor()と関係がある.
HashMap.indexFor(int n,int length)は、計算されたhash値に基づいて、HashMapの「バックボーン」であるbucket配列(HashMap.Entry配列として実装される)から対応するbucketを見つける.Java.util.HashMapはbucket配列の長さが2のべき乗であることを保証するので、本来はindex=n%lengthと書くべきである
の場合、index=n&(length-1)と書くことができます.
両者はlengthが2のべき乗で等価である.
2つのhash値が同じindexを算出すると、「hash競合」--2つのキー値ペアが同じbucketに挿入されます.一般的な解法は2つあります.
*オープンhash map:bucket配列を骨幹とし、各bucketにはhashのようなキー値ペアを格納するチェーンテーブルが掛けられています.チェーンテーブルを使わずに例えばツリーを使う変種がありますが、どうせ「オープン」で要素を追加できるデータ構造であればいいのです.
*閉鎖式hash map:bucket配列が主体で、衝突すると線形に後ろに配列の中で次の空のbucketを探して挿入します;検索操作も同様です.
JAva.util.HashMapはオープンデザインです.Hash競合が多ければ多いほどアクセス効率に影響を与えるため、できるだけ避けなければならない.
hashcodeもVMに依存し、VM用オブジェクトメモリアドレスがある.
HashMapとHashTableのデフォルトサイズの違い:
Hashtableのデフォルトサイズが11であるのは、(近似)質量数を除いた分散効果が良いためである:java-Why initialCapacity of Hashtable is 11 while the DEFAULT_INITIAL_CAPACITY in HashMap is 16 and requires a power of 2 Hashtableの拡張は、次のようにします.
int oldCapacity = table.length;
int newCapacity = oldCapacity * 2 + 1;
capacityが質量数であることは保証されませんが、少なくとも奇数であることは保証されています.Hashtableのアドレスは、Entry tab[]=table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
直接keyのhashCode()を使うのは、HashMapでhashの分散効果を増強するために二次hashを作るのとは違います(ここではJDK 6版を使用していますが、古い方が便利です):
/**
* Applies a supplemental hash function to a given hashCode, which
* defends against poor quality hash functions. This is critical
* because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
int hash = (key == null) ? 0 : hash(key.hashCode()); // hash
table[indexFor(hash, table.length)]