HashMap內部有一個Entry數組，可以稱之為hash table。HashMap的默認構造值為初始容量為16，負載因子為0.75，閥值(初始容量*負載因子)為12。其默認構造子如下：
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
/** *//**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 16;
/** *//**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*
* 如果一個較大的值被任意一個帶有參數的構造器指定，最大容量被使用。
*/
static final int MAXIMUM_CAPACITY = 1 << 30; //1073741824
/** *//**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/** *//**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;
/** *//**
* The number of key-value mappings contained in this map.
*/
transient int size;
/** *//**
* The next size value at which to resize (capacity * load factor).
*
* 下一個用來調整的大小值
* @serial
*/
int threshold;
/** *//**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY]; //默認情況下，以容量為16構建Entry數組
init();
}
put方法分析：
<1>HashMap首先判斷key是否為null，如果為null，
<1.1>HashMap從hash table中第0個位置的Entry，如果該Entry不等于null且entry.key也不為null，當前value覆蓋entry的value。
<1.2>否則，在hash table[0]處創建新的key=null的Entry。
<2>
接下來，以key的hashcode做hash運算，獲得hash值。該hash值與hash table的長度-1做與操作，獲得key在當前hash table中的位置索引。
然后檢查在該索引位置是否存在Entry對象，如果存在，且該Entry對象的key的hash值與上面計算的hash值相等，且entry的key與傳入的key相等或者key.equals(entry.key),那么以當前的value值覆蓋舊值，并返回舊值。
如果hash table中不存在key所指定的Entry，那么就要增加新的Entry。在增加Entry后，要檢查容量是否已經達到閥值，如果達到閥值，就以當前hash table的長度的2倍擴展。同時要重新計算entry在新的hash table中的索引位置。注意，由于hash計算可能導致key的hash值可能是重復的，HashMap采用鏈表的方式解決hash值沖突的問題，另外一種解決方法是開放地址法。
以下是put方法部分代碼：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
/**//*這里對key的hasCode做hash*/
int hash = hash(key.hashCode());
/**//*通過hash值與hash表的長度減1做與操作獲取hash表的索引值*/
int i = indexFor(hash, table.length);
/**//*由于hash可能重復，導致獲取重復的索引值，這里通過判斷傳入的key的has值與當前節點的key的has值是否相等，且key相等或者equals相等，來用新的value替換舊值，并返回舊值*/
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;
}
處理key為空的情況：
private V putForNullKey(V value) {
/**//*從0桶查找key為null的Entry。如果桶中有null的Entry，那么把當前新的值設置到Entry中，并返回舊值*/
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;
}
計算key的hash值與計算key所應處在hash table中的位置：
static int hash(int h) {
// 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);
}
/** *//**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
增加entry節點以及擴容：
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];//臨時存儲指定桶索引的Entry
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);//在指定桶索引位置創建新的Entry，并自動把原桶索引的Entry作為當前Entry的next
/**//*當size達到閥值(當前容量*負載因子=threshold)，需要擴容*/
if (size++ >= threshold)
resize(2 * table.length);
}
------------------------------------------------
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
/**//*如果就有容量達到默認的的容量最大值(2的30次方),threshold設為整形的最大值（2的31次方-1）*/
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
/**//*這里把源hash表中的數據拷貝到新的hash表中，注意的是，源hash表中鏈表到新hash表中由頭變成了尾*/
transfer(newTable);
table = newTable;
/**//*設置擴容后新的閥值*/
threshold = (int)(newCapacity * loadFactor);
}
get方法分析：
當調用get方法時，HashMap首先判斷key是否為null,如果為null，其hash值為0，否則通過hash算法計算。
接下來，通過該hash值與hash table的長度-1做與操作，獲得key在hash table中的索引。如果entry不等null，且該傳入key的hash值與entry的hash值相等，且key==entry.key或者key.equals(entry.key)，則返回該entry.value.否則返回null.
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : 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 != null && key.equals(k))))
return e;
}
return null;
}
posted on 2012-02-13 14:42
zhangxl 閱讀(420)
評論(0) 編輯 收藏 所屬分類:
JDK