java hashmapソースコードは、プロパティ、構造方法を学ぶ
7157 ワード
java 8におけるHashMapの主な構造は配列、シングルチェーン、レッドツリーからなる。HashMapには、容量が多満杯に達したときにhashmap(負荷係数*容量)を拡張する属性
なぜ容量は2のn乗が必要ですか?後の
load_factor
があり、デフォルトは0.75である。ロード係数が大きいと、スペースが節約できますが、クエリコストが増加します。その主な属性:// 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//
static final int MAXIMUM_CAPACITY = 1 << 30;
// 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// , 。 8
static final int TREEIFY_THRESHOLD = 8;
// resize() , , , 6
static final int UNTREEIFY_THRESHOLD = 6;
// ,hashmap , resize()。 TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
HashMapの一番下の構造は、各ノードにhash値、key、value、next属性、getKey、getValue、toString、hashCode、setValue、equals方法があり、equals(Object o)
方法はkey
とvalue
が同じであると判断してtrue
に戻ります。static class Node<K, V> implements Map.Entry<K, V>{
final int hash;
final K key;
V value;
Node next;
Node(int hash, K key, V value, Node next){
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
...
}
key
に従って、対応するhash値を取得する方法:static final int hash(Object key){
int h;
return (key == 0) ? 0 : (h = key.hasCode())^(h>>>16);
}
配列構造:transient Node[] table;
与えられたcapacityによってこのcapacityより小さい二次べき乗sizeを返します。http://blog.csdn.net/fan2012huan/article/details/51097331:なぜ容量は2のn乗が必要ですか?後の
put()
、get()
の方法では、(size-1)&hash( key hash )
を通じてインデックスを見つけてから動作するので、この式は固定されていて、この式を使うとインデックスが配列範囲内にあることが保証されます。sizeが2のn乗である場合、size-1は奇数となり、最後のビットが1であるため、最後に計算されたインデックス値の最後のビットは0となり、1となり得る。そうでないとインデックスの最後の値は0となり、半分の空間しか利用できなくなる。
static final int tableSizeFor(int cap) {
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;
}
4つのコンストラクタ://
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;
this threshold = tableSizeFor(initialCapacity);
// threshold size*loadFactor , , , table , threshold
}
//
public HashMap(int initialCapacity){
this(initialCapacity, DEFAULT_LOAD_FACTOR);
//
public HashMap(){
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
// Map,
http://blog.sina.com.cn/s/blog_9b6eb6f90102wvft.html
public HashMap(Map extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}