3、ハッシュテーブル
HashHashTableとHashMapは、一般的にハッシュ、ハッシュ、またはハッシュとして翻訳され、任意の長さの入力は、ハッシュアルゴリズムを介して出力の固定長に変換され、出力はハッシュ値である。
--拡張: ハッシュ・アルゴリズムにMD5,SHA,CRCが使われている。
配列がなければハッシュテーブルもないと言える。
ハッシュ関数は、ハッシュとして定義することができ、キーは要素のキー値を表し、ハッシュの値はハッシュ関数によって計算されたハッシュ値を表す。
HashTable extends Dictionary implements Map<K,V>, Cloneable
transient Entry<?,?>[] table; //ノードの配列を保存する
transient int count; //
int threshold; //hashTable展開のしきい値
float loadFactor; //閾値の計算に使われる負荷係数、デフォルトは0.75
transient int modCount = 0; //構造体の破壊を実行するための修正回数は、HashTableとHashMapをトラバースする際の急激な失敗と関係している。
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //最大容量、2の31乗 - 9
private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Entry<K,V> next;
//コンストラクタ
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
}
HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>,Cloneable{
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //デフォルトの初期化容量16
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; //デフォルトの負荷係数は0.75f
static final int TREEIFY_THRESHOLD = 8; //連鎖表を木に変換する閾値
static final int UNTREEIFY_THRESHOLD = 6; //ツリーを連鎖表に変換する閾値
static final int MIN_TREEIFY_CAPACITY = 64; //ツリーへの変換のための最小容量のしきい値
transient Node<K,V>[] table; //ノードの配列を保存する
transient Set<Map.Entry<K,V>> entrySet; //すべてのノードが保存される
transient int size; //保存されるノードの数
transient int modCount; //イテレータの高速障害に使用される修正数
int threshold; //拡張のしきい値
final float loadFactor; //負荷係数
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;
}
}
}
ハッシュの衝突：ハッシュの衝突はなぜ起こるのでしょうか？ハッシュアルゴリズムは固定された限られた長さのハッシュ値を生成します。例えば、先に引用したMD5の例では、ハッシュ値は固定された128ビットのバイナリ文字列であり、ハッシュされるデータは無限であるのに対し、2 ^ 128までの限られた数のデータを表現することができます。
解決策
- オープン・アドレッシング
-- 例：ThreadLocalMapはリニア・プロービングによるオープン・アドレス指定で競合を解決します。
- 利点：オープンアドレッシングでは、ハッシュテーブルのデータが配列に格納されるため、CPUキャッシュを効果的に使用してクエリを高速化できます。さらに、この方法で実装されたハッシュテーブルはシリアライズが容易です。連鎖リスト法ではポインタが含まれるため、シリアライズが容易ではありません。
- 欠点：オープンアドレス方式で競合を解決するハッシュテーブルは、データの削除が面倒で、削除されたデータに特別なマークを付ける必要があります。また、オープンアドレス方式では、すべてのデータが配列に格納されるため、連鎖リスト方式に比べて競合に対するコストが高くなります。そのため、オープンアドレス法を用いて競合を解決するハッシュテーブルでは、負荷率の上限をあまり大きくすることはできません。この結果、この方法は連鎖表方式よりもメモリ空間を浪費することにもなります。
- まとめ：データ量が比較的少なく、負荷率が小さい場合は、オープンアドレッシング方式を使うのが適しています。JavaのThreadLocalMapがハッシュの衝突を解決するためにオープンアドレッシングを使用する理由もここにあります。
- 連鎖表法
--例: LinkedHashMapは、競合を解決するために連鎖テーブルメソッドを使用します。
- 利点：連鎖表法はオープン・アドレッシング法よりもメモリ効率が高いです。これは、連鎖テーブル・ノードは必要なときに作成でき、オープン・アドレッシング法のように事前に要求する必要がないためです。また、大きなロードファクターにも耐性があります。
- 欠点：連鎖表はポインタを格納する必要があるため、小さなオブジェクトを格納するためにメモリを消費し、メモリ消費量が2倍になる可能性があります。また、連鎖表のノードはメモリ上に点在しており、連続的ではないため、CPUのキャッシュと相性が悪く、この点も実行効率に一定の影響を与えます。
- 要約：連鎖表をベースとしたハッシュ競合処理方式は、大きなオブジェクトと大きなデータ量のハッシュ表を格納するのに適しており、オープンアドレス方式と比較して、より柔軟で、連鎖表の代わりに赤黒木を使用するなど、より多くの最適化戦略をサポートしています。
- ハッシュ関数の設計に関しては、ハッシュされた値がランダムで均等になるように最善を尽くすべきです。そうすれば、ハッシュの衝突を最小限に抑えることができますし、衝突が起こった後でも、各スロットに割り当てられるデータはより均等になります。また、ハッシュ関数の設計は複雑にしすぎてはいけません。複雑にしすぎると時間がかかりすぎ、ハッシュテーブルの性能にも影響します。
- ハッシュ競合の解決方法の選択については、オープンアドレス方式と連鎖表方式のそれぞれの長所と短所、適応シナリオを比較しました。ほとんどの場合、連鎖表法の方が普遍的です。また、連鎖表法の連鎖表を赤黒木のような他の動的ルックアップ・データ構造に変換することで、ハッシュ表の時間複雑度がO(n)に劣化するのを回避し、ハッシュ衝突攻撃に耐えることが可能です。しかし、オープンアドレッシング法は、データサイズが小さく、負荷率が低いハッシュテーブルに適しています。
HashMapもハッシュテーブルです。
- 初期サイズ HashMapのデフォルトの初期サイズは16です、もちろん、このデフォルト値を設定することができます、あなたが事前にどのように大きなおおよそのデータ量を知っている場合、あなたは大幅にHashMapのパフォーマンスを向上させる動的展開の数を減らすために、デフォルトの初期サイズを変更することができます。
- ローディング・ファクターと動的拡張 最大ローディング・ファクターはデフォルトで0.75で、HashMapの要素数が0.75*容量を超えると拡張が開始され、そのたびに元のサイズの2倍に拡張されます。
- ハッシュの競合解決方法 HashMap の底部では、チェーンテーブル方式で競合を解決します。負荷率やハッシュ関数が合理的に設計されていても、ZIPが長すぎる状況が発生することは避けられず、一旦ZIPが長すぎると、HashMapのパフォーマンスに深刻な影響を与えます。そこで、JDK1.8バージョンでは、HashMapのさらなる最適化を行うために、赤黒木の導入。そして、チェーンテーブルの長さが長すぎる場合、チェーンテーブルは赤黒木に変換されます。赤黒木は、高速な追加、削除、チェックという特徴を利用して、HashMapの性能を向上させることができます。赤黒木のノード数が8未満の場合、赤黒木は連鎖表に変換されます。データ量が少ない場合、赤黒木でバランスを保つため、連鎖表に比べて性能上の優位性は明らかではありません。
