- ハッシュマップ -
利点:O(1)時間の複雑さに到達できる超高速クエリ速度とデータ構造はハッシュマップです。動的可変長ストレージデータ(配列に対する)。
短所:ハッシュ値をさらに計算する必要があり、適切に処理されていない場合は、余分なスペースを占有します。
- ハッシュマップの使用方法 -
通常、ハッシュマップを次のように使用します
map <integer、string> maps = new hashmap <integer、string>(); maps.put(1、 "a"); maps.put(2、 "b");
上記のコードは、新しいハッシュマップを作成し、2つのデータを挿入します。基本的なデータ型は、KとVを行うためにここでは受け入れられません。
これを書くと、問題があります。
map <int、double> maps = new Hashmap <int、double>();
なぜこの方法を使用するのですか?ソースコードをご覧ください:
パブリッククラスのhashmap <k、v>は、abstractmap <k、v>を拡張します<k、v>、クローン可能、シリアル化可能
これは、HashMap実装クラスの定義です。
- ハッシュマップは動的に可変な長さのデータ構造です。
ハッシュマップを使用する場合、実行効率を改善するために、ハッシュマップの初期化容量を設定することがよくあります。
map <string、string> rm = new hashmap <string、string>(2)
または、Guavaのツールクラスマップを使用して、コレクションを簡単に作成し、適切なサイズで値を初期化します。
map <string、object> map = maps.newhashmapwithexpectedsize(7);
では、なぜこのように使用するのですか?ソースコンストラクターを見てみましょう。
パラメーターのないコンストラクター:
public hashmap(){this.loadfactor = default_load_factor; threshold =(int)(default_initial_capacity * default_load_factor);表= new entry [default_initial_capacity]; init(); } public hashmap(){
this.loadfactor = default_load_factor;
threshold =(int)(default_initial_capacity * default_load_factor);
表= new entry [default_initial_capacity];
init();
}
/** *指定された初期 *容量とデフォルトの負荷係数(0.75)を使用して、空の<tt> hashmap </tt>を構築します。 * * @param initialcapacity初期容量。 *初期容量が負の場合、@Throws IllegalargumentException。 */ public hashmap(int initialcapacity){this(initialcapacity、default_load_factor); }名詞の説明:
default_load_factor //デフォルトの読み込み係数、指定されていない場合は0.75。 default_initial_capacity //デフォルトの初期化容量、デフォルトは16しきい値//しきい値(yu)値は、負荷係数と初期化容量に基づいて計算されます。 <Span style = "color:rgb(54、46、43); font-family:" microsoft yahei ";">しきい値とは、ハッシュマップのサイズがしきい値より大きい場合、サイズ操作が実行されることを意味します。
したがって、パラメーターレスコンストラクターを呼び出すと、16の容量の配列が得られることがわかります。
質問は、初期容量で十分でない場合はどうなりますか?
配列は固定された長さです。固定長データを使用して、不確実な長さのデータを表す方法は?答えは、より長いものを見つけることですが、サイズすると効率が低下します。したがって、Hashmapに初期化時に信頼できる容量を与えることをお勧めします。
- ハッシュマッププットメソッド -
public v put(k key、v value){if(key == null)//キーが空の場合、ハッシュマップとハッシュテーブルの違いはputfornullkey(value); int hash = hash(key.hashcode()); //キーint i = indexfor(hash、table.length)のハッシュコードに基づいてハッシュ値をフレーム化します。 //(エントリ<k、v> e = table [i]; e!= null; e = e.next)のハッシュ値に基づいて配置する配列の添え付けをフレーム化する{//ループの全体が、kが存在する場合、vオブジェクトkを置き換えることを実装します。 if(e.hash == hash &&((k = e.key)== key || key.equals(k)){v oldvalue = e.value; e.value = value; E.RecordAccess(This); OldValueを返します。 }} modcount ++; //カウンターアデントリー(ハッシュ、キー、値、i); //配列に追加しますnull; }挿入されたデータが既存の容量を超えると、実行されます
Addentry(Hash、Key、Value、I);
void addentry(int hash、k key、v value、int bucketindex){entry <k、v> e = table [bucketindex];表[BucketIndex] =新しいエントリ<K、v>(ハッシュ、キー、値、e); if(size ++> = threshold)<span style = "color:#ff0000;"> <strong> resize(2 * table.length);}ここで、現在のサイズ++>しきい値が表示されると、現在のサイズが2回拡張され、サイズ変更(2*table.length)が実行されます。では、どのようにして拡大しますか?
void resize(int newcapacity){entry [] oldtable = table; int oldcapacity = oldtable.length; if(oldcapacity == maximing_capacity){threhhold = integer.max_value;戻る; } entry [] NewTable = new Entry [NewCapacity]; <Span style = "color:rgb(51、51、51); font-family:arial;"> new a new array、</span> <strong> <span style = "color:#ff0000;"> transfer(newtable); </span> </strong> //配列を新しい配列テーブル= newtable;しきい値=(int)(newcapacity * loadfactor); //容量を再計算}転送配列転送はどのように転送されますか?
void transfer(entry [] newtable){entry [] src = table; int newcapacity = newtable.length; for(int j = 0; j <src.length; j ++){entry <k、v> e = src [j]; if(e!= null){src [j] = null; {entry <k、v> next = e.next; int i = <strong> <span style = "color:#ff0000;"> indexfor(e.hash、newcapacity); //ハッシュ値容量に基づいてインデックスを再計算</span> </strong> e.next = newTable [i]; newtable [i] = e; e = next; } while(e!= null); }}}- ハッシュマップ拡張の追加の実行の数 -
したがって、1000の要素のハッシュマップを追加する場合、デフォルト値を使用する場合、計算する必要がある追加の計算数は何ですか?
16*0.75 = 12を超える場合、12回再計算する必要があります
16*2*0.75 = 24を超える場合、追加の24の計算が必要です。
...
16*n*0.75 = 768を超える場合、追加の768の計算が必要です。
そこで、拡張プロセスで12+24+48+…+768回計算しました
したがって、このようなプロジェクトの範囲を知っている場合は、初期サイズを手動で指定する必要があることを強くお勧めします。
map <integer、string> maps = new hashmap <integer、string>(1000);
概要:これが、使用中の初期容量を超えるとハッシュマップの実行効率が大幅に低下する理由です。
上記は、Javaソースコード分析に関するこの記事でのHashMapの使用に関するすべてです。すべての人に役立つことを願っています。興味のある友人は、このサイトの他の関連トピックを引き続き参照できます。欠点がある場合は、それを指摘するためにメッセージを残してください。このサイトへのご支援をありがとうございました!