JDK7ソースコード解析
はじめに
jdk7のHashMapは、配列とリンクリストを基礎構造としており、その中核となるメソッドはputとgetです。これはArrayLsitとLinedListを彷彿とさせますが、これらの実装原理が同じかどうかを考えてみましょう。
以下は、ArrayListのgetとaddメソッドの簡単な分析です。
package setlearn;
import java.util.ArrayList;
/**
*
*/
public class ArrayListLearn {
public static void main(String[] args) {
ArrayList<String> arrayList=new ArrayList<>();
arrayList.add("Name");
arrayList.add(0,"Enoch");
System.out.println(arrayList.get(0));
System.out.println(arrayList.get(1));
}
}
ArrayListには2つのaddメソッドがあります。
考える：添え字が指定されていない場合に、要素が追加される要素を決定する方法は？
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
//インデックスが合法かどうかを判断する
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
ArrayList には size 属性があり、添え字が指定されると、添え字の位置に要素が追加され、添え字が指定されないと、添え字のデフォルトのサイズが要素を追加するサイズになります。
次に、ArrayList の get メソッドを見てください。
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
つまり、配列の値を取得するために着信インデックスによると。
考える：HashMapもこのメソッドを使うのでしょうか？
HashMapはputのputメソッド、およびgetのgetメソッド。図の構造によって見ることができる、もしHashMapもArrayListの同様のメソッドを使用すると、putメソッドは、配列の最初の位置から順番に配列の最後の位置に追加され、配列がいっぱいになると、それはチェーンリストを追加するには、最初の位置の下の配列の最初の位置にされ、その後、順番に追加され、効率のこの方法は良いように見えるので、それは本当にそうですか？配列がいっぱいになると、配列の最初の位置の下に追加され、順番に追加され、この方法の効率がよさそうなので、本当にそうですか？ここでは、getメソッドを考慮する必要があり、彼はキーの値に基づいて、過去の1つずつトラバーサルする必要があります。明らかにこのgetの効率は低く、getの効率はputよりもずっと低く、これは許されません。だからHashMapのputとgetはどのように実現するのですか？
putメソッドの簡単な分析
ArrayListのような方法は適切ではないので、その後、それを実装する方法を置く？
推測してみましょう：
put(key,value);
key-->key.hashCode()-->-->-->
index-->index%table.length
異なるキーは異なるハッシュコード値を持っていますが、バランスを取った後、配列内のそれらの位置は同じである可能性があり、ここで連鎖リスト構造が使用されます。
public class Node{
private Object content;
private Node next;
public Node(Object content,Node next){
this.content=content;
this.next=next;
}
}
連鎖表はどのように挿入するのですか？ここで効率の観点から、それはヘッド挿入方法の使用である必要があります、つまり、添え字の配列の場合には、チェーンテーブルを横断する時間を短縮するように、チェーンテーブルの先頭として値、新しい値を持っています。
対応するコード
public static void main(String[] args) {
Node header=new Node(new Object(),null);
header.next=new Node(new Object,null);
new Node(new Object(),header);
}
要約すると、putメソッドの一般的な流れは、擬似コードで次のように表されます。
put(key,value){
int hashcode=key.hashCode();
//添え字はインデックスの最初の要素である
//table[index]=new Entry(key,value,null);
//ヘッダー挿入メソッドの一般的な実装形式
table[index]=new Entry(key,value,table[index]);
}
上記は、putメソッドの一般的な実行方法を理解するために、ソースコードの観点からputメソッドを簡単に分析したものです。
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key
key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
テーブルが空の場合、inflateTable(threshold)メソッドを実行し、テーブルサイズを初期化します。次にハッシュ値を取得します。ハッシュ値とテーブルサイズによると、配列の添え字の形成。次に、for ループに入ります。ループは、チェーン・テーブルの配列添え字の下でトラバースされ、プットされたキーとチェーン・テーブルの下のキーが同じ場合は、元のキー値の値が返されます。
public class HashMapLearn {
public static void main(String[] args) {
HashMap<String,String> map=new HashMap<>();
map.put("a","a");
System.out.println(map.put("a","b"));
}
}
出力: a.
同じ値を持つキーがない場合は、NULL が返されます。
次に、addEntry メソッドに進みます。
void addEntry(int hash, K key, V value, int bucketIndex) {
//もっと考える、もっと読む、もっと学ぶ
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
if文は展開操作です。
次に createEntry() メソッドに進みます。
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
これは、上で分析した単純な put メソッドの実装です。
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
HashMapの初期化配列
HashMap<String,String> map=new HashMap<>(F);
オブジェクトの作成におけるHashMapでは、配列の容量と負荷率を設定できます。
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);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
threshold のデフォルトのサイズは 16、loadFactor のデフォルトのサイズは 0.75 です。
テーブルは空なので、put時に初期化する必要があります。
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
//以下は、単純な解析の拡張と組み合わせる。
initHashSeedAsNeeded(capacity);
}
テーブルのデフォルトは空なので、inflateTable メソッドで配列を初期化し、配列のサイズを決定します。
容量を取得するには、roundUpToPowerOf2() メソッドに入る必要があります。
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
Integer.highestOneBit() メソッドに注目します。
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
//入力はint型で、長さは32ビットである。
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
17を例にとってみよう：
17 ----->
右に1ビットシフトする：
右に2ビットシフトする：
4ビットを右にシフトする：
右に8ビットシフトする： ------
右に16ビットシフトする： ------
return (-)=()
16は、最大値の2の17乗より小さい。
分析：それは例か全体か？
001* ****例えば、上の例によれば、結果は次のようになるはずだ。
001* ****
右に1ビットシフトする 0001 ****
0011 ****
右に2シフトする **
**
4ビットを右にシフトする
右に8ビットシフトする
右に16ビットシフトする
return ==>
要約すると、このメソッドは渡された値の2のべき乗よりも小さい最大値を返します。
戻るroundUpToPowerOf2に、値を取るためにMAXIMUM_CAPACITYよりも大きい、それは1を取る1未満の場合、それ以外のInteger.highestOneBit（<< 1）の実装では、上記の分析から、それはInteger.highestOneBitが得られる2のべき乗の現在の値よりも小さいことがわかります。最大値。
numを 0010 **** *数字の中に1があるかもしれないし、全部に0があるかもしれない。
すべてが0のとき (num-1)<<1 --> -->
highestOneBit() --->
すべてが0でない場合-1その後、最上位ビットはまだ1 0010 ****
010* ***0--->highestOneBit -->
これは、出力が最小値の2のべき乗の現在の値よりも大きいことがわかります。
したがって、しきい値に渡される配列の初期化は、生成される配列の最終的な長さではないことがわかります。
Think: なぜ容量は2のべき乗でなければならないのですか？
put メソッド配列添え字生成
putメソッドを簡単に分析すると、キーの位置が順番に格納されるのではなく、ランダムに格納されることがわかりますが、この2つの要件を可能な限り満たす方法として
- 生成されるインデックスが範囲外でないこと
- 可能な限り、各位置に格納される平均値。
int hash = hash(key);
int i = indexFor(hash, table.length);
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
hは返される任意のハッシュ値であり、配列の初期化から、長さの値は2のべき乗でなければなりません。
仮にhが
length である場合、その格納場所は0-15
h&---> & -->
つまり、任意のインデックスで生成された任意のハッシュ値（これは2のべき乗で初期化された配列としても理解できる）に従っている。
考えてみてください。
A: ビット演算はコンピュータの中で最速であり、この方法は効率的に機能します。
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
hhの代入結果はkのハッシュ値のままなので、hのisoとシフト操作は、主にハッシュを改善するために、indexforメソッドでhの各ビットの値を最大限に活用することである。
putForNullKey
上記では、putメソッドと言いましたが、putForNullKeyメソッドだけは言っていません。その名の通り、NULL値処理のためにキーに入れるメソッドです。
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//変数は話の展開の中に出てくる。
modCount++;
addEntry(0, null, value, 0);
return null;
}
table[0] Entry<K,V>オブジェクト, 見つけるe==nullの場合e.key==null古い値を読み込み、新しい値を代入し、最後に古い値を
展開操作
addEntry()メソッドに
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
配列のエントリ数がしきい値を超えたときに配列が展開されます。このとき、現在追加されている位置が NULL ではないことが条件となります。
この時点で resize() メソッドが実行され、新しい容量が古い容量の 2 倍に設定されます。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
最初に oldtable 配列を取得し、そのサイズが Integer.MAX_VALUE と等しいかどうかを判断し、等しい場合はそのまま返します。
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
// false
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
それは上記のindexForメソッドは、配列の添え字を見つけることですが、それはテーブルの新しい容量で、その要素の添え字は、必ずしも古い要素の添え字と同じではないことに注意する必要があります、また、長さの右table.oldlength長さにシフトすることができます。
仮にhが
oldlength
-1 --->
& --->
newlength
-1 --->
& --->
元の結果と比較すると、oldlengthが右に移動していることがわかる。
転送のフローチャート
ご覧のように、転送はテーブルを逆の順序で表示します。
Entry<K,V> next = e.next;2つのスレッドが同時にtransferメソッドに入ったとすると、最初のスレッドは通常の順序で実行され、2番目のスレッドは.
このように、複数のスレッドが存在する場合、循環連鎖テーブルの状況になることがありますが、もちろんこれはそのような状況の1つに過ぎません。
考えてみてください。このようなことが起こり得るのであれば、古い配列のEntry参照を新しい配列に直接コピーすればいいのではないでしょうか？この方が速いだけでなく、循環連鎖表の状況も回避できます。
ここで考えなければならないのは、拡張の最終的な目的です。彼は単に配列の容量を拡張するだけではなく、古い配列の値をそのまま新しい配列に配置します。
initHashSeedAsNeeded()
final boolean initHashSeedAsNeeded(int capacity) {
//hashSeedデフォルトは0なので、currentAltHashingに最初に入るのは間違いなく0である。false
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
//switchingがtrueのときだけ、hashSeedの値を変更することができる。true
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
private static class Holder {
/**
* Table capacity above which to switch to use alternative hashing.
*/
static final int ALTERNATIVE_HASHING_THRESHOLD;
static {
String altThreshold = java.security.AccessController.doPrivileged(
new sun.security.action.GetPropertyAction(
"jdk.map.althashing.threshold"));
int threshold;
try {
threshold = (null != altThreshold)
? Integer.parseInt(altThreshold)
: ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
// disable alternative hashing if -1
if (threshold == -1) {
threshold = Integer.MAX_VALUE;
}
if (threshold < 0) {
throw new IllegalArgumentException("value must be positive integer.");
}
} catch(IllegalArgumentException failed) {
throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
}
ALTERNATIVE_HASHING_THRESHOLD = threshold;
}
}
jdk.map.althashing.thresholdを設定する環境変数があるかどうかを判断し、もしあれば threshold に値を代入し、その値をALTERNATIVE_HASHING_THRESHOLD
jdk.map.althashing.thresholdしたがって、このメソッドのアイデアは、環境変数が設定されているかどうかを判断することです、もしそうなら、配列の容量は、の値よりも大きい場合は、HashSeedが生成されます。
新しいHashSeedが生成されるとき、rehashは真、すなわちハッシュ値が再生成されます。
modCount
public class HashMapLearn {
public static void main(String[] args) {
HashMap<String,String> hashMap=new HashMap<>();
hashMap.put("1","1");
// hashMap.put("2","2");
for (String key:hashMap.keySet()){
if (key.equals("1")){
hashMap.remove(key);
}
}
}
}
例外なし
public class HashMapLearn {
public static void main(String[] args) {
HashMap<String,String> hashMap=new HashMap<>();
hashMap.put("1","1");
hashMap.put("2","2");
for (String key:hashMap.keySet()){
if (key.equals("2")){
hashMap.remove(key);
}
}
}
}
エラー
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextEntry(HashMap.java:922)
at java.util.HashMap$KeyIterator.next(HashMap.java:956)
at setlearn.HashMapLearn.main(HashMapLearn.java:14)
デコンパイルされたファイルを見る
public class HashMapLearn {
public HashMapLearn() {
}
public static void main(String[] args) {
HashMap<String, String> hashMap = new HashMap();
hashMap.put("1", "1");
hashMap.put("2", "2");
//リターンKeyIterator
Iterator i$ = hashMap.keySet().iterator();
while(i$.hasNext()) {
String key = (String)i$.next();
if (key.equals("2")) {
hashMap.remove(key);
}
}
}
}
KeyIterator は HashIterator を継承しています。
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
modCount は HashMap の属性で、put メソッドに戻ると、put するたびに modCount が ++ されることがわかります。expectedModCount: 2 modCount：2
public final boolean hasNext() {
return next != null;
}
private final class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
//例外の発生場所
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key
(key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
removeメソッドでもmodCountが変化するので、modCountの意味は変更された回数であることがわかります。そのため、最初のループの最後ではmodCountは1、expectedModCountは2です。2番目のループでは、nextメソッドのnextEntryメソッドでmodCountとexpectedModCountの値が異なるため例外が発生します。
修正方法：Iterator の remove メソッドを使用します。
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
//削除するたびに、値を再割り当てするexpectedModCount
expectedModCount = modCount;
}
考察：modCountの役割は何ですか？
modCountは高速な失敗許容メカニズムです。
エラーを報告したコードを見直すと、あたかも2つのスレッドがあって、1つはトラバース、もう1つはモディファイをしていて、同時実行の問題があり、その時点でHashMapはこれが起こると考えて例外を投げています。
もっと考える、もっと読む、もっと学ぶ
