HashMap基于哈希表的Map接口實(shí)現(xiàn)瓷式，是以key-value存儲(chǔ)形式存在闽烙。
系統(tǒng)會(huì)根據(jù)hash算法來計(jì)算key-value的存儲(chǔ)位置遥皂，可以通過key快速存取value指攒。
HashMap基于hashing原理，我們通過put()和get()方法儲(chǔ)存和獲取對(duì)象址儒。當(dāng)我們將鍵值對(duì)傳遞給put()方法時(shí)芹枷，它調(diào)用鍵對(duì)象的hashCode()方法來計(jì)算hashcode，然后找到bucket位置來儲(chǔ)存值對(duì)象莲趣。當(dāng)獲取對(duì)象時(shí)鸳慈，通過鍵對(duì)象的equals()方法找到正確的鍵值對(duì)，然后返回值對(duì)象喧伞。
HashMap使用鏈表來解決碰撞問題走芋，當(dāng)發(fā)生碰撞了，對(duì)象將會(huì)儲(chǔ)存在鏈表的下一個(gè)節(jié)點(diǎn)中潘鲫。 HashMap在每個(gè)鏈表節(jié)點(diǎn)中儲(chǔ)存鍵值對(duì)對(duì)象翁逞。
當(dāng)兩個(gè)不同的鍵對(duì)象的hashcode相同時(shí)會(huì)發(fā)生什么？ 它們會(huì)儲(chǔ)存在同一個(gè)bucket位置的鏈表中溉仑。鍵對(duì)象的equals()方法用來找到鍵值對(duì)挖函。
定義
HashMap實(shí)現(xiàn)了Map接口，Map接口定義了鍵映射到值的規(guī)則彼念。HashMap繼承了AbstractMap挪圾，AbstractMap提供接口的主要實(shí)現(xiàn)，以最大限度的減少HashMap實(shí)現(xiàn)Map接口所需的工作逐沙。
初始容量和負(fù)載因子
默認(rèn)初始容量16哲思，默認(rèn)負(fù)載因子0.75。這兩個(gè)參數(shù)是影響HashMap性能的重要參數(shù)吩案，其中容量表示哈希表中桶的數(shù)量棚赔，初始容量是創(chuàng)建哈希表時(shí)的容量，負(fù)載因子是哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿的一種尺度徘郭，它衡量的是一個(gè)散列表的空間的使用程度靠益，負(fù)載因子越大表示散列表的裝填程度越高，反之愈小残揉。對(duì)于使用鏈表法的散列表來說胧后，查找一個(gè)元素的平均時(shí)間是O(1+a)，因此如果負(fù)載因子越大抱环，對(duì)空間的利用更充分壳快，然而后果是查找效率的降低；如果負(fù)載因子太小镇草，那么散列表的數(shù)據(jù)將過于稀疏眶痰，對(duì)空間造成嚴(yán)重浪費(fèi)。系統(tǒng)默認(rèn)負(fù)載因子為0.75梯啤，一般情況下我們是無需修改的竖伯。
數(shù)據(jù)結(jié)構(gòu)
Java中最常用的兩種結(jié)構(gòu)是數(shù)組和模擬指針(引用)，幾乎所有的數(shù)據(jù)結(jié)構(gòu)都可以利用這兩種來組合實(shí)現(xiàn)因宇，HashMap也是如此七婴。實(shí)際上HashMap是一個(gè)“鏈表散列”，如下是它數(shù)據(jù)結(jié)構(gòu)：
組察滑，只是數(shù)組的每一項(xiàng)都是一條鏈本姥。其中參數(shù)initialCapacity就代表了該數(shù)組的長度。
//空表
static final Entry<?,?>[] EMPTY_TABLE = {};
//用于存儲(chǔ)的表杭棵，長度可以調(diào)整婚惫，且必須是2的n次冪
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
每次新建一個(gè)HashMap時(shí)，都會(huì)初始化一個(gè)table數(shù)組魂爪。table數(shù)組的元素為Entry節(jié)點(diǎn)先舷。
其中Entry為HashMap的內(nèi)部類，它包含了鍵key滓侍、值value蒋川、下一個(gè)節(jié)點(diǎn)next，以及hash值撩笆，這是非常重要的捺球，正是由于Entry才構(gòu)成了table數(shù)組的項(xiàng)為鏈表缸浦。
存儲(chǔ)實(shí)現(xiàn)：put(key,value)
public V put(K key, V value) {
//當(dāng)表為空表時(shí)，擴(kuò)展表
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//當(dāng)key為null時(shí)氮兵，保存null在table第一個(gè)位置中
if (key == null)
return putForNullKey(value);
//計(jì)算key的hash值
int hash = hash(key);
//計(jì)算key hash值在table數(shù)組中的位置
int i = indexFor(hash, table.length);
//在i處開始迭代e裂逐，找到key保存的位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//判斷該條鏈上是否有hash值相同的（key相同），若存在相同的泣栈，則直接覆蓋value卜高，返回舊value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//修改次數(shù)加1
modCount++;
//將key，value添加到i位置處
addEntry(hash, key, value, i);
return null;
}
通過源碼我們可以清晰看到HashMap保存數(shù)據(jù)的過程為：首先判斷表是否為空南片，為空的話掺涛，先擴(kuò)展表；然后判斷key是否為null疼进，若為null薪缆，則直接調(diào)用putForNullKey方法。若不為空則先計(jì)算key的hash值伞广，然后根據(jù)hash值搜索在table數(shù)組中的索引位置矮燎，如果table數(shù)組在該位置處有元素，則通過比較是否存在相同的key赔癌，若存在則覆蓋原來key的value诞外，否則將該元素保存在鏈頭（最先保存的元素放在鏈尾）。若table在該處沒有元素灾票，則直接保存峡谊。
迭代：此處迭代原因就是為了防止存在相同的key值，若發(fā)現(xiàn)兩個(gè)hash值（key）相同時(shí)刊苍，HashMap的處理方式是用新value替換舊value既们，這里并沒有處理key，這就解釋了HashMap中沒有兩個(gè)相同的key正什。
-
int hash = hash(key);hash方法啥纸，計(jì)算key的hash值，代碼如下：final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); // 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); } -
對(duì)于HashMap的table而言婴氮，數(shù)據(jù)分布需要均勻（最好每項(xiàng)都只有一個(gè)元素斯棒，這樣就可以直接找到），不能太緊也不能太松主经，太緊會(huì)導(dǎo)致查詢速度慢荣暮，太松則浪費(fèi)空間。計(jì)算hash值后罩驻，怎么才能保證table元素分布均與呢穗酥？我們會(huì)想到取模，但是由于取模的消耗較大，HashMap是這樣處理的：調(diào)用indexFor方法砾跃。
static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1); }HashMap的底層數(shù)組長度總是2的n次方骏啰，在構(gòu)造函數(shù)中存在：capacity <<= 1;這樣做總是能夠保證HashMap的底層數(shù)組長度為2的n次方。當(dāng)length為2的n次方時(shí)抽高，h&(length - 1)就相當(dāng)于對(duì)length取模判耕，而且速度比直接取模快得多厨内，這是HashMap在速度上的一個(gè)優(yōu)化祈秕。
indexFor方法渺贤，該方法僅有一條語句：h&(length - 1)雏胃，這句話除了上面的取模運(yùn)算外還有一個(gè)非常重要的責(zé)任：均勻分布table數(shù)據(jù)和充分利用空間。
當(dāng)length = 2^n時(shí)志鞍，不同的hash值發(fā)生碰撞的概率比較小瞭亮，這樣就會(huì)使得數(shù)據(jù)在table數(shù)組中分布較均勻，查詢速度也較快固棚。
這里我們?cè)賮韽?fù)習(xí)put的流程：當(dāng)我們想往一個(gè)HashMap中添加一對(duì)key-value時(shí)统翩，系統(tǒng)首先會(huì)計(jì)算key的hash值，然后根據(jù)hash值確認(rèn)在table中存儲(chǔ)的位置此洲。若該位置沒有元素厂汗，則直接插入。否則迭代該處元素鏈表并依此比較其key的hash值呜师。如果兩個(gè)hash值相等且key值相等(e.hash == hash && ((k = e.key) == key || key.equals(k))),則用新的Entry的value覆蓋原來節(jié)點(diǎn)的value娶桦。如果兩個(gè)hash值相等但key值不等 ，則將該節(jié)點(diǎn)插入該鏈表的鏈頭汁汗。具體的實(shí)現(xiàn)過程見addEntry方法衷畦，如下：
void addEntry(int hash, K key, V value, int bucketIndex) {
//HashMap元素超過極限，則擴(kuò)容為兩倍
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//創(chuàng)建新的Entry
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
//獲取bucketIndex處的Entry
Entry<K,V> e = table[bucketIndex];
//將新創(chuàng)建的 Entry 放入 bucketIndex 索引處知牌，并讓新的 Entry 指向原來的 Entry
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
- 鏈的產(chǎn)生：這是一個(gè)非常優(yōu)雅的設(shè)計(jì)祈争。系統(tǒng)總是將新的Entry對(duì)象添加到bucketIndex處。如果bucketIndex處已經(jīng)有了對(duì)象角寸，那么新添加的Entry對(duì)象將指向原有的Entry對(duì)象菩混，形成一條Entry鏈，但是若bucketIndex處沒有Entry對(duì)象扁藕，也就是e==null,那么新添加的Entry對(duì)象指向null墨吓，也就不會(huì)產(chǎn)生Entry鏈了。
- 擴(kuò)容問題：隨著HashMap中元素的數(shù)量越來越多纹磺，發(fā)生碰撞的概率就越來越大帖烘，所產(chǎn)生的鏈表長度就會(huì)越來越長，這樣勢(shì)必會(huì)影響HashMap的速度橄杨，為了保證HashMap的效率秘症，系統(tǒng)必須要在某個(gè)臨界點(diǎn)進(jìn)行擴(kuò)容處理照卦。該臨界點(diǎn)在當(dāng)HashMap中元素的數(shù)量等于table數(shù)組長度*加載因子。但是擴(kuò)容是一個(gè)非常耗時(shí)的過程乡摹，因?yàn)樗枰匦掠?jì)算這些數(shù)據(jù)在新table數(shù)組中的位置并進(jìn)行復(fù)制處理役耕。所以如果我們已經(jīng)預(yù)知HashMap中元素的個(gè)數(shù)，那么預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高HashMap的性能聪廉。
讀取實(shí)現(xiàn)：get(key)
通過key的hash值找到在table數(shù)組中的索引處的Entry瞬痘，然后返回該key對(duì)應(yīng)的value即可。
public V get(Object key) {
//若為null板熊，獲取null對(duì)應(yīng)的value
if (key == null)
return getForNullKey();
//getEntry(key)為真正獲取方法
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//根據(jù)key獲取hash值
int hash = (key == null) ? 0 : hash(key);
//取出table數(shù)組中指定索引處的值
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//key相同框全，返回對(duì)應(yīng)的value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
在這里能夠根據(jù)key快速的取到value除了和HashMap的數(shù)據(jù)結(jié)構(gòu)密不可分外，還和Entry有莫大的關(guān)系干签，在前面就提到過津辩，HashMap在存儲(chǔ)過程中并沒有將key，value分開來存儲(chǔ)容劳，而是當(dāng)做一個(gè)整體key-value來處理的喘沿，這個(gè)整體就是Entry對(duì)象。同時(shí)value也只相當(dāng)于key的附屬而已竭贩。在存儲(chǔ)的過程中蚜印，系統(tǒng)根據(jù)key的hashcode來決定Entry在table數(shù)組中的存儲(chǔ)位置，在取的過程中同樣根據(jù)key的hashcode取出相對(duì)應(yīng)的Entry對(duì)象留量。
源碼分析
jdk1.7.0_71
//默認(rèn)初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//系統(tǒng)默認(rèn)負(fù)載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//空表
static final Entry<?,?>[] EMPTY_TABLE = {};
//用于存儲(chǔ)的表窄赋，長度可以調(diào)整，且必須是2的n次冪
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//map的size
transient int size;
//下次擴(kuò)充的臨界值 capacity * load factor
int threshold;
//哈希表的負(fù)載因子
final float loadFactor;
//在使用迭代器遍歷的時(shí)候肪获，用來檢查列表中的元素是否發(fā)生結(jié)構(gòu)性變化（列表元素?cái)?shù)量發(fā)生改變的一個(gè)計(jì)數(shù)）了寝凌，主要在多線程環(huán)境下需要使用，防止一個(gè)線程正在迭代遍歷孝赫，另一個(gè)線程修改了這個(gè)列表的結(jié)構(gòu)较木。
transient int modCount;
//容量閾值，默認(rèn)大小為Integer.MAX_VALUE
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
//計(jì)算哈希值得時(shí)候用
transient int hashSeed = 0;
Holder 靜態(tài)內(nèi)部類,存放一些在虛擬機(jī)啟動(dòng)后才能初始化的值
容量閾值青柄，初始化hashSeed的時(shí)候會(huì)用到該值
static final int ALTERNATIVE_HASHING_THRESHOLD;
static靜態(tài)塊
獲取系統(tǒng)變量jdk.map.althashing.threshold
jdk.map.althashing.threshold系統(tǒng)變量默認(rèn)為-1伐债，如果為-1，則將閾值設(shè)為Integer.MAX_VALUE
HashMap(int initialCapacity, float loadFactor) 指定容量和負(fù)載因子 構(gòu)造
public HashMap(int initialCapacity, float loadFactor) {
...
init();
}
HashMap(int initialCapacity) 指定初始容量的構(gòu)造,負(fù)載因子為默認(rèn)
public HashMap(int initialCapacity) {}
HashMap() 默認(rèn)初始容量和默認(rèn)負(fù)載因子的構(gòu)造
public HashMap(){}
HashMap(Map<? extends K, ? extends V> m) 用map初始化
public HashMap(Map<? extends K, ? extends V> m) {
//調(diào)用構(gòu)造,初始化空的hashMap
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
//擴(kuò)容
inflateTable(threshold);
//把元素放入到HashMap中
putAllForCreate(m);
}
size() key-value映射個(gè)數(shù)
public int size() {
return size;
}
isEmpty()是否為空
public boolean isEmpty() {
return size == 0;
}
get(Object key) 根據(jù)key獲取value
public V get(Object key) {
//獲取key為null的
getForNullKey();
//獲取其他的key,利用hash值查找
getEntry(Object key);
}
containsKey(Object key) 是否包含key
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
put(K key, V value) 將指定的key value放入HashMap中,若已存在key,就替換舊值
public V put(K key, V value) {}
resize(int newCapacity) 重新設(shè)置大小
void resize(int newCapacity){}
transfer(Entry[] newTable, boolean rehash)現(xiàn)有的table放入新的table
void transfer(Entry[] newTable, boolean rehash) {}
putAll(Map<? extends K, ? extends V> m)
把指定的元素 全部放入HashMap中,已經(jīng)存在的key,會(huì)把舊value覆蓋掉
public void putAll(Map<? extends K, ? extends V> m) {}
remove(Object key) 根據(jù)key刪除
public V remove(Object key) {
removeEntryForKey(key);
}
clear() 清空
public void clear(){}
containsValue(Object value) 是否包含value
public boolean containsValue(Object value) {}
clone() 淺拷貝
public Object clone() {}
static class Entry<K,V> implements Map.Entry<K,V> 內(nèi)部類
addEntry(int hash, K key, V value, int bucketIndex) 添加一個(gè)鍵值對(duì)
void addEntry(int hash, K key, V value, int bucketIndex) {}
createEntry(int hash, K key, V value, int bucketIndex) 添加一個(gè)鍵值對(duì)
void createEntry(int hash, K key, V value, int bucketIndex) {}
參考
http://www.cnblogs.com/chenpi/p/5280304.html
http://www.cnblogs.com/justany/archive/2013/02/01/2889335.html
http://tangyanbo.iteye.com/blog/1756536
