HashMap(及びhash関数の真の巧妙さを理解する)
4711 ワード
/**
*@author annegg
*@date 2009-12-02
*/
Hashmapは非常によく使われている、幅広いデータタイプです.最近は関連の内容を研究して、復習しています.ネット上ではhashmapに関する文章が多いですが、自分で勉強しただけの総括です.
1、hashmapのデータ構造
hashmapが何かを知るには、まずそのデータ構造を明らかにします.javaプログラミング言語の中で、一番基本的な構造は二つです.一つは配列です.もう一つはアナログポインタです.すべてのデータ構造はこの二つの基本構造で構成できます.hashmapも例外ではありません.Hashmapは実際には配列とチェーンの結合体です.
図からはhashmapが行列構造であり、hashmapが新たに作られると、行列が初期化されます.javaコードを見てみます.
hashmapのput元素に行く時、まずkeyのhashによってこの元素の配列の中の位置に値します.この要素を対応する位置に置くことができます.この元素が位置する位置に他の要素が既に保存されている場合、同じ席の要素はチェーンで保存されます.新しく加入したのはチェーンの先に置いて、最初に参加したのはチェーンの最後に置きます.hashmapから要素をgetする時、まずkeyのhashcodeを計算して、配列中の対応する位置のいずれかを見つけます.元素、そしてkeyのequals方法を通じて、対応する位置のチェーンに必要な元素を見つけます.ここから想像できます.各位置のチェーンが元素一つしかないなら、hashmapのget効率は一番高いです.でも、理想はいつもすばらしいです.現実はいつも困難があります.私たちが克服したいです.ハハ.
2、hashアルゴリズム
hashmapである要素を見つけるには、keyのhash値に基づいて対応する配列の位置を求める必要があります.この位置をどう計算するかはhashアルゴリズムです.hashmapという前に述べたデータ構造は配列とチェーンの結合です.もちろん、このhashmapの中の要素位置はできるだけ均一に分布してほしいです.各位置の要素数をできるだけ均等にしてください.量は一つしかないです.hashアルゴリズムでこの位置を求めたら、すぐに対応する位置の要素が私たちの必要なものであることが分かります.
まず最初に考えたのは、hashcodeを配列長に対して型を取るということです.そうすると、元素の分布は相対的に均質です.しかし、「型」演算の消費はまだ大きいです.もっと速くて、もっと小さい方法を探してもいいですか?javaでは、
下の図を見ると、左の2つのグループは配列長16(2の4乗)で、右の2つのグループは配列長15である.2つのグループのhashcodeは8と9であるが、それらと1110が「和」であることは明らかである.同じ結果が発生した場合、つまり配列中の同じ位置に位置して衝突が発生し、8と9は同じチェーンに配置されます.照会する時はこのチェーンを遍歴して、8または9を得る必要があります.そうすると、クエリの効率が低下します.また、配列長さが15の時に、hashodの値は14(1110)と「和」します.最後のビットは常に0であり、0001、0011、0101、1001、1011、0111、1101という位置は、要素を永遠に保存することができなくなりました.空間の浪費がかなり大きく、さらに悪いのは、配列が使用できる位置は配列の長さよりもずっと小さくなりました.
したがって、配列長が2のn乗の場合、異なるkeyはindexと同じ確率で計算されます.データは配列上の分布が比較的に均一です.つまり、衝突の確率が小さいです.相対的に、照会するときは、ある位置のチェーンを遍歴しなくても、より高いです.これは本当の理由です.ソースコードを見ても多くの人がいます.原因は分かりません
÷ここに来て、hashmapのデフォルトの配列の大きさを見てみます.ソースコードを見れば、16はなぜですか?15ではなく、20でもないです.上のanneggの説明を見たら分かりますよね.16は2の整数の累乗の原因です.小さいデータ量の場合、16は15と20よりkey間の衝突を減らすことができます.検索の効率を上げる.
したがって、大容量のデータを格納する際には、hashmapのsizeを2の整数番目の累乗を予め指定したほうがいいです.指定しなくても、指定された値の大きさに最も近い2乗で初期化されます.コードは以下の通りです.
hashmapの中の要素が多くなると、衝突の確率も高くなります.したがって、クエリの効率を向上させるためには、hashmapの配列を拡張し、配列拡張という操作はアラーListにも現れますので、これは汎用的な操作です.多くの人がその性能に疑問を持っていますが、私たちの「均等割り」を考えてみてください.原理としては、hashmap配列の拡充後、最も消費された性能の点が現れた.元の配列のデータは新しい配列の中の位置を再計算して入れなければならない.これはresizeである.
hashmapはいつ拡張されますか?hashmapの要素個数が配列サイズ*loadFactorを超えると行列拡張が行われます.loadFactorのデフォルト値は0.75です.つまり、デフォルトでは配列サイズは16です.hashmapの要素個数が16*0.75=12を超えると、配列の大きさを2*16=32倍に拡大します.各要素の配列中の位置を計算します.これは非常に性能を消耗する操作です.だから、hashmapの要素の個数を予知したら、事前設定要素の個数は効果的にhashmapの性能を高めることができます.例えば、私達は1000個の元素をhashmapに置くと、hashmapのsizeを1024に設定するのはいい選択です.既に述べたように、hashmapは1000でも自動的に1024に設定されます.
4、keyのhashcodeとequals方法の書き換え
第一部分hashmapのデータ構造において、anneggはget方法のプロセスを書きました.まず、keyのhashcodeを計算して、配列中の対応する位置のある要素を見つけて、keyのequals方法によって、対応する位置のチェーンに必要な要素を見つけます.
hashmapのkeyは、Userのような任意のタイプのオブジェクトであってもいいです.同じ属性を持つuserのhashcodeが同じであることを保証するために、hashcodeを書き換える方法が必要です.例えば、hashcodeの値の計算をUserオブジェクトのidに関連付けると、userが同じidを持っている限り、彼らのhashcodeも一致します.ap配列中の位置です.この位置に複数の要素がある場合は、keyのequals方法で対応する位置のチェーンに必要な要素を見つけます.だから、hashcodeメソッドを書き換えただけでは足りません.equals方法も書き換えが必要です.もちろん、正常な思考ロジックで、equals方法は一般的に実際の業務内容によって定義されます.例えば、userオブジェクトによって.のIDを使って、二つのuserが同じかどうかを判断します.
equals方法を書き換える時、以下の3点を満たす必要があります.
(1)自発性:つまりa.equals(a)はtrueでなければなりません.
(2)対称性:つまりa.equals(b)＝trueであれば、b.equals(a)もtrueでなければなりません.
(3)伝達性:つまりa.equals(b)=trueであり、b.equals(c)=trueであれば、a.equals(c)もtrueでなければなりません.
keyオブジェクトのequalsとhashcodeを書き換えることにより、任意の業務対象をmapのkeyとすることができます.
まとめ: 本論文では主にHashMapの構造とhashmapにおけるhash関数の実現とその実現の特性を述べながら、hashmapにおけるresizeの性能消費の根本的な原因と普通のドメインモデルオブジェクトをkeyの基本的な要求として説明した.特にhash関数の現実は、HashMap全体の真髄とも言える.このhash関数を本当に理解しなければならない.ということで、HashMapに対して一定の理解ができました.
*@author annegg
*@date 2009-12-02
*/
Hashmapは非常によく使われている、幅広いデータタイプです.最近は関連の内容を研究して、復習しています.ネット上ではhashmapに関する文章が多いですが、自分で勉強しただけの総括です.
1、hashmapのデータ構造
hashmapが何かを知るには、まずそのデータ構造を明らかにします.javaプログラミング言語の中で、一番基本的な構造は二つです.一つは配列です.もう一つはアナログポインタです.すべてのデータ構造はこの二つの基本構造で構成できます.hashmapも例外ではありません.Hashmapは実際には配列とチェーンの結合体です.
図からはhashmapが行列構造であり、hashmapが新たに作られると、行列が初期化されます.javaコードを見てみます.
/**
* The table, resized as necessary. Length MUST Always be a power of two.
* FIXME ，
*/
transient Entry[] table;static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
final int hash;
Entry<K,V> next;
..........
}
hashmapのput元素に行く時、まずkeyのhashによってこの元素の配列の中の位置に値します.この要素を対応する位置に置くことができます.この元素が位置する位置に他の要素が既に保存されている場合、同じ席の要素はチェーンで保存されます.新しく加入したのはチェーンの先に置いて、最初に参加したのはチェーンの最後に置きます.hashmapから要素をgetする時、まずkeyのhashcodeを計算して、配列中の対応する位置のいずれかを見つけます.元素、そしてkeyのequals方法を通じて、対応する位置のチェーンに必要な元素を見つけます.ここから想像できます.各位置のチェーンが元素一つしかないなら、hashmapのget効率は一番高いです.でも、理想はいつもすばらしいです.現実はいつも困難があります.私たちが克服したいです.ハハ.
2、hashアルゴリズム
hashmapである要素を見つけるには、keyのhash値に基づいて対応する配列の位置を求める必要があります.この位置をどう計算するかはhashアルゴリズムです.hashmapという前に述べたデータ構造は配列とチェーンの結合です.もちろん、このhashmapの中の要素位置はできるだけ均一に分布してほしいです.各位置の要素数をできるだけ均等にしてください.量は一つしかないです.hashアルゴリズムでこの位置を求めたら、すぐに対応する位置の要素が私たちの必要なものであることが分かります.
まず最初に考えたのは、hashcodeを配列長に対して型を取るということです.そうすると、元素の分布は相対的に均質です.しかし、「型」演算の消費はまだ大きいです.もっと速くて、もっと小さい方法を探してもいいですか?javaでは、
static int indexFor(int h, int length) {
return h & (length-1);
}下の図を見ると、左の2つのグループは配列長16(2の4乗)で、右の2つのグループは配列長15である.2つのグループのhashcodeは8と9であるが、それらと1110が「和」であることは明らかである.同じ結果が発生した場合、つまり配列中の同じ位置に位置して衝突が発生し、8と9は同じチェーンに配置されます.照会する時はこのチェーンを遍歴して、8または9を得る必要があります.そうすると、クエリの効率が低下します.また、配列長さが15の時に、hashodの値は14(1110)と「和」します.最後のビットは常に0であり、0001、0011、0101、1001、1011、0111、1101という位置は、要素を永遠に保存することができなくなりました.空間の浪費がかなり大きく、さらに悪いのは、配列が使用できる位置は配列の長さよりもずっと小さくなりました.
したがって、配列長が2のn乗の場合、異なるkeyはindexと同じ確率で計算されます.データは配列上の分布が比較的に均一です.つまり、衝突の確率が小さいです.相対的に、照会するときは、ある位置のチェーンを遍歴しなくても、より高いです.これは本当の理由です.ソースコードを見ても多くの人がいます.原因は分かりません
÷ここに来て、hashmapのデフォルトの配列の大きさを見てみます.ソースコードを見れば、16はなぜですか?15ではなく、20でもないです.上のanneggの説明を見たら分かりますよね.16は2の整数の累乗の原因です.小さいデータ量の場合、16は15と20よりkey間の衝突を減らすことができます.検索の効率を上げる.
したがって、大容量のデータを格納する際には、hashmapのsizeを2の整数番目の累乗を予め指定したほうがいいです.指定しなくても、指定された値の大きさに最も近い2乗で初期化されます.コードは以下の通りです.
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;hashmapの中の要素が多くなると、衝突の確率も高くなります.したがって、クエリの効率を向上させるためには、hashmapの配列を拡張し、配列拡張という操作はアラーListにも現れますので、これは汎用的な操作です.多くの人がその性能に疑問を持っていますが、私たちの「均等割り」を考えてみてください.原理としては、hashmap配列の拡充後、最も消費された性能の点が現れた.元の配列のデータは新しい配列の中の位置を再計算して入れなければならない.これはresizeである.
hashmapはいつ拡張されますか?hashmapの要素個数が配列サイズ*loadFactorを超えると行列拡張が行われます.loadFactorのデフォルト値は0.75です.つまり、デフォルトでは配列サイズは16です.hashmapの要素個数が16*0.75=12を超えると、配列の大きさを2*16=32倍に拡大します.各要素の配列中の位置を計算します.これは非常に性能を消耗する操作です.だから、hashmapの要素の個数を予知したら、事前設定要素の個数は効果的にhashmapの性能を高めることができます.例えば、私達は1000個の元素をhashmapに置くと、hashmapのsizeを1024に設定するのはいい選択です.既に述べたように、hashmapは1000でも自動的に1024に設定されます.
4、keyのhashcodeとequals方法の書き換え
第一部分hashmapのデータ構造において、anneggはget方法のプロセスを書きました.まず、keyのhashcodeを計算して、配列中の対応する位置のある要素を見つけて、keyのequals方法によって、対応する位置のチェーンに必要な要素を見つけます.
hashmapのkeyは、Userのような任意のタイプのオブジェクトであってもいいです.同じ属性を持つuserのhashcodeが同じであることを保証するために、hashcodeを書き換える方法が必要です.例えば、hashcodeの値の計算をUserオブジェクトのidに関連付けると、userが同じidを持っている限り、彼らのhashcodeも一致します.ap配列中の位置です.この位置に複数の要素がある場合は、keyのequals方法で対応する位置のチェーンに必要な要素を見つけます.だから、hashcodeメソッドを書き換えただけでは足りません.equals方法も書き換えが必要です.もちろん、正常な思考ロジックで、equals方法は一般的に実際の業務内容によって定義されます.例えば、userオブジェクトによって.のIDを使って、二つのuserが同じかどうかを判断します.
equals方法を書き換える時、以下の3点を満たす必要があります.
(1)自発性:つまりa.equals(a)はtrueでなければなりません.
(2)対称性:つまりa.equals(b)＝trueであれば、b.equals(a)もtrueでなければなりません.
(3)伝達性:つまりa.equals(b)=trueであり、b.equals(c)=trueであれば、a.equals(c)もtrueでなければなりません.
keyオブジェクトのequalsとhashcodeを書き換えることにより、任意の業務対象をmapのkeyとすることができます.
まとめ: 本論文では主にHashMapの構造とhashmapにおけるhash関数の実現とその実現の特性を述べながら、hashmapにおけるresizeの性能消費の根本的な原因と普通のドメインモデルオブジェクトをkeyの基本的な要求として説明した.特にhash関数の現実は、HashMap全体の真髄とも言える.このhash関数を本当に理解しなければならない.ということで、HashMapに対して一定の理解ができました.