HashMap采用了数组和链表的数据结构,能在查询和修改方便继承了数组的线性查找和链表的寻址修改,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的。
解决哈希冲突的三个方法:
a.开放定址法
又被称为再散列法,包括线性探测再散列、二次探测再散列、伪随机探测再散列
b.再哈希法
地址冲突后,对哈希结果再次进行哈希,直到不冲突为止
c.链地址法
冲突后的元素组成一个链指向当前地址(HashMap采用的该方式,只是当链表长度超过8后,就会把链表改为红黑树)
以下是具体的put过程(JDK1.8版)
1、对Key求Hash值,然后再计算下标
2、如果没有碰撞,直接放入数组中(碰撞的意思是计算得到的Hash值相同,需要放到同一个bucket中)
3、如果碰撞了,以链表的方式链接到后面
4、如果链表长度超过阀值( TREEIFY THRESHOLD==8),就把链表转成红黑树,链表长度低于6,就把红黑树转回链表
5、如果节点已经存在就替换旧值
6、如果数组满了(容量16*加载因子0.75),就需要 resize(扩容2倍后重排)
选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成很深的问题),遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题,我们知道红黑树属于平衡二叉树,但是为了保持“平衡”是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少,所以当长度大于8的时候,会使用红黑树,如果链表长度很短的话,根本不需要引入红黑树,引入反而会慢。
下面从初始化一个HashMap及put一个键值对,来看下HashMap的resize()
Map exampleMap = new HashMap();
初始化Map则,可以看到exampleMap中,loadFactor是默认值0.75(loadFactor用于设置阈值,即到什么程度执行resize操作)
exampleMap.put("1",1)
map中放入数据,看下源代码做了什么
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 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) {//hash是1的hash值,key是字符串1,value是1
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)//tab的length是16,n的值是16
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)//按一定的规则,确定新增的参数放在tab数组的tab[i]位置,如果该位置为空,则直接初始化Node放入该位置;
tab[i] = newNode(hash, key, value, null);
else {//如果tab[i]不为空进入该分支
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))//如果hash相同,key相同,则替换tab[i]
e = p;
else if (p instanceof TreeNode)//判断如果tab[i]是treeNode,则把当前数据放入红黑树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//如果tab[i]是普通Node,则在tab[i]维护的链尾部新增,当链接的Node数量大于8后,要把链改为红黑树结构存储
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);
return oldValue;
}
}
++modCount;
if (++size > threshold)//添加Node之后判断当前map中数据量是否大于12(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR),如果大于需要resize,否则结束当前操作
resize();
afterNodeInsertion(evict);
return null;
}