前言
從開始學(xué)java起就接觸了HashMap, 用起來很簡(jiǎn)單, 存的是鍵值對(duì), 取的時(shí)候根據(jù)鍵取出對(duì)應(yīng)的值. 但是它內(nèi)部的數(shù)據(jù)結(jié)構(gòu)是怎么樣的, 是怎么實(shí)現(xiàn)存取操作, 始終沒研究過.
最近在看LruCache, 內(nèi)部主要用到了LinkedHashMap, LinkedHashMap繼承了HashMap, 為了弄懂LruCache的緩存原則, 才看了HashMap的源碼, 才有了這篇文章.
注意: 這里分析的是jdk1.7中HashMap, 實(shí)現(xiàn)起來比較簡(jiǎn)單, jdk1.8中對(duì)HashMap優(yōu)化了很多, 變動(dòng)比較大, 后續(xù)文章會(huì)涉及到.
HashMap的數(shù)據(jù)結(jié)構(gòu)
看HasMap的源碼會(huì)發(fā)現(xiàn)有一個(gè)數(shù)組, 數(shù)組中每一個(gè)元素都是HashMapEntry:
transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
看下靜態(tài)內(nèi)部類HashMapEntry的結(jié)構(gòu):
static class HashMapEntry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
HashMapEntry<K,V> next;
int hash;
/**
* Creates new entry.
*/
HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
保存了key, value, hash, 還有一個(gè)next HashMapEntry, 是一個(gè)單鏈表.
So, HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組, 而數(shù)組上每一個(gè)元素都是一個(gè)單鏈表. (注意: key為空時(shí)存儲(chǔ)在數(shù)組第0位)
代碼解析
看代碼當(dāng)然先看構(gòu)造函數(shù)了
static final int DEFAULT_INITIAL_CAPACITY = 4;//默認(rèn)初始容量, 必須是2的倍數(shù)
static final float DEFAULT_LOAD_FACTOR = 0.75f;//默認(rèn)加載因子
static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
initialCapacity = DEFAULT_INITIAL_CAPACITY;//最小容量是4
}
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
threshold = initialCapacity;
init();
}
//需要子類復(fù)寫, 進(jìn)行創(chuàng)建之后, 存儲(chǔ)數(shù)據(jù)之前的初始化操作
void init() {
}
然后是我們經(jīng)常用到的幾個(gè)方法:
1. put
public V put(K key, V value) {
//如果數(shù)組為空, 就去填充數(shù)組, threshold為初始容量
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
key為空時(shí), 存儲(chǔ)value
if (key == null)
return putForNullKey(value);
//根據(jù)key獲取到hash值
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
//根據(jù)hash值計(jì)算出一個(gè)下標(biāo)
int i = indexFor(hash, table.length);
//遍歷該坐標(biāo)上的鏈表
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果找到hash值相等, key也相等的Entry, 替換value, 因此hashmap存數(shù)據(jù), key相等時(shí), value會(huì)覆蓋
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//如果遍歷完鏈表未發(fā)現(xiàn)hash值和key相等的entry, 就通過addEntry把key和value存進(jìn)數(shù)組
modCount++;
addEntry(hash, key, value, i);
return null;
}
//數(shù)組為空, 初始化數(shù)組
private void inflateTable(int toSize) {
// roundUpToPowerOf2返回2的N次方, 根據(jù)初始容量獲取數(shù)組大小
int capacity = roundUpToPowerOf2(toSize);
// 數(shù)組大小*加載因子獲取到一個(gè)臨界值, 該臨界值在數(shù)組擴(kuò)容時(shí)用到, 后面會(huì)講到
float thresholdFloat = capacity * loadFactor;
if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
thresholdFloat = MAXIMUM_CAPACITY + 1;
}
threshold = (int) thresholdFloat;
table = new HashMapEntry[capacity];
}
//key為null時(shí)存儲(chǔ)數(shù)據(jù)
private V putForNullKey(V value) {
//遍歷數(shù)組第0位的鏈表, 因?yàn)閗ey為空的時(shí)候, hash為0, 對(duì)應(yīng)下標(biāo)也是0
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
//找到key為null的Entry, 就把value替換成新value
if (e.key == null) {
V oldValue = e.value;
e.value = value;
//記錄該entry的值被重寫了
e.recordAccess(this);
return oldValue;//返回舊值
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
重點(diǎn)看下addEntry
void addEntry(int hash, K key, V value, int bucketIndex) {
//判斷數(shù)組大小是否超過臨界值, 如果超過臨界值且數(shù)組當(dāng)前位置不為空就要對(duì)數(shù)組擴(kuò)容
if ((size >= threshold) && (null != table[bucketIndex])) {
//對(duì)數(shù)組擴(kuò)容, 容量變?yōu)?倍
resize(2 * table.length);
//重新計(jì)算key的hash值和對(duì)應(yīng)的下標(biāo)
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
//數(shù)組中增加Entry
void createEntry(int hash, K key, V value, int bucketIndex) {
//先保存當(dāng)前位置的Entry
HashMapEntry<K,V> e = table[bucketIndex];
//新建一個(gè)Entry, next指向之前的Entry, 即新建的Entry加入單鏈表頭部
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
}
總結(jié)一下, 就是根據(jù)key找到對(duì)應(yīng)的下標(biāo), 然后遍歷數(shù)組中該位置上的單鏈表, 如果找到hash和key相等的entry, 就替換value, 返回舊value, 如果沒找到就新建一個(gè)entry, 放在該位置單鏈表的頭部.
下面重點(diǎn)看下數(shù)組擴(kuò)容的方法.
//數(shù)組擴(kuò)容
void resize(int newCapacity) {
//先保存下數(shù)組
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable.length;
//判斷數(shù)組容量是否達(dá)到最大容量
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//新建一個(gè)數(shù)組, 長(zhǎng)度為新容量
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
//把老數(shù)組中的所有元素轉(zhuǎn)移到新數(shù)組中
transfer(newTable);
table = newTable;
//重新計(jì)算數(shù)組擴(kuò)容時(shí)的臨界值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
//遍歷老數(shù)組中所有元素
for (HashMapEntry<K,V> e : table) {
//遍歷單鏈表中所有元素
while(null != e) {
//先保存當(dāng)前entry的next
HashMapEntry<K,V> next = e.next;
//計(jì)算當(dāng)前entry在新數(shù)組中的下標(biāo)
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
//把當(dāng)前entry放到新數(shù)組對(duì)應(yīng)位置上
newTable[i] = e;
//把next及放到單鏈表頭部, 繼續(xù)循環(huán)
e = next;
}
}
}
重新建一個(gè)長(zhǎng)度是之前2倍的數(shù)組, 然后把老數(shù)組中所有元素, 重新計(jì)算位置后一一保存到新數(shù)組中, 這個(gè)工作量是相當(dāng)大的, 所以建議使用HashMap的時(shí)候預(yù)估一下所用的容量, 初始化時(shí)容量稍微大一點(diǎn), 盡量避免數(shù)組擴(kuò)容.
2. get
public V get(Object key) {
//key為空時(shí)獲取value
if (key == null)
return getForNullKey();
//key不為null時(shí)查找value
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
//獲取key為空的value
private V getForNullKey() {
if (size == 0) {
return null;
}
//遍歷數(shù)組第0位的單鏈表, 因?yàn)閗ey為null時(shí), hash值和對(duì)應(yīng)下標(biāo)都是0
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
//查找key不為null的Entry
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//計(jì)算出key的hash值
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
//根據(jù)hash值計(jì)算出對(duì)應(yīng)下表, 遍歷該位置的單鏈表
for (HashMapEntry<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;
}
get方法比put方法簡(jiǎn)單很多, 計(jì)算出對(duì)應(yīng)下標(biāo)后, 遍歷該位置的單鏈表, 如果hash值和key都相等就返回, 沒有就返回null;
3. contains
containsKey: 是否包含key
containsValue: 是否包含value
containsNullValue: 是否包含null
public boolean containsKey(Object key) {
//看數(shù)組中key對(duì)應(yīng)的Entry是否為空
return getEntry(key) != null;
}
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
HashMapEntry[] tab = table;
//遍歷數(shù)組
for (int i = 0; i < tab.length ; i++)
//遍歷該位置的單鏈表
for (HashMapEntry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}
private boolean containsNullValue() {
HashMapEntry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (HashMapEntry e = tab[i] ; e != null ; e = e.next)
if (e.value == null)
return true;
return false;
}
很簡(jiǎn)單, 就是遍歷數(shù)組, 遍歷單鏈表, 看是否有對(duì)應(yīng)值相等的元素.
4. remove
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.getValue());
}
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
//根據(jù)key計(jì)算hash值及對(duì)應(yīng)下表
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
//保存鏈表頭部元素
HashMapEntry<K,V> prev = table[i];
HashMapEntry<K,V> e = prev;
//遍歷該位置的單鏈表
while (e != null) {
//e:當(dāng)前元素 next:下一個(gè)元素 pre:前一個(gè)元素
HashMapEntry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
//如果key對(duì)應(yīng)的entry在頭部, 就把頭部元素刪除, 把next放在鏈表頭.
//如果不在頭部, 就刪除當(dāng)前元素, 把next跟在pre后
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
//鏈表元素下移, 繼續(xù)查找
prev = e;
e = next;
}
return e;
}
5. clear
public void clear() {
modCount++;
Arrays.fill(table, null);
size = 0;
}
很簡(jiǎn)單就是把數(shù)組清空, 數(shù)組長(zhǎng)度置空.
HashMap簡(jiǎn)單介紹完了, 是不是很簡(jiǎn)單, 下面來看下它的子類LinkedHashMap.
