1篇の文章は徹底的にHashMapのHashMapソースコードの解析を読みます(上)
9952 ワード
，HashMap “ ”， HashMap 、 。
， HashMap ， ， 、 HashMap （ ）。 ， ， HashMap ， HashMap 。 ~
この記事は、HashMapソース分析(JDK 8、分かりやすい)HashMap面接「スター」問題のまとめ、スター問題の答えの順に整理されます.
以下はJDK 8におけるHashMapのソース分析であり、以下のソース分析である.
(1)HashMapのメンバー属性ソース分析
public class HashMap
extends AbstractMap
implements Map,
Cloneable, Serializable {
private static final long serialVersionUID
= 362498820763181265L;
//HashMap 16，HashMap
// ，
//
static final int DEFAULT_INITIAL_CAPACITY
= 1 << 4;
//HashMap
static final int MAXIMUM_CAPACITY
= 1 << 30;
//
static final float DEFAULT_LOAD_FACTOR
= 0.75f;
// >=8 ，
// , >=64,
static final int TREEIFY_THRESHOLD = 8;
// <=6 ，
//
static final int UNTREEIFY_THRESHOLD = 6;
// ： Node >=64 ，
// >=8，
//
static final int MIN_TREEIFY_CAPACITY = 64;
}
DEFAULT_LOAD_FACTOR:HashMapの負荷係数は、HashMapの性能に影響するパラメータの1つであり、時間と空間のバランスであり、後にHashMapの要素がNode配列に格納されているのが見えます.この配列の大きさはここでは「バケツ」の大きさと呼ばれます.もう1つのパラメータsizeは、HashMapにどれだけの要素をputしたかを指します.size>バケツの数*DEFAULT_LOAD_FACTORの場合、このときHashMapは拡容操作を行います.つまりバケツがいっぱいにならないことです.DEFAULT_LOAD_FACTORはバケツの使用率を測定します.
DEFAULT_LOAD_FACTORが小さい(バケツの利用率が小さい)場合、無駄なスペースが多く(バケツの数DEFAULT_LOAD_FACTOR個のエレメントしか記憶できないので、それを超えると拡張する)、この場合HashMapにputエレメントを入れる際に衝突する確率も小さく、衝突とは、複数のエレメントが同じバケツにputされたこと、衝突が小さいことを意味する(1つのバケツに1つの要素しかないと考えられる)put,getなどのHashMapの操作コストは低く,O(1)と考えられる.DEFAULT_LOAD_FACTORが大きい場合、バケツの利用率が大きい場合(衝突する要素はチェーンテーブルや赤黒い木で接続されているので注意が大きい)、この場合空間利用率が高く、これは1つのバケツに多くの要素が格納されていることを意味し、この場合HashMapのput、getなどの操作コストが比較的大きいことを意味する.各putまたはget操作はチェーンテーブルまたは赤黒ツリーに対する操作となり、コストはO(1)より大きいに違いないので、DEFAULT_LOAD_FACTORは空間と時間の平衡点である.DEFAULT_LOAD_FACTORは小さいので、必要な空間は大きいが、putとgetの代価は小さい.DEFAULT_LOAD_FACTORが大きい場合、必要なスペースは小さいが、putとgetの代価は大きい).拡張操作はバケツの数*2、すなわちNode配列の大きさを拡張前の2倍に調整することであり、なぜ2倍なのか、拡張関数を分析する際に説明するが、これはtrickであり、詳細は後述する.Node配列の各バケツにはNodeチェーンテーブルが格納されており、チェーンテーブルの長さ>=8のとき、Node配列の大きさ>=64のとき、チェーンテーブルは赤黒ツリー構造になります(赤黒ツリーの削除の複雑さはlognであり、チェーンテーブルはnであり、赤黒ツリー構造はチェーンテーブルよりもコストが小さいため).
(2)HashMap内部類——Nodeソース分析
//Node HashMap
static class Node
implements Map.Entry {
final int hash;
final K key;// map key
V value;// map value
Node next;//
//
Node(int hash, K key, V value
,Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
HashMapの内部クラスNode:HashMapのすべてのデータはNode配列に保存されていますが、このNodeはいったい何なのでしょうか.Nodeのhash属性:keyのhashcodeの値を保存する:keyのhashcode^(keyのhashcode>>16).主にhash衝突を減らすためにmapにput(k,v)を押すと、このk,vキー値ペアがノードにカプセル化されます.では、このノードはノード配列のどの位置に置かれますか.index=hash&(n-1)、nはノード配列の長さです.では、なぜhashをこのように計算すると衝突を減らすことができるのでしょうか.hashCode&(n-1)を直接使用してindexを計算する場合、hashCodeの高位ランダム特性はまったく使用されません.nはhashcodeの値に対して小さいため、indexを計算するときは16ビットしか使用できません.これに基づいて、hashcodeの高い16ビットの値を、hashCodeの低い16ビットに異種または混合することによって、hashCodeの低い16ビットのランダム性を増強する.
(3)HashMap hash関数解析
static final int hash(Object key) {
int h;
return (key == null) ? 0 :
(h = key.hashCode()) ^ (h >>> 16);
}
HashMapはkeyがnull、nullのhashが0(HashMapはkeyがnullのキー値対であることを意味する)を許容し、null以外のkeyのhash高16ビットと低16ビットは、keyのhashCode高16ビットとhashCodeの高16ビット異またはhashCodeの低16ビットからなる.主にhashのランダム性を増強しhash&(n−1)のランダム性を低減し、すなわちhash衝突を低減し、HashMapの性能を向上させるためである.したがって、HashMapのkeyであるhashCode関数の実装はHashMapの性能に大きな影響を及ぼし、極端な場合、すべてのkeyのhashCodeは同じであり、これはHashMapの性能が悪い!
(4)HashMap tableSizeFor関数ソースコード解析
static final int tableSizeFor(int cap) {
// ：n 1( )，
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1
: (n >= MAXIMUM_CAPACITY)
? MAXIMUM_CAPACITY : n + 1;
}
new HashMapの場合、サイズパラメータを入力すると、これはHashMapが入力したHashMap容量をtableSizeFor関数に転送します.この関数の主な機能は、cap以上2の整数乗数の中で最も小さい数を返すことです.すなわち、capに最も近い(>=cap)を返します.2の整数乗の数です.具体的な論理は以下の通りである:1つの数は2の整数次べき乗であり、この数が1を減らすバイナリはマスクの列であり、すなわちバイナリはあるビットから連続する1の列である.したがって、対応するマスクがペアであれば、マスク+1は必ず2の整数次べき乗であり、これもn=cap−1の理由である.例えば、n=000100000_00000000_00000000
n |= n >>> 1;//実行後//n=00011000_00000000_00000000
n |= n >>> 2;//実行後//n=00011110_00000000_00000000
n |= n >>> 4;//実行後//n=00011111_11100000_00000000
n |= n >>> 8;//実行後//n=00011111_11111111_11100000
n |= n >>> 16;//実行後//n=0001111_11111111_11111111
n+1,(n+1)>=cap,2の整数次べき乗を返し,capとの差が最も小さい数である.最後のn+1は必ず2の整数次べき乗であり、必ず>=capである.全体的な考え方は,nのバイナリのk番目が1であれば,上の4つの‘|’演算を経て[0,k]ビットはいずれも1になる,すなわち,一連の連続バイナリ‘1’(マスク),最後にn+1は必ず2の整数次べき乗(オーバーフローしない場合)である.
/ map put (k,v) Node ，
// Node table
transient Node[] table;
// keySet values
transient Set> entrySet;
// map
transient int size;
//failFast ， ArrayList
// LinkedList
transient int modCount;
(6)threshold属性分析
int threshold;//
// ， DEFAULT_LOAD_FACTOR
// ， 0.75
final float loadFactor;
thresholdも重要な属性です.HashMapを作成するとき、この変数の値は、初期容量です.(2の整数次べき乗)後のthresholdの値は、現在のNodetable配列の長さ*loadfactorであるHashMap拡張の閾値である.例えば、HashMapコンストラクタに渡される容量サイズが9の場合、thresholdの初期値は16であり、HashMapの最初の要素に向かうと、内部に長さ16のNode配列が作成され、thresholdの値は160.7に更新される5=12.具体的には、HashMap put要素に向かっているとき、ある要素をputした後、Node配列の要素の個数が13である場合、このとき、拡張(配列内の要素数>threshold、すなわち13>threshold=12)がトリガーされ、具体的な拡張操作は後で詳細に分析され、単純に理解すると、拡張操作はノード配列長2を、元のすべての要素を新しいノード配列に移行する.
(7)HashMapコンストラクタソース分析
// ： map ， loadfactor
public HashMap(int initialCapacity
, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException
("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0
|| Float.isNaN(loadFactor))
throw new IllegalArgumentException(
"Illegal load factor: " + loadFactor);
// loadfactor
this.loadFactor = loadFactor;
/* ， tableSizeFor ，
：>=initialCapacity、
2 ，
。
*/
this.threshold =
tableSizeFor(initialCapacity);
}
/*
HashMap ，
loadfactor
:0.75
*/
public HashMap(int initialCapacity) {
this(initialCapacity
, DEFAULT_LOAD_FACTOR);
}
// ， loadfactor：0.75,
// 16
public HashMap() {
this.loadFactor
= DEFAULT_LOAD_FACTOR;
}
//
コンストラクタから、HashMapは「怠け者ロード」であり、コンストラクタの値には関連する保存された値が保持され、table配列は初期化されていません.mapのputの最初の要素に向かうと、mapは初期化されます.(8)HashMapのget関数ソースコード解析
// , value
public V get(Object key) {
Node e;
//hash
return (e = getNode(hash(key), key))
== null
? null : e.value;
}
get関数は実質的に、指定したkeyのノードをチェーンテーブルまたは赤黒ツリーで遍歴するプロセスである.また、HashMapのget関数の戻り値は、1つのkeyがmapに含まれているか否かを判断することができず、get戻りnullがそのkeyを含まない可能性があることに注意する必要がある.このkeyに対応するvalueがnullである可能性もあります.HashMapではkeyがnull、valueがnullを許可します.(9)getNode関数ソース分析
// getNode
final Node getNode(int hash
, Object key) {
Node[] tab;
Node first, e;
int n; K k;
if ((tab = table) != null
&& (n = tab.length) > 0
&&(first=tab[(n-1)&hash])
!= null) {
if (first.hash == hash&&
((k = first.key) == key
|| (key != null
&& key.equals(k))))
// ， ，
//
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
// /
return ((TreeNode)first)
.getTreeNode(hash, key);
do {
// ( )
if (e.hash == hash &&
((k = e.key) == key
|| (key != null
&& key.equals(k))))
return e;//
} while ((e = e.next) != null);
}
}
return null;// ， null
}
注意getNodeが返すタイプはNode:戻り値がnullのときmapに対応するkeyがないことを示し、注意区別valueがnull:keyに対応するvalueがnullであればgetNodeに現れる戻り値e.valueがnullであり、このとき戻り値もnullである.つまりHashMapのget関数はmapに対応するkeyがあるか否かを判断できない:get戻り値がnullの場合、そのkeyを含まない可能性があるkeyのvalueがnullである可能性もあります!では、mapにキーが含まれているかどうかをどのように判断しますか?次のcontains関数解析を参照してください.getNode関数詳細解析:(n-1)&hash:現在keyが存在する可能性のあるバケツインデックスであり、put操作時にもindex=(n-1)&hash位置にノードを格納する.getNodeの主な論理:table[index]のノードのkeyが探しているkeyであれば、そのノードに直接戻ります.そうでない場合:table[index]の位置で検索を行うと、ターゲットkeyのノードが存在するか否かを検索する:ここでの検索はまた2種類に分けられる:チェーンテーブル検索と赤黒ツリー検索、具体的な赤黒ツリーの検索は展開されず、赤黒ツリーは弱いバランス(AVLに対する)BSTであり、赤黒ツリー検索、削除、挿入などの操作はO(lon(n))時間の複雑さ内に完了することを保証することができる.赤黒樹の原理は本稿の範囲内ではないが、赤黒樹の各種操作が実現できることを知っておく必要がある.簡単な点では、赤黒樹をBSTと理解することができる.BSTの検索、挿入、削除などの操作の実現は、前の文章にBST java実現説明があり、赤黒樹は実際にはバランスのとれたBSTである.(10)contains関数ソース分析:
public boolean containsKey(Object key) {
// get ， map put
// Node ，
// Node key
return getNode(hash(key), key) != null;
}