如有轉(zhuǎn)載請(qǐng)注明出處 http://www.reibang.com/p/f4b5a7025f86
粗略說(shuō)一說(shuō)
HashMap主要是由數(shù)組+鏈表數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的抱环，數(shù)組存儲(chǔ)鏈表，而鏈表中存儲(chǔ)了上一個(gè)節(jié)點(diǎn)地址骄恶、下一個(gè)節(jié)點(diǎn)地址、key和value的值，在jdk1.8中加入了紅黑樹(shù)做鹰，當(dāng)鏈表的長(zhǎng)度超過(guò)一定閾值的時(shí)候會(huì)轉(zhuǎn)換成紅黑樹(shù)。
接下來(lái)我們就詳細(xì)挖一下每一部分都做了什么鼎姐。
get(Object key)
當(dāng)我們要獲取hashMap中的value時(shí)钾麸，需要根據(jù)key來(lái)調(diào)用get方法更振，那我們看一看get方法做了什么操作。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
在return中我們可以看到通過(guò)getNode方法獲取鏈表中的某一個(gè)node節(jié)點(diǎn)喂走，如果node不為空則返回node中的value殃饿，如果node為null則返回null。
在getNode方法中第一個(gè)參數(shù)是對(duì)key的hashCode進(jìn)行了hash處理芋肠，hash是通過(guò)散列算法將一些長(zhǎng)度不一樣的數(shù)據(jù)轉(zhuǎn)換成長(zhǎng)度一樣的數(shù)據(jù)乎芳。一般通過(guò)加法，位運(yùn)算帖池，乘法來(lái)獲取hash奈惑。
舉個(gè)例子：
aa -> aadb
bbb -> bbbc
c -> cedc
那我們來(lái)看看hash(key)是如何生成的？
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Object的hashCode()通過(guò)將物理地址進(jìn)行hash睡汹，然后將hash值右移16位讓高位的參加運(yùn)算再進(jìn)行按照位的異或來(lái)生成的肴甸，這樣能保證生成的數(shù)據(jù)更加散列。
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
(n - 1) & hash 可以得到hash值在數(shù)組中的下標(biāo)囚巴，按位與得到的是0-n-1范圍內(nèi)的值
假設(shè)key得到的hash值為2135657,他的二進(jìn)制是
0000 0000 0010 0000 1001 0110 0110 1001
當(dāng)前數(shù)組的長(zhǎng)度是9原在，那么n-1為8，他的二進(jìn)制是
0000 0000 0000 0000 0000 0000 0000 1000
進(jìn)行&運(yùn)算之后得到的就是8彤叉，當(dāng)前的key對(duì)應(yīng)的hash值就在數(shù)組中的8位置
之后的操作就比較簡(jiǎn)單了庶柿，先判斷鏈表中的第一個(gè)節(jié)點(diǎn)的key是否相同，如果是對(duì)象就判斷地址是否相同秽浇，如果地址不相同在判斷里面存的值是否相同浮庐，如果鏈表的第一個(gè)節(jié)點(diǎn)不匹配，那么就判斷是否是紅黑二叉樹(shù)柬焕，如果是的話就在樹(shù)中進(jìn)行查找审残，如果不是樹(shù)結(jié)構(gòu)就接著找鏈表后面的節(jié)點(diǎn)。
