HashMap內(nèi)部有一個(gè)Entry數(shù)組，可以稱之為hash table。HashMap的默認(rèn)構(gòu)造值為初始容量為16，負(fù)載因子為0.75，閥值(初始容量*負(fù)載因子)為12。其默認(rèn)構(gòu)造子如下：
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.
*
* 如果一個(gè)較大的值被任意一個(gè)帶有參數(shù)的構(gòu)造器指定，最大容量被使用。
*/
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).
*
* 下一個(gè)用來調(diào)整的大小值
* @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]; //默認(rèn)情況下，以容量為16構(gòu)建Entry數(shù)組
init();
}
put方法分析：
<1>HashMap首先判斷key是否為null，如果為null，
<1.1>HashMap從hash table中第0個(gè)位置的Entry，如果該Entry不等于null且entry.key也不為null，當(dāng)前value覆蓋entry的value。
<1.2>否則，在hash table[0]處創(chuàng)建新的key=null的Entry。
<2>
接下來，以key的hashcode做hash運(yùn)算，獲得hash值。該hash值與hash table的長(zhǎng)度-1做與操作，獲得key在當(dāng)前hash table中的位置索引。
然后檢查在該索引位置是否存在Entry對(duì)象，如果存在，且該Entry對(duì)象的key的hash值與上面計(jì)算的hash值相等，且entry的key與傳入的key相等或者key.equals(entry.key),那么以當(dāng)前的value值覆蓋舊值，并返回舊值。
如果hash table中不存在key所指定的Entry，那么就要增加新的Entry。在增加Entry后，要檢查容量是否已經(jīng)達(dá)到閥值，如果達(dá)到閥值，就以當(dāng)前hash table的長(zhǎng)度的2倍擴(kuò)展。同時(shí)要重新計(jì)算entry在新的hash table中的索引位置。注意，由于hash計(jì)算可能導(dǎo)致key的hash值可能是重復(fù)的，HashMap采用鏈表的方式解決hash值沖突的問題，另外一種解決方法是開放地址法。
以下是put方法部分代碼：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
/**//*這里對(duì)key的hasCode做hash*/
int hash = hash(key.hashCode());
/**//*通過hash值與hash表的長(zhǎng)度減1做與操作獲取hash表的索引值*/
int i = indexFor(hash, table.length);
/**//*由于hash可能重復(fù)，導(dǎo)致獲取重復(fù)的索引值，這里通過判斷傳入的key的has值與當(dāng)前節(jié)點(diǎn)的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;
}
}
/**//*否則增加節(jié)點(diǎn)*/
modCount++;
addEntry(hash, key, value, i);
return null;
}
處理key為空的情況：
private V putForNullKey(V value) {
/**//*從0桶查找key為null的Entry。如果桶中有null的Entry，那么把當(dāng)前新的值設(shè)置到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;
}
計(jì)算key的hash值與計(jì)算key所應(yīng)處在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節(jié)點(diǎn)以及擴(kuò)容：
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];//臨時(shí)存儲(chǔ)指定桶索引的Entry
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);//在指定桶索引位置創(chuàng)建新的Entry，并自動(dòng)把原桶索引的Entry作為當(dāng)前Entry的next
/**//*當(dāng)size達(dá)到閥值(當(dāng)前容量*負(fù)載因子=threshold)，需要擴(kuò)容*/
if (size++ >= threshold)
resize(2 * table.length);
}
------------------------------------------------
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
/**//*如果就有容量達(dá)到默認(rèn)的的容量最大值(2的30次方),threshold設(shè)為整形的最大值（2的31次方-1）*/
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
/**//*這里把源hash表中的數(shù)據(jù)拷貝到新的hash表中，注意的是，源hash表中鏈表到新hash表中由頭變成了尾*/
transfer(newTable);
table = newTable;
/**//*設(shè)置擴(kuò)容后新的閥值*/
threshold = (int)(newCapacity * loadFactor);
}
get方法分析：
當(dāng)調(diào)用get方法時(shí)，HashMap首先判斷key是否為null,如果為null，其hash值為0，否則通過hash算法計(jì)算。
接下來，通過該hash值與hash table的長(zhǎng)度-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 閱讀(422)
評(píng)論(0) 編輯 收藏 所屬分類:
JDK