HashMap采用Node<K,V> 數(shù)組來存儲(chǔ)key-value對(duì)，每一個(gè)鍵值對(duì)組成了一個(gè)Node實(shí)體，Node類實(shí)際上是一個(gè)單向的鏈表結(jié) 構(gòu)，它具有Next指針，可以連接下一個(gè)Node實(shí)體。
HashMap在JDK1.8之前和之后的區(qū)別
JDK1.8 之前，數(shù)組 + 鏈表 存儲(chǔ)結(jié)構(gòu)
缺點(diǎn)就是哈希函數(shù)很難使元素百分百的均勻分布，這會(huì)產(chǎn)生一種極端的可能，就是大量的元素存在一個(gè)桶里
JDK1.8 之后：數(shù)組 + 鏈表 + 紅黑樹
- 添加元素時(shí)：鏈表長(zhǎng)度 大于8的時(shí)候，轉(zhuǎn)換為紅黑樹
- 刪除元素、擴(kuò)容時(shí)，同上，數(shù)量大于8時(shí)，也是采用紅黑樹形式存儲(chǔ)，但是在數(shù)量較少時(shí)，即數(shù)量小于6時(shí)，會(huì)將紅黑樹轉(zhuǎn)換回鏈表
- 遍歷、查找時(shí)，使用紅黑樹，他的時(shí)間復(fù)雜度O（log n），便于性能的提高。
數(shù)據(jù)結(jié)構(gòu)
存儲(chǔ)結(jié)構(gòu)
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey(){ return key; }
public final V getValue(){ return value; }
public final String toString(){ return key + "=" + value; }
public final int hashCode(){
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue){
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o){
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
// Node<K,V> 數(shù)組
transient Node<K,V>[] table;
//加載因子
final float loadFactor;
//默認(rèn)加載因子 ，容量達(dá)到這個(gè)比例時(shí)自動(dòng)擴(kuò)容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 數(shù)量大于8時(shí)，鏈表轉(zhuǎn)換為紅黑樹形式存儲(chǔ)
static final int TREEIFY_THRESHOLD = 8;
//即數(shù)量小于6時(shí)，會(huì)將紅黑樹轉(zhuǎn)換回鏈表，刪除元素時(shí)remove
static final int UNTREEIFY_THRESHOLD = 6;
//PUT 時(shí)每次都做hash
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//put 函數(shù)核心算法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // 這里的n 表示數(shù)組的長(zhǎng)度。
// hash
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 空實(shí)現(xiàn)
return oldValue;
}
}
++modCount; // modCount 是java集合中Fail-Fast的底層實(shí)現(xiàn)原理
if (++size > threshold) //擴(kuò)容
resize();
afterNodeInsertion(evict);// 空實(shí)現(xiàn)
return null;
}
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
思考
java集合中的快速失?。簃odCount
//?快速失敗是Java集合的一種錯(cuò)誤檢測(cè)機(jī)制，當(dāng)多個(gè)線程對(duì)集合進(jìn)行結(jié)構(gòu)上的改變的操作時(shí)，有可能會(huì)產(chǎn)生fail-fast。
//舉個(gè)例子：假設(shè)存在兩個(gè)線程（線程1、線程2），線程1通過Iterator在遍歷集合A中的元素，在某個(gè)時(shí)候線程2修改了集合A的結(jié)構(gòu)（是結(jié)構(gòu)上面的修改，而不是簡(jiǎn)單的修改集合元素的內(nèi)容），那么這個(gè)時(shí)候程序就可能會(huì)拋出
ConcurrentModificationException異常，從而產(chǎn)生fast-fail快速失敗。
HashMap中遍歷算法如下：
final class KeySet extends AbstractSet<K> {
public final int size(){ return size; }
public final void clear(){ HashMap.this.clear(); }
public final Iterator<K> iterator(){ return new KeyIterator(); }
public final boolean contains(Object o){ return containsKey(o); }
public final boolean remove(Object key){
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator<K> spliterator(){
return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super K> action){
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
if (modCount != mc)
//拋出異常，F(xiàn)ail-Fast
throw new ConcurrentModificationException();
}
}
}優(yōu)化hash 算法
JDK1.8中,是通過hashCode()的高16位異或低16位實(shí)現(xiàn)的:(h=k.hashCode())^(h>>>16),主要是從速度,功效和質(zhì)量來考慮的,減少系統(tǒng)的開銷,也不會(huì)造成因?yàn)楦呶粵]有參與下標(biāo)的計(jì)算,從而引起的碰撞。
//擾動(dòng)函數(shù)：促使元素位置分布均勻，減少碰撞幾率
static final int hash(Object key){
int h;
// 如果key == null 返回的值是 0
// 如果key !=null
// 首先計(jì)算 key 的 hashcode 值賦值給 h ,
// 然后與h 無符號(hào)右移16位后的二進(jìn)制按位異或預(yù)算得到最后hash值
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hash具體實(shí)現(xiàn)過程如下圖所示：
hash 計(jì)算過程與putval函數(shù)的應(yīng)用
- key.hashCode()；返回散列值也就是hashcode，假設(shè)隨便生成的一個(gè)值。
- n表示數(shù)組初始化的長(zhǎng)度是16。
- &（按位與運(yùn)算）：運(yùn)算規(guī)則：相同的二進(jìn)制數(shù)位上，都是1的時(shí)候，結(jié)果為1，否則為零。
- ^（按位異或運(yùn)算）：運(yùn)算規(guī)則：相同的二進(jìn)制數(shù)位上，數(shù)字相同，結(jié)果為0，不同為1。
高16bit不變，低16bit和高16bit做了一個(gè)異或（得到的hashCode轉(zhuǎn)化為32位二進(jìn)制，前16位和后16位低16bit和高16bit做了一個(gè)異或）
為什么這樣實(shí)現(xiàn)呢？
如果當(dāng)n即數(shù)組長(zhǎng)度很小，假設(shè)是16的話，那么n - 1即為1111 ，這樣的值和hashCode直接做按位與操作，實(shí)際上只使用了哈希值的后4位。如果當(dāng)哈希值的高位變化很大，低位變化很小，這樣就很容易造成哈希沖突了，所以這里把高低位都利用起來，從而解決了這個(gè)問題。降低了Hash沖突的概率
為什么要用異或運(yùn)算符
保證了對(duì)象的hashCode的32位值只要有一位發(fā)生改變,整個(gè)hash()返回值就會(huì)改變。盡可能的減少碰撞。
工作原理
存儲(chǔ)對(duì)象時(shí),將K/V鍵值傳給put()方法:
- 調(diào)用hash(K)方法計(jì)算K的hash值,然后結(jié)合數(shù)組長(zhǎng)度,計(jì)算得數(shù)組下標(biāo);
- 調(diào)整數(shù)組大小(當(dāng)容器中的元素個(gè)數(shù)大于capacity*loadfactor時(shí),容器會(huì)進(jìn)行擴(kuò)容resize為2n);
- hash碰撞
i.如果K的hash值在HashMap中不存在,則執(zhí)行插入,若存在,則發(fā)生碰撞;
ii.如果K的hash值在HashMap中存在,且它們兩者equals返回true,則更新鍵值對(duì);
iii.如果K的hash值在HashMap中存在,且它們兩者equals返回false,則插入鏈表的尾部(尾插法)或者紅黑樹中(樹的添加方式)。(JDK1.7之前使用頭插法、JDK1.8使用尾插法)
//get 實(shí)現(xiàn)
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return
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;
}
問題思考？
Q：默認(rèn)初始化大小是多少？為啥是這么多？為啥大小都是2的冪？
A：hash運(yùn)算的過程其實(shí)就是對(duì)目標(biāo)元素的Key進(jìn)行hashcode，再對(duì)Map的容量進(jìn)行取模，而JDK 的工程師為了提升取模的效率，使用位運(yùn)算代替了取模運(yùn)算，這就要求Map的容量一定得是2的冪。HashMap的容量為什么是2的n次冪，和這個(gè)putval方法中（n - 1) & hash的計(jì)算方法有著千絲萬縷的關(guān)系，符號(hào)&是按位與的計(jì)算，這是位運(yùn)算，計(jì)算機(jī)能直接運(yùn)算，特別高效，按位與&的計(jì)算方法是，只有當(dāng)對(duì)應(yīng)位置的數(shù)據(jù)都為1時(shí)，運(yùn)算結(jié)果也為1，當(dāng)HashMap的容量是2的n次冪時(shí)，(n-1)的2進(jìn)制也就是1111111***111這樣形式的，這樣與添加元素的hash值進(jìn)行位運(yùn)算時(shí)，能夠（充分的散列），使得添加的元素均勻分布在HashMap的每個(gè)位置上，減少hash碰撞。
Q:HashMap如何有效減少碰撞？
A: 擾動(dòng)函數(shù)：促使元素位置分布均勻，減少碰撞幾率 、使用final對(duì)象，并采用合適的equals()和hashCode()方法
