HashMapを深く理解する

5250 ワード
/**
*@author annegg
*@date 2009-12-02
*/
「size=medium」hashmapは非常によく使われている、幅広いデータタイプです.最近は関連の内容を研究して、復習しています.ネット上ではhashmapに関する文章が多いですが、自分で勉強しただけの総括です.
1、hashmapのデータ構造
hashmapが何かを知るには、まずそのデータ構造を明らかにします.javaプログラミング言語の中で、一番基本的な構造は二つです.一つは配列です.もう一つはアナログポインタです.すべてのデータ構造はこの二つの基本構造で構成できます.hashmapも例外ではありません.Hashmapは実際には配列とチェーンの結合体です.(データ構造では、一般的に「鎖表ハッシュ」と呼ばれています.)下の図を見てください.
[img]http://dl.iteye.com/upload/attachment/175485/64a63042-280e-3651-ba05-abeaa96fea07.jpg[img]
[size=medium]は図から見られます.hashmapは配列構造です.hashmapを新規作成すると、行列が初期化されます.javaコードを見てみます.[/size]
/**
     * The table, resized as necessary. Length MUST Always be a power of two.
     *  FIXME          ，         
     */
    transient Entry[] table;

static class Entry implements Map.Entry {
        final K key;
        V value;
        final int hash;
        Entry next;
..........
}
[size=medium]
上のEntryは配列中の要素で、次の要素を指す参照を持っています.
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);
    }
[size=medium]まずkeyはhashcodeの値を計算して、配列の長さ-1と「和」演算をします.簡単に見えますが、実は玄機があります.配列の長さは2の4乗です.hashcodeは2の4乗-1と「和」をします.演算です.多くの人がこの疑問を持っています.なぜhashmapの配列初期化サイズは2の二乗の大きさで、hashmapの効率が一番高いのか、2の4乗の例を挙げて、行列の大きさが2のべきなときにhashmapが訪問する性能が一番高いのかを説明します.
下の図を見ると、左の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のこれらの位置は、要素を保存することができなくなりました.空間の浪費が大きく、さらに悪いことに、配列が使用できる位置は配列の長さよりもずっと小さくなりました.これは、衝突の確率をさらに増加させ、クエリの効率を遅くすることを意味します.
[img]http://dl.iteye.com/upload/attachment/175477/f7fdb997-2dbe-3d79-9a36-5720691f40d3.jpg[img]
[size=medium]
したがって、配列長が2のn乗の場合、異なるkeyはindexと同じ確率で計算されます.データは配列上で分布が比較的に均一で、つまり衝突の確率が小さいです.相対的に、照会するときは、ある位置のチェーンを遍歴する必要がなく、検索効率も高いです.
ここでは、hashmapのデフォルトの配列の大きさを振り返ってみます.ソースコードを見ると、16はなぜ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;
[size=medium]
3、hashmapのresize
hashmapの中の要素が多くなると、衝突の確率も高くなります.したがって、クエリの効率を向上させるためには、hashmapの配列を拡張し、配列拡張という操作はアラーListにも現れますので、これは汎用的な操作です.多くの人がその性能に疑問を持っていますが、私たちの「均等割り」を考えてみてください.原理としては、hashmap配列の拡充後、最も消費された性能の点が現れた.元の配列のデータは新しい配列の中の位置を再計算して入れなければならない.これはresizeである.
hashmapはいつ拡張されますか?hashmapの要素個数が配列サイズ*loadFactorを超えると行列拡張が行われます.loadFactorのデフォルト値は0.75です.つまり、デフォルトでは配列サイズは16です.hashmapの要素個数が16*0.75=12を超えると、配列の大きさを2*16=32倍に拡大します.各要素の配列中の位置を計算します.これは非常に性能を消耗する操作です.だから、hashmap中の要素の個数を予知したら、事前設定要素の個数はhashmapの性能を効果的に高めることができます.例えば、私達は1000の要素new HashMap(1000)がありますが、理論的にはnew HashMap(1024)があります.もっと適していますが、上のanneggでは、たとえ1000でもhashmapは自動的に1024に設定されると言っていましたが、new HashMap(1024)はもっと適していません.0.75*1000<1000,つまり0.75*size>1000をするためには、new HashMap(2048)が一番適しています.
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とすることができます.
[size=medium]
まとめ:
本論文では主にHashMapの構造とhashmapにおけるhash関数の実現とその実現の特性を述べながら、hashmapにおけるresizeの性能消費の根本的な原因と普通のドメインモデルオブジェクトをkeyの基本的な要求として説明した.特にhash関数の現実は、HashMap全体の真髄とも言える.このhash関数を本当に理解しなければならない.ということで、HashMapに対して一定の理解ができました.
これはhashmapの第一編です.hashmapのデータ構造とhashの計算方法について説明しました.続いてanneguは第二編も書きます.主にLinked hashMapとLRUHashMapについて話します.まず予告します.ほほほ～
java.util.concurrentバッグのソースコードは読みます.