以前寫過一篇源碼分析HashMap數(shù)據(jù)結(jié)構(gòu)的，現(xiàn)在找不回了妖啥，重新簡(jiǎn)單的分析一下HashMap的數(shù)據(jù)結(jié)構(gòu)增強(qiáng)一下自己的記憶，好久不寫博对碌，語言組織會(huì)比較差荆虱。
首先HashMap簡(jiǎn)單的理解應(yīng)該是一種“數(shù)組”加“鏈表的結(jié)構(gòu)”，先貼一個(gè)簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)的圖參考一下：
!
其中，圖中顯示的Entry怀读，表示的是
Entry<K,V>
里面的屬性為：
final K key;
V value;
Entry<K,V> next;
int hash;
可以看到诉位，Entry中存有hash值，當(dāng)前Entry的鍵值對(duì)(K,V),指向下一個(gè)Entry的指針next愿吹。
我們先分析左側(cè)初始化的Entry數(shù)組不从。
transient Entry[] table;
那么初始化大小的為：
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
接著，怎么確定數(shù)據(jù)存放到數(shù)組中的哪一個(gè)Entry中呢犁跪？那么我們先看put方法：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
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;
}
首先put方法會(huì)計(jì)算當(dāng)前key值的hash值椿息，并將hash值傳入到putVal方法。
putVal方法首先判斷表中該hash值的Table[hash & Entry[].length]位置上是否有entry坷衍，如果沒有寝优，就將當(dāng)前的entry放置于此，如有枫耳，就將該位置的entry值設(shè)成當(dāng)前值乏矾，并將next指向原來桶的值。
參考第一個(gè)圖中的展示迁杨。
get的方法可以反向推理钻心，通過hash值找到entry在數(shù)組的位置，然后通過鏈表不斷的往后尋找對(duì)應(yīng)的key值铅协。
那么這里有一個(gè)問題捷沸，當(dāng)table初始定義的大小太小，hashmap存取的數(shù)據(jù)多的時(shí)候狐史，hash值碰撞會(huì)增高痒给，每一個(gè)桶中的存取的鏈表就會(huì)很深。
所以骏全，當(dāng)：size >= threshold苍柏，其中
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
static final float DEFAULT_LOAD_FACTOR = 0.75f;
最后延伸一個(gè)問題，為什么HashMap線程是不安全的姜贡？
因?yàn)樵阪湵碇惺杂酰琻ext指向有可能同時(shí)有兩個(gè)線程同時(shí)修改next的值，造成數(shù)據(jù)被覆蓋的情況楼咳，丟失entry值潘悼。
