序文:Java 8の後に追加された新しいものがたくさんあります。オンラインで関連する情報を見つけました。ハッシュマップが乱用された後、私は自分自身に関連する知識を整理することにしました。写真といくつかのコンテンツを参照するこの記事:http://www.vevb.com/article/80446.htm
ハッシュマップの保管構造を図に示します。バケツに8つ以上のノードがある場合、保管構造は赤と黒の木であり、8未満は一方向リンクリストです。
1:ハッシュマップの一部のプロパティ
パブリッククラスハッシュマップ<k、v>拡張抽象マップ<k、v>実装マップ<k、v>、クローン可能、シリアル化可能{private static final long serialversionuid = 362498820763181265l; 30; //デフォルトの塗りつぶし要因(前のバージョンは負荷係数とも呼ばれていました)静的最終float default_load_factor = 0.75f; //これはしきい値です。バケットのリンクリストの数がこの値よりも大きい場合、赤と黒の木に変換されます。 PUTメソッドのコードは、静的なfinal int treeify_threshold = 8; //しきい値でもあります。バケットのリンクリストの数がこの値よりも少ない場合、ツリーはリンクリストに変換されますstatic final int untreeify_threshold = 6; //ソースコードのコメントで、ツリーの最小容量は少なくとも4 x treeify_threshold = 32。要素の保存され、常に2つの過渡ノード<k、v> []テーブル;一時的なセット<map.entry <k、v >> enterset; //保存されている要素の数は、これは配列の長さに等しくないことに注意してください。一時的なINTサイズ; //マップ構造の各拡張と変更のカウンターは一時的なint modcount;2:ハッシュマップ構築方法
//初期容量を指定し、充填因子パブリックハッシュマップ(int initial-capacity、float loadactor){//指定された初期容量は非陰性です(初期容量<0)新しい違法容量(違法初期容量: +初期容量); Maximion_capacity; //充填比は正です(loadFactor <= 0 || float.isnan(loadfactor))新しいIllegalargumentexception(違法荷重係数: +loadfactor); this.loadfactor = loadfactor; //容量を指定した後、Tablesize forメソッドは臨界値を計算します。データを配置するときに値を超えると、拡大します。値は間違いなく2.//指定された初期容量は保存されておらず、臨界値を生成するためにのみ使用されます。thredhold = tablesizefor(initialcapacity);} // n | = n >>> 1; n | = n >>> 2; n | = n >>> 4; n | = n >>> 8; n | = n >>> 16; //三角演算子のネストされた戻り(n <0)? 1:(n> = maximion_capacity)? Maximinal_capacity:n + 1;} // constructor 2public hashmap(int initialCapacity){this(initialCapacity、default_load_factor);} // constructor 3public hashmap(){this.loadfactor = default_load_factor; //他のすべてのフィールドがデフォルト}}3:取得して配置するときに配列内の要素の位置を決定する
static final int hash(object key){int h; return(key == null)? 0:(h = key.hashcode()) ^(h >>> 16);}場所を決定します
最初のステップ:最初のことは、キーのハッシュコードを計算することです。これはINTタイプ番号です。次のH >>> 16ソースコードのコメントは次のように述べています。ハッシュ衝突を避けるために、高い位置は低位置に広がります。これは、速度やパフォーマンスなどのさまざまな要因を考慮した後に行われます。
ステップ2:Hはハッシュコードで、長さは上記のノード[]配列の長さで、同じ操作H&(長さ1)を実行します。長さは2 -1の倍数であるため、そのバイナリコードは1であり、操作後に均一性を確保するために、他の数値が1の結果が0または1になる場合があります。つまり、ハッシュメソッドにより、結果の均一性が保証されます。これは非常に重要であり、ハッシュマップのパフォーマンスに大きく影響します。比較のために次の写真を参照してください。
図3.1は非対称ハッシュの結果です
図3.2は、バランスの取れたハッシュ結果です
これら2つのグラフには多くのデータはありません。リンクされたリストが8より長い場合、赤と黒の木に変換されます。当時はもっと明白だろう。 JDK8は常に以前にリンクされたリストでした。リンクされたリストクエリの複雑さはo(n)であり、独自の特性による赤と黒の木の複雑さはo(log(n))です。ハッシュの結果が不均一な場合、操作の複雑さに大きく影響します。 a <a href = "http://blog.chinaunix.net/uid-26575352-ID-3061918.html">赤とブラックツリーの基本知識ブログ</a>オンラインの別の例があります。
Public Class MutableKeyTest {public static void main(string args []){class mykey {integer i; public void seti(integer i){this.i = i;} public mykey(this.i = i;}@overridepublic int hashcode(){/ return i;メソッドは@OverridePublic boolean Equals(オブジェクトobj){if(obj instanceof mykey){return i.equals((((mykey))obj).i) map <mykey、string> map = new hashmap <>(25000,1); date begin = new date(); for(int i = 0; i <20000; i ++){map.put(new mykey(i)、 "test" + i);} date end = new date(); system.out.println( "time(" time(ms) " +(end.gettime();4:メソッドを取得します
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; // hash&(length -1)赤と黒の木のルート位置またはリンクリストのヘッダーを取得しますif((tab = table)!= null &&(n = tab.length)> 0 &&(first = tab]) key.equals(k)))first; if((e = first.next)!= null){//ツリーの場合、赤と黒の木を通過する複雑さはo(log(n))です。 == hash &&((k = e.key)== key ||(key!= null && key.equals(k))))return e;}5:メソッドを置くと、h&(長さ1)に従ってバケツを見つけてから、赤と黒の木かリンクされたリストと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;ノード<k、v> p; int n、i; //タブが空の場合、または長さが0の場合、メモリに割り当てられたresize()if((tab = table)== null ||(n = tab.length)== 0)n =(tab = resize())。空の場合、putif((p = tab [i =(n -1)&hash])== null)tab [i] = newnode(hash、key、value、null); else {node <k、v> e; k k; //最初のノードのハッシュ値は同じであり、キー値は挿入キーと同じです(p.hash == hash &&((k = p.key)== key ||(key!= null && key.equals(k)))e = p; Putvalの後、ツリー全体を横断する必要があります。必要に応じて、値を変更して、赤と黒の木の特性e =((treeNode <k、v>)pの特性(this、tab、hash、key、value); else {//(int bincount = 0;; ++ bincount){if(e = p.next)= nuld {/ eはnuldに達します。テーブルの新しいノードP.Next = newNode(ハッシュ、キー、値、null); //新しいノードを追加した後、ノードの数がしきい値に達した場合、リンクされたリストを赤と黒の木に変換する場合(bincount> = treeify_threshold -1) Hash &&((k = e.key)== key ||(key!= null && key.equals(k))))))))) value; autgleDeaccess(e); return oldvalue;} ++ modcount; if(++ size> threshold)resize(); foredodeinsertion(evict); return null;}6:サイズメソッド
final node <k、v> [] resize(){node <k、v> [] oldtab = table; int oldcap =(oldtab == null)? 0:oldtab.length; int oldthr = shreshold; int newcap、newtr = 0; if(oldcap> = maximing_capacity){threshold = integer.max_value;} //この文はより重要です。 > = default_initial_capacity)newthr = oldthr << 1; // double threshold} else if(oldthth> 0)//初期容量がしきい値に配置された場合、whrotholdnewcap = oldtr; loadfactor; newthr =(newCap <Maximing_capacity && ft <(float)maximum_capacity?(int)ft:integer.max_value);} threshold = newthr;@suppresswarnings({"rawTypes"、 "Unchecked"}) node [newcap]; table = newtab; if(oldtab!= null){for(int j = 0; j <oldcap; ++ j){node <k、v> e; if((e = oldtab [j]) treeNodeのinstance)((treenode <k、v>)e).split(this、newtab、j、oldcap); else {// preserve ordernode <k、v> lohead = null、lotail = null; node <k、v> hihead = null、hitail = null; node <k、v> do {next = e. {if(lotail == null)lohead = e; elselotail.next = e; lotail = e;} else {if(hitail == null)hihead = e; elsehitail.next = e; hitail = e;}} != null){hitail.next = null; newtab [j + oldcap] = hihead;}}}}} newtab;}}}}}上記は、編集者が紹介したJava8ハッシュマップの実装原則分析に関する関連する知識です。それがあなたに役立つことを願っています!