1 . HashMap数据结构
源码片段:
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
......
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
// table 是一个Node类型的数组,下文是Node的部分源码
transient Node<K,V>[] table;
... ...
// Node 是一个链表数据结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
...
}
}
整体看来,HashMap是一个由数组 + 链表 结合起来构成的复合型数据结构.
2 . api
put()方法及相关部分源码
...
/**
* put 方法入口
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
...
/**
* hash 方法入口
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
...
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1. 判断是否空,是则扩容一下 (在这个过程中, 顺便将table的引用赋给了tab,tab在之后会被用到)
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 计算被插入元素应该落入索引 i 的值,算法 : 用当前数组的长度和key的hash值做 & 运算；
// 获取tab[i] 处的元素,判断该元素是否为空
// 2. tab[i]处的值是空,hash不冲突,那就新建一个元素实例,并将其放在索引 i处 ，（即tab[i]）ok了.
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 3. tab[i]处的值不是空,hash冲突了
else {
Node<K,V> e; K k;
// 3.1 key与当前位置的老key相等,将老的元素引用赋给e;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 3.2 红黑树的插入处理,如果key值相等,将老的元素引用赋给e;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 3.3 链表的插入处理,,如果key值相等,将老的元素引用赋给e;
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;
}
}
// 如果老元素e存在,说明key是重复插入,那么根据是否"缺席插入" 处理是否进行新老替代,并将老的元素的value返回
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
由源码可知,进入put(k,v)方法时,首先对key 做了hash ① 运算,然后将hash值连同key,value和一些其他参数调用putVal()方法;
putVal()内部实现大致思路是:
(1)首先判断是否是空的,不是则继续下一步,否则重新扩容hashmap,并将(k,v)存放入table中,返回;
(2)不为空,判断table数组在key的hash值所指向索引处是否有值(是否有hash冲突),有 : 则判断value是否相同,相同则替换并返回;不同则进入下一步.
(3)存在hash冲突,并且值不一样,判断node的类型,如果是TreeNode,则将本(key,value)放入该索引处对应红黑树的末尾并返回;否则将本(key,value)放入该索引链表末尾返回.(此处省略了后续回调的代码)
3 . 线程安全
hashmap由于扩容操作涉及到对多个元素进行操作的程序,且有一定次序性,固在多线程环境时,可能会有风险.
transfer()方法源码 :
......
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} // while
}
}
......
由源码可知,扩容部分的逻辑大概是 :
新建一个数组-- newTab其容量为老数组的2倍,然后遍历老的数组-- oldTab,将其中的值拷贝进新的数组即可.
再涉及链表部分操作的时候,对县城情况下会引起首位死循环 (无hash冲突链表的情况下无此风险).
简单地讲:
<1> α线程在刚刚获取到当前元素(e)和下一元素(next)的指针时候,cpu将α线程挂起,切换到β线程,
<2> 在β线程做完扩容后,cpu再切回α线程,此时由于jdk1.7在扩容时,链表会与原链表倒叙(采用头插法导致),其指向关系也发生了变化,而α
线程在按照切换之前指针进行扩容后,新链表倒叙,导致α线程将旧的指向关系带进了新的扩容后的链表,最终导致链表成环.
jdk1.8后,此问题没有了,原因是1.8以后hashMap做了部分优化:
<1> 当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能.
<2> 在扩容时候对链表操作时,引入了两个临时指针,采用尾插法,不会引起死循环的问题了.
但是1.8也不能完全避免hashMap多线程操作时丢失数据的情况,在企业应用中,已知的小概率风险一定会重现. 固稳妥起见还是用ConccurrentHashMap吧.
注释部分
① : hash运算
一种散列算法,其内部调用了jdk的native方法,native方法由c++实现,并编译成dll文件,打包进入了jdk环境.算法的目的是将同一类型,值不相同的数据通过计算后增大他们之间的散列距离(通俗的说,就是加他他们之间的缝隙,减少冲突的几率),应用于求取(非严谨要求的)唯一散列值的场景.
在java中,Object类本身提供的hashCode() 方法调用的是native中的方法,但是不同的子类有时候会有不同的重写.例如 String :
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
其采用了 string 串不同索引处的ASC码与 31 * h 阶乘的方式,计算String 类型数据的hashCode值;
评论区