在Java集合類中最常用的除了ArrayList外就是HashMap了本文盡自己所能盡量詳細的解釋HashMap的源碼一山還有一山高有不足之處請之處定感謝指定並及時修正
在看HashMap源碼之前先復習一下數據結構
Java最基本的數據結構有數組和鏈表數組的特點是空間連續(大小固定)尋址迅速但是插入和刪除時需要移動元素所以查詢快增加刪除慢鏈表恰好相反可動態增加或減少空間以適應新增和刪除元素但查找時只能順著一個個節點查找所以增加刪除快查找慢有沒有一種結構綜合了數組和鏈表的優點呢?當然有那就是哈希表(雖說是綜合優點但實際上查找肯定沒有數組快插入刪除沒有鏈表快一種折中的方式吧)一般采用拉鏈法實現哈希表哈希表?拉鏈法?可能一下想不起來不過放張圖就了然了
(圖片google來的好多都用了文章用了這張圖了不知道出處了就沒申明作者了)
學計算機的肯定學過這玩意兒也不需要解釋都懂的
鋪墊了這麼多又是數組又是鏈表還有哈希表拉鏈法該入正題了我們什麼時候用到了這些內容具體它是怎麼實現的?
其實我們一直在用(別告訴我你沒用過HashMap什麼的)可能你一直沒去深究沒看到它如何實現的所以一直沒感受到這裡主要分析HashMap的源碼就不再多扯其他的了
HashMap繼承自AbstractMap實現了Map接口(這些內容可以參考《Java集合類》)來看類的定義
public class HashMap extends AbstractMap implements Map Cloneable Serializable
Map接口定義了所有Map子類必須實現的方法Map接口中還定義了一個內部接口Entry(為什麼要弄成內部接口?改天還要學習學習)Entry將在後面有詳細的介紹
AbstractMap也實現了Map接口並且提供了兩個實現Entry的內部類SimpleEntry和SimpleImmutableEntry
定義了接口接口中又有內部接口然後有搞了個抽象類實現接口抽象類裡面又搞了兩個內部類實現接口的內部接口有沒有點繞為什麼搞成這樣呢?先不管了先看HashMap吧
HashMap中定義的屬性(應該都能看明白不過還是解釋一下)
/**
* 默認的初始容量必須是的冪
*/
static final int DEFAULT_INITIAL_CAPACITY = ;
/**
* 最大容量(必須是的冪且小於的次方傳入容量過大將被這個值替換)
*/
static final int MAXIMUM_CAPACITY = << ;
/**
* 默認裝載因子這個後面會做解釋
*/
static final float DEFAULT_LOAD_FACTOR = f;
/**
* 存儲數據的Entry數組長度是的冪看到數組的內容了接著看數組中存的內容就明白為什麼博文開頭先復習數據結構了
*/
transient Entry[] table;
/**
* map中保存的鍵值對的數量
*/
transient int size;
/**
* 需要調整大小的極限值(容量*裝載因子)
*/
int threshold;
/**
*裝載因子
*/
final float loadFactor;
/**
* map結構被改變的次數
*/
transient volatile int modCount;
接著是HashMap的構造方法
/**
*使用默認的容量及裝載因子構造一個空的HashMap
*/
public HashMap() {
thisloadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);//計算下次需要調整大小的極限值
table = new Entry[DEFAULT_INITIAL_CAPACITY];//根據默認容量()初始化table
init();
}
/**
* 根據給定的初始容量的裝載因子創建一個空的HashMap
* 初始容量小於或裝載因子小於等於將報異常
*/
public HashMap(int initialCapacity float loadFactor) {
if (initialCapacity < )
throw new IllegalArgumentException(Illegal initial capacity: +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)//調整最大容量
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= || FloatisNaN(loadFactor))
throw new IllegalArgumentException(Illegal load factor: +
loadFactor);
int capacity = ;
//設置capacity為大於initialCapacity且是的冪的最小值
while (capacity < initialCapacity)
capacity <<= ;
thisloadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
/**
*根據指定容量創建一個空的HashMap
*/
public HashMap(int initialCapacity) {
this(initialCapacity DEFAULT_LOAD_FACTOR);//調用上面的構造方法容量為指定的容量裝載因子是默認值
}
/**
*通過傳入的map創建一個HashMap容量為默認容量()和(mapzise()/DEFAULT_LOAD_FACTORY)+的較大者裝載因子為默認值
*/
public HashMap(Map m) {
this(Mathmax((int) (msize() / DEFAULT_LOAD_FACTOR) +
DEFAULT_INITIAL_CAPACITY) DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}
上面的構造方法中調用到了init()方法最後一個方法還調用了putAllForCreate(Map m)init方法是一個空方法裡面沒有任何內容putAllForCreate看方法名就是創建的時候將傳入的map全部放入新創建的對象中該方法中還涉及到其他方法將在後面介紹
先看初始化table時均使用了Entry這是HashMap的一個內部類實現了Map接口的內部接口Entry
下面給出MapEntry接口及HashMapEntry類的內容
MapEntry接口定義的方法
K getKey();//獲取Key
V getValue();//獲取Value
V setValue();//設置Value至於具體返回什麼要看具體實現
boolean equals(Object o);//定義equals方法用於判斷兩個Entry是否相同
int hashCode();//定義獲取hashCode的方法
HashMapEntry類的具體實現
static class Entry implements MapEntry {
final K key;
V value;
Entry next;//對下一個節點的引用(看到鏈表的內容結合定義的Entry數組是不是想到了哈希表的拉鏈法實現?!)
final int hash;//哈希值
Entry(int h K k V v Entry n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;//返回的是之前的Value
}
public final boolean equals(Object o) {
if (!(o instanceof MapEntry))//先判斷類型是否一致
return false;
MapEntry e = (MapEntry)o;
Object k = getKey();
Object k = egetKey();
// Key相等且Value相等則兩個Entry相等
if (k == k || (k != null && kequals(k))) {
Object v = getValue();
Object v = egetValue();
if (v == v || (v != null && vequals(v)))
return true;
}
return false;
}
// hashCode是Key的hashCode和Value的hashCode的異或的結果
public final int hashCode() {
return (key==null ? : keyhashCode()) ^
(value==null ? : valuehashCode());
}
// 重寫toString方法是輸出更清晰
public final String toString() {
return getKey() + = + getValue();
}
/**
*當調用put(kv)方法存入鍵值對時如果k已經存在則該方法被調用(為什麼沒有內容?)
*/
void recordAccess(HashMap m) {
}
/**
* 當Entry被從HashMap中移除時被調用(為什麼沒有內容?)
*/
void recordRemoval(HashMap m) {
}
}
看完屬性和構造方法接著看HashMap中的其他方法一個個分析從最常用的put和get說起吧
put()
public V put(K key V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(keyhashCode());
int i = indexFor(hash tablelength);
for (Entry e = table[i]; e != null; e = enext) {
Object k;
if (ehash == hash && ((k = ekey) == key || keyequals(k))) {
V oldValue = evalue;
evalue = value;
erecordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash key value i);
return null;
}
當存入的key是null的時候將調用putForNUllKey方法暫時將這段邏輯放一邊看key不為null的情況先調用了hash(int h)方法獲取了一個hash值
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 at default load factor)
h ^= (h >>> ) ^ (h >>> );
return h ^ (h >>> ) ^ (h >>> );
}
這個方法的主要作用是防止質量較差的哈希函數帶來過多的沖突(碰撞)問題Java中int值占個字節即位根據這位值進行移位異或運算得到一個值
static int indexFor(int h int length) {
return h & (length);
}
indexFor返回hash值和table數組長度減的與運算結果為什麼使用的是length?應為這樣可以保證結果的最大值是length不會產生數組越界問題
獲取索引位置之後做了什麼?探測table[i]所在的鏈表所發現key值與傳入的key值相同的對象則替換並返回oldValue若找不到則通過addEntry(hashkeyvaluei)添加新的對象來看addEntry(hashkeyvaluei)方法
void addEntry(int hash K key V value int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash key value e);
if (size++ >= threshold)
resize( * tablelength);
}
這就是在一個鏈表頭部插入一個節點的過程獲取table[i]的對象e將table[i]的對象修改為新增對象讓新增對象的next指向e之後判斷size是否到達了需要擴充table數組容量的界限並讓size自增如果達到了則調用resize(int capacity)方法將數組容量拓展為原來的兩倍
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTablelength;
// 這個if塊表明如果容量已經到達允許的最大值即MAXIMUN_CAPACITY則不再拓展容量而將裝載拓展的界限值設為計算機允許的最大值
// 不會再觸發resize方法而是不斷的向map中添加內容即table數組中的鏈表可以不斷變長但數組長度不再改變
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = IntegerMAX_VALUE;
return;
}
// 創建新數組容量為指定的容量
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
// 設置下一次需要調整數組大小的界限
threshold = (int)(newCapacity * loadFactor);
}
結合上面給出的注釋調整數組容量的內容僅剩下將原table中的內容復制到newTable中並將newTable返回給原table即上面代碼中的transfer(newTable);table = newTable;來看transfer(Entry[] newTable)方法
void transfer(Entry[] newTable) {
// 保留原數組的引用到src中
Entry[] src = table;
// 新容量使新數組的長度
int newCapacity = newTablelength;
// 遍歷原數組
for (int j = ; j < srclength; j++) {
// 獲取元素e
Entry e = src[j];
if (e != null) {
// 將原數組中的元素置為null
src[j] = null;
// 遍歷原數組中j位置指向的鏈表
do {
Entry next = enext;
// 根據新的容量計算e在新數組中的位置
int i = indexFor(ehash newCapacity);
// 將e插入到newTable[i]指向的鏈表的頭部
enext = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
從上面的代碼可以看出HashMap之所以不能保持元素的順序有以下幾點原因第一插入元素的時候對元素進行哈希處理不同元素分配到table的不同位置;第二容量拓展的時候又進行了hash處理;第三復制原表內容的時候鏈表被倒置
一個put方法帶出了這麼多內容接著看看putAll吧
public void putAll(Map m) {
int numKeysToBeAdded = msize();
if (numKeysToBeAdded == )
return;
// 為什麼判斷條件是numKeysToBeAdded不是(numKeysToBeAdded+tablelength)>threshold???
if (numKeysToBeAdded > threshold) {
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + );
if (targetCapacity > MAXIMUM_CAPACITY)
targetCapacity = MAXIMUM_CAPACITY;
int newCapacity = tablelength;
while (newCapacity < targetCapacity)
newCapacity <<= ;
if (newCapacity > tablelength)
resize(newCapacity);
}
for (Iterator> i = mentrySet(erator(); ihasNext(); ) {
MapEntry e = inext();
put(egetKey() egetValue());
}
}
先回答上面的問題為什麼判斷條件是numKeysToBeAdded不是(numKeysToBeAdded+tablelength)>threshold???
這是一種保守的做法明顯地我們應該在(numKeysToBeAdded+tablelength)>threshold的時候去拓展容量但是考慮到將被添加的元素可能會有Key與原本存在的Key相同的情況所以采用保守的做法避免拓展到過大的容量
接著是遍歷m中的內容然後調用put方法將元素添加到table數組中
遍歷的時候涉及到了entrySet方法這個方法定義在Map接口中HashMap中也有實現後面會解釋HashMap的這個方法其它Map的實現暫不解釋
下面介紹在put方法中被調用到的putForNullKey方法
private V putForNullKey(V value) {
for (Entry e = table[]; e != null; e = enext) {
if (ekey == null) {
V oldValue = evalue;
evalue = value;
erecordAccess(this);
return oldValue;
}
}
modCount++;
addEntry( null value );
return null;
}
這是一個私有方法在put方法中被調用它首先遍歷table數組如果找到key為null的元素則替換元素值並返回oldValue;否則通過addEntry方法添加元素之後返回null
還記得上面構造方法中調用到的putAllForCreate嗎?一口氣將put操作的方法看完吧
private void putAllForCreate(Map m) {
for (Iterator> i = mentrySet(erator(); ihasNext(); ) {
MapEntry e = inext();
putForCreate(egetKey() egetValue());
}
}
先將遍歷的過程放在一邊因為它同樣涉及到了entrySet()方法剩下的代碼很簡單只是調用putForCreate方法逐個元素加入
private void putForCreate(K key V value) {
int hash = (key == null) ? : hash(keyhashCode());
int i = indexFor(hash tablelength);
for (Entry e = table[i]; e != null; e = enext) {
Object k;
if (ehash == hash &&
((k = ekey) == key || (key != null && keyequals(k)))) {
evalue = value;
return;
}
}
createEntry(hash key value i);
}
該方法先計算需要添加的元素的hash值和在table數組中的索引i接著遍歷table[i]的鏈表若有元素的key值與傳入key值相等則替換value結束方法若不存在key值相同的元素則調用createEntry創建並添加元素
void createEntry(int hash K key V value int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash key value e);
size++;
}
這個方法的內容就不解釋了上面都解釋過
至此所有put相關操作都解釋完畢了put之外另一個常用的操作就是get下面就來看get方法
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(keyhashCode());
for (Entry e = table[indexFor(hash tablelength)];
e != null;
e = enext) {
Object k;
if (ehash == hash && ((k = ekey) == key || keyequals(k)))
return evalue;
}
return null;
}
該方法分為key為null和不為null兩塊先看不為null的情況先獲取key的hash值之後通過hash值及tablelength獲取key對應的table數組的索引遍歷索引的鏈表所找到key相同的元素則返回元素的value否者返回null不為null的情況調用了getForNullKey()方法
private V getForNullKey() {
for (Entry e = table[]; e != null; e = enext) {
if (ekey == null)
return evalue;
}
return null;
}
這是一個私有方法只在get中被調用該方法判斷table[]中的鏈表是否包含key為null的元素包含則返回value不包含則返回null為什麼是遍歷table[]的鏈表?因為key為null的時候獲得的hash值都是
添加(put)和獲取(get)都結束了接著看如何判斷一個元素是否存在
HashMap沒有提供判斷元素是否存在的方法只提供了判斷Key是否存在及Value是否存在的方法分別是containsKey(Object key)containsValue(Object value)
containsKey(Object key)方法很簡單只是判斷getEntry(key)的結果是否為null是則返回false否返回true
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
final Entry getEntry(Object key) {
int hash = (key == null) ? : hash(keyhashCode());
for (Entry e = table[indexFor(hash tablelength)];
e != null;
e = enext) {
Object k;
if (ehash == hash &&
((k = ekey) == key || (key != null && keyequals(k))))
return e;
}
return null;
}
getEntry(Object key)也沒什麼內容只是根據key對應的hash值計算在table數組中的索引位置然後遍歷該鏈表判斷是否存在相同的key值
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
Entry[] tab = table;
for (int i = ; i < tablength ; i++)
for (Entry e = tab[i] ; e != null ; e = enext)
if (valueequals(evalue))
return true;
return false;
}
private boolean containsNullValue() {
Entry[] tab = table;
for (int i = ; i < tablength ; i++)
for (Entry e = tab[i] ; e != null ; e = enext)
if (evalue == null)
return true;
return false;
}
判斷一個value是否存在比判斷key是否存在還要簡單就是遍歷所有元素判斷是否有相等的值這裡分為兩種情況處理value為null何不為null的情況但內容差不多只是判斷相等的方式不同
這個判斷是否存在必須遍歷所有元素是一個雙重循環的過程因此是比較耗時的操作
接著看HashMap中刪除相關的操作有remove(Object key)和clear()兩個方法
remove(Object key)
public V remove(Object key) {
Entry e = removeEntryForKey(key);
return (e == null ? null : evalue);
}
看這個方法removeEntryKey(key)的返回結果應該是被移除的元素如果不存在這個元素則返回為nullremove方法根據removeEntryKey返回的結果e是否為null返回null或evalue
removeEntryForKey(Object key)
final Entry removeEntryForKey(Object key) {
int hash = (key == null) ? : hash(keyhashCode());
int i = indexFor(hash tablelength);
Entry prev = table[i];
Entry e = prev;
while (e != null) {
Entry next = enext;
Object k;
if (ehash == hash &&
((k = ekey) == key || (key != null && keyequals(k)))) {
modCount++;
size;
if (prev == e)
table[i] = next;
else
prevnext = next;
erecordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
上面的這個過程就是先找到table數組中對應的索引接著就類似於一般的鏈表的刪除操作而且是單向鏈表刪除節點很簡單在C語言中就是修改指針這個例子中就是將要刪除節點的前一節點的next指向刪除被刪除節點的next即可
clear()
public void clear() {
modCount++;
Entry[] tab = table;
for (int i = ; i < tablength; i++)
tab[i] = null;
size = ;
}
clear()方法刪除HashMap中所有的元素這裡就不用一個個刪除節點了而是直接將table數組內容都置空這樣所有的鏈表都已經無法訪問Java的垃圾回收機制會去處理這些鏈表table數組置空後修改size為
這裡為什麼不直接操作table而是通過tab呢?希望有知道的大俠指點一二
主要方法看的差不多了接著看一個上面提到了好幾次但是都擱在一邊沒有分析的方法entrySet()
entrySet()
public Set> entrySet() {
return entrySet();
}
private Set> entrySet() {
Set> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}
為什麼會有這樣的方法只是調用了一下entrySet而且entrySet的名稱看著就很奇怪再看entrySet方法中為什麼不直接return entrySet!=null?entrySet:(entrySet = new EntrySet)呢?
上面的疑問還沒解開但是先看entrySet這個屬性吧在文章開頭的屬性定義中並沒有給出這個屬性下面先看一下它的定義
private transient Set> entrySet = null;
它是一個內容為MapEntry的Set看看在哪些地方往裡面添加了元素
為什麼上面的那句話我要把它標成紅色?因為這是一個陷阱在看代碼的時候我就陷進去了
仔細看EntrySet這個類
private final class EntrySet extends AbstractSet> {
public Iterator> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof MapEntry))
return false;
MapEntry e = (MapEntry) o;
Entry candidate = getEntry(egetKey());
return candidate != null && candidateequals(e);
}
public boolean remove(Object o) {
return removeMapping(o) != null;
}
public int size() {
return size;
}
public void clear() {
HashMapthisclear();
}
}
看到了什麼?這個類根本就沒屬性它只是個代理因為它內部類可以訪問外部類的內容debug的時候能看到的屬性都是繼承或者外部類的屬性輸出的時候其實也是調用到了父類的toString方法將HashMap中的內容輸出了
keySet()
public Set keySet() {
Set ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
}
是不是和entrySet()方法很像!
private final class KeySet extends AbstractSet {
public Iterator iterator() {
return newKeyIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return HashMapthisremoveEntryForKey(o) != null;
}
public void clear() {
HashMapthisclear();
}
}
同樣是個代理類containsremoveclear方法都是調用的HashMap的方法
values()
public Collection values() {
Collection vs = values;
return (vs != null ? vs : (values = new Values()));
}
private final class Values extends AbstractCollection {
public Iterator iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMapthisclear();
}
}
values()方法也一樣是代理只是Values類繼承自AbstractCollention類而不是AbstractSet
還有一個重要的內容沒有進行說明那就是迭代器HashMap中的entrySet()keySet()values()等方法都使用到了迭代器Iterator的知識其他集合類也有使用到迭代器
From:http://tw.wingwit.com/Article/program/Java/ky/201311/28065.html
