HashMapソースコードの理解
HashMap対応のソースコードを見てみましょう.
1.クラス、インタフェース関係
クローンとシーケンス化が分からないので、まずMapを見てください.
2.実装インタフェースMap
3.継承された抽象クラスAbstractMap
この方法は700行あるから、いくつか選んで話します.
3.1構造方法
3.2いくつかの方法
簡単にいくつか紹介しても、実際の意味はありません.
AbstractMapはここを見ていますが、主にHashMapを見ています.
4.HashMap
4.0テキストの説明
HashMapはまず16空間のEntry(キー値ペア)配列を開き、
Entryクラスに含まれる
そして、格納されたkeyに対してhash演算を行い、1つの数字(1-15)を算出し、対応する位置に格納する.
対応する位置にデータがある場合は、現在のデータの代わりに、元のデータの参照を新しいデータ、すなわちnextに割り当てます.一定の値に保存すると、スペースが拡張されます.
クエリーの時にkeyを計算して(1-15)、それから対応する位置をクエリーしてnextに行って、データを取るか終わるかを知っています.
4.1コンストラクション関数.
4.2 putメソッド
4.3 getメソッド
4.4一般的な方法
4.4.1 public boolean containsKey(Object key)
キーをhash計算し、キー値ペアを見つけて結果を返します.
4.4.2 public boolean containsValue(Object value)
配列を巡ってvalueが見つかったことを知っています.性能がかかる.
4.4.3 public void clear()
配列を巡り、すべてnullに設定します.
4.4.4 public V remove(Object key)
対応keyを見つけ、削除し、関連値を更新します.
4.4.5 public Set keySet()
配列全体を返し、このSetは単独で実装されたクラスで、反復器、size、含む、クリア、反復の結果をMapのkeyに返します.実は完全なMapコンテンツを返しました.余分なスペースが開かれていないので、この方法はすぐにできます.
4.4.6 public Collection values()
これは前述と同様に,Mapの全体データを直接返し,Collectionを反復器,size,含む,消去し,反復の結果をMapのvalueに返す.
5.使用するhashアルゴリズム
計算はすべてhashCodeで計算されるので、HashMapに格納されたオブジェクトはhashCodeを1つの値に書かないほうがいいです.hashCodeの各クラスには独自の生成方法があり、Objectはデフォルトでメモリ位置のようですが、IntegerやStringが上書きされているのを見たばかりです.
intは32ビットを占め,符号なし左シフト20ビット,空孔補0,符号なし右シフト20ビットである.まあ、このバイナリ演算子は系統的に見て、まずこのようにします.
6.終了
ここを見ると、HashMapの構造とhashアルゴリズムを理解するのが主です.
同時に二つの疑問が生じたので、先にメモしておきます.
疑問1:抽象クラスAbstractMapだけを実現してはいけませんか?なぜimplements Mapが必要なのか、繰り返さないのか.
疑問2:transient volatileが変数をこのように宣言したのはなぜですか.
1.クラス、インタフェース関係
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializableクローンとシーケンス化が分からないので、まずMapを見てください.
2.実装インタフェースMap
public interface Map<K,V> {
// ， 。
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
V put(K key, V value);
V remove(Object key);
void putAll(Map<? extends K, ? extends V> m);
void clear();
//
Set<K> keySet();
//
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
boolean equals(Object o);
int hashCode();
// ， key-value 。
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
}
}
3.継承された抽象クラスAbstractMap
この方法は700行あるから、いくつか選んで話します.
3.1構造方法
public abstract class AbstractMap<K,V> implements Map<K,V> {
protected AbstractMap() {
}
}3.2いくつかの方法
簡単にいくつか紹介しても、実際の意味はありません.
// ， Map ， Set key+value
public abstract Set<Entry<K,V>> entrySet();
//Map
public int size() {
return entrySet().size();
}
//
public boolean isEmpty() {
return size() == 0;
}
//
public boolean containsValue(Object value) {
// ， Set。
// for each， jdk1.2， 。 。
Iterator<Entry<K,V>> i = entrySet().iterator();
// 。
if (value==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getValue()==null)
return true;
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
// ： equals， ==
if (value.equals(e.getValue()))
return true;
}
}
return false;
}
// ， Set
public V get(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
return e.getValue();
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
return e.getValue();
}
}
return null;
}
// 。
public V put(K key, V value) {
throw new UnsupportedOperationException();
}
//
public V remove(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
Entry<K,V> correctEntry = null;
//key null， key 。
if (key==null) {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
correctEntry = e;
}
} else {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
correctEntry = e;
}
}
//
V oldValue = null;
if (correctEntry !=null) {
oldValue = correctEntry.getValue();
// 。
i.remove();
}
// value。
return oldValue;
}
// Map ，
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
// set clear
public void clear() {
entrySet().clear();
}
AbstractMapはここを見ていますが、主にHashMapを見ています.
4.HashMap
4.0テキストの説明
HashMapはまず16空間のEntry(キー値ペア)配列を開き、
Entryクラスに含まれる
final K key;
V value;
Entry<K,V> next;
final int hash;そして、格納されたkeyに対してhash演算を行い、1つの数字(1-15)を算出し、対応する位置に格納する.
対応する位置にデータがある場合は、現在のデータの代わりに、元のデータの参照を新しいデータ、すなわちnextに割り当てます.一定の値に保存すると、スペースが拡張されます.
クエリーの時にkeyを計算して(1-15)、それから対応する位置をクエリーしてnextに行って、データを取るか終わるかを知っています.
4.1コンストラクション関数.
public HashMap() {
// 0.75f
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 16*0.75=12， 12
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
// 16
table = new Entry[DEFAULT_INITIAL_CAPACITY];
//init 。
init();
}4.2 putメソッド
public V put(K key, V value) {
// key ， 。
if (key == null)
// key null ， 。
return putForNullKey(value);
// hash ，
int hash = hash(key.hashCode());
// hash
int i = indexFor(hash, table.length);
// 。
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// key hash 。
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// value 。
V oldValue = e.value;
e.value = value;
// ， 。
e.recordAccess(this);
// value 。
return oldValue;
}
}
// key map。
//
modCount++;
//
addEntry(hash, key, value, i);
return null;
}
// key。 0 。
private V putForNullKey(V value) {
// ，
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
// key
if (e.key == null) {
// 。
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
// 。
return oldValue;
}
}
modCount++;
// 0 。
addEntry(0, null, value, 0);
return null;
}
// ， hash 。
void addEntry(int hash, K key, V value, int bucketIndex) {
// ，
Entry<K,V> e = table[bucketIndex];
// ， hash ， 。 ， 。
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
// size 。
if (size++ >= threshold)
//
resize(2 * table.length);
}
//
void resize(int newCapacity) {
Entry[] oldTable = table;
//
int oldCapacity = oldTable.length;
// 。
if (oldCapacity == MAXIMUM_CAPACITY) {
// int 。
threshold = Integer.MAX_VALUE;
// 。
return;
}
// , 。
Entry[] newTable = new Entry[newCapacity];
//
transfer(newTable);
// table 。
table = newTable;
// 。
threshold = (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;
do {
Entry<K,V> next = e.next;
// hash 。
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}4.3 getメソッド
// key 。
public V get(Object key) {
//key null
if (key == null)
// 0 。
return getForNullKey();
// key hash。
int hash = hash(key.hashCode());
// indexFor table ， 。 。
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
// key null value。
private V getForNullKey() {
// 0 ， next， key null ， 。
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}4.4一般的な方法
4.4.1 public boolean containsKey(Object key)
キーをhash計算し、キー値ペアを見つけて結果を返します.
4.4.2 public boolean containsValue(Object value)
配列を巡ってvalueが見つかったことを知っています.性能がかかる.
4.4.3 public void clear()
配列を巡り、すべてnullに設定します.
4.4.4 public V remove(Object key)
対応keyを見つけ、削除し、関連値を更新します.
4.4.5 public Set
配列全体を返し、このSetは単独で実装されたクラスで、反復器、size、含む、クリア、反復の結果をMapのkeyに返します.実は完全なMapコンテンツを返しました.余分なスペースが開かれていないので、この方法はすぐにできます.
4.4.6 public Collection
これは前述と同様に,Mapの全体データを直接返し,Collectionを反復器,size,含む,消去し,反復の結果をMapのvalueに返す.
5.使用するhashアルゴリズム
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
return h & (length-1);
}計算はすべてhashCodeで計算されるので、HashMapに格納されたオブジェクトはhashCodeを1つの値に書かないほうがいいです.hashCodeの各クラスには独自の生成方法があり、Objectはデフォルトでメモリ位置のようですが、IntegerやStringが上書きされているのを見たばかりです.
intは32ビットを占め,符号なし左シフト20ビット,空孔補0,符号なし右シフト20ビットである.まあ、このバイナリ演算子は系統的に見て、まずこのようにします.
6.終了
ここを見ると、HashMapの構造とhashアルゴリズムを理解するのが主です.
同時に二つの疑問が生じたので、先にメモしておきます.
疑問1:抽象クラスAbstractMapだけを実現してはいけませんか?なぜimplements Mapが必要なのか、繰り返さないのか.
疑問2:transient volatileが変数をこのように宣言したのはなぜですか.