Java HashMap深入分析
基于哈希表的 Map 接口的實現。此實現提供所有可選的映射操作，并允許使用 null 值和 null 鍵。（除了非同步和允許使用 null 之外，HashMap 類與 Hashtable 大致相同。）此類不保證映射的順序，特別是它不保證該順序恒久不變。 此實現假定哈希函數將元素適當地分布在各桶之間，可為基本操作（get 和 put）提供穩定的性能。迭代 collection 視圖所需的時間與 HashMap 實例的“容量”（桶的數量）及其大小（鍵-值映射關系數）成比例。所以，如果迭代性能很重要，則不要將初始容量設置得太高（或將加載因子設置得太低）。
HashMap 的實例有兩個參數...
hash存儲過程:
初始化:
1: 首先初始化hash結構, 初始化桶的個數和加載因子.
put(k, v):
1: 通過k的hashcode值再hash的得到h, 再和桶的長度進行indexFor(int h, int length),得出桶的index.
2: 相當于在桶的中尋找出合適的位置.
3: 在這個位置放下這個對象:table[i] = Entry(k, v), Entry實際上是一個鏈表
4: 將數據放在鏈表的一個位置. table[i].next =new Entry(k, v, oldValue).
5: 如果數據增加到臨界值(初始大小*加載因子), 則需要重新創建以前2倍大小的桶(new_table=2*table).
6: 然后將table數據再拷貝到newtable中, 當然拷貝的只是table的索引.
get(k):
1: 通過k的hashcode值再hash的得到h和桶的長度(length). 再進行indexFor(int h, int length),得出桶的index.
2: 取出桶中的數據Entry,由于Entry是一個鏈表所以需要遍歷出k的hash值和key都是相等的數據.
//HashMap
public HashMap() {
//即上文說的加載因子(默認0.75)
this.loadFactor = DEFAULT_LOAD_FACTOR;
//默認大小(12 = 16 0.75)
threshold = (int)(DEFAULT_INITIAL_CAPACITY DEFAULT_LOAD_FACTOR);
//初始化桶的個數
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
//put方法:
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
//hashCode=> hash
int hash = hash(key.hashCode());
//hash => index
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;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
//取出以前數據
Entry<K,V> e = table[bucketIndex];
//對新的數據封裝.
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
//如果容量過大應該重建table結構.
resize(2 * table.length);
}
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);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
//get
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
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;
}</pre>