HashMap是一个散列桶(数组和链表或数组和红黑树),它存储的内容是键值对(key-value)映射,不是线程安全的,HashTable是线程安全的
首先,我们先看下HashMap结构
HashMap最外层为数组,JDK1.8优化,默认会将超过8个元素的桶转换成红黑树,否则则为链表形式
在这篇中我们将每个数组位置称为桶
一、参数说明
//HashMap初始容量,必须为2的幂 (默认:16)
final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// HashMap最大容量,必须为2的幂 (默认:1 << 30)
final int MAXIMUM_CAPACITY = 1 << 30;
//默认装载因子0.75f (默认:0.75f)
final float DEFAULT_LOAD_FACTOR = 0.75f;
//当桶中元素个数超过这个值,将从链表节点转变为红黑树(默认:8)
final int TREEIFY_THRESHOLD = 8;
//当桶中元素个数小于这个值,将从红黑转变为树链表节点(默认:6)
final int UNTREEIFY_THRESHOLD = 6;
/**table表中元素超过这个值 才会将通中元素转换成红黑树,否则则扩容table
* 这个值应该大于 4*REEIFY_THRESHOLD
* 避免红黑树和扩容之间冲突
*(默认:64)**/
final int MIN_TREEIFY_CAPACITY = 64;
//hash表
transient Node<K,V>[] table
//保存缓存的entrySet()
transient Set<Map.Entry<K,V>> entrySet
// HashMap长度
transient int size
//记录HashMap的修改次数 put()和get() 等方法会进行++操作
transient int modCount
//临界值 当HashMap中元素超过这个值,会触发HashMap扩容
int threshold
//hash表装载因子
final float loadFactor;
二、内部类说明
1.链表类
static class Node<K,V> implements Map.Entry<K,V> {
//HashMap key的hash值
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; }
//此hash值区分HashMap key的hash值
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;
}
}
2 红黑树类
红黑树目前不做摘录
三、方法说明
1.创建方法
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;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**这个方法一定会返回2的幂
* 说明:n |= n >>> 1 等价为 n = n| n>>> 1
* | 或操作(相同位只要一个为1即为1)
* n |= n >>> 1;
* n |= n >>> 2;
* n |= n >>> 4;
* n |= n >>> 8;
* n |= n >>> 16
* 会将 字节码低位全部置为1
* int n = cap - 1; 是为了防止出现 2的最大幂的出现
* 因为字节码首位1之后都是1的字节码 ,加1后首位进1
* 就变成了 首位为1 之后都为0 的字节码
* 也就意味着 类似 cap 为 7会返回 8
*
**/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
也就是说我们创建HashMap时候,无论规定长度多少,threshold 的长度都为2的幂
注意:当我们初始化传入HashMap 长度时候 threshold 赋值 发生在创建时期
当我们不指定HashMap 长度时候 threshold赋值 发生在put时期
2.put()方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 新的元素存放于哪个桶里边 是由key的hash和哈希表长度散列决定
* i = (n - 1) & hash
* & 操作 同时为1,则对应结果位也为1
* 由此可以看出位于同一桶中元素 的hashcode值并不一定相同
* @param onlyIfAbsent if true, don't change existing value
*如果为true,则出现相同key值时候并不会覆盖原来的value值,(不包括null,value为null,onlyIfAbsent不论true或者false都可以覆盖 )
* @param evict if false, the table is in creation mode.
* 如果为假,则表处于创建模式
**/
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)
//如果这个位置没有元素,则新增
tab[i] = newNode(hash, key, value, null);
else {
//p是为红黑树或者链表
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果元素的hash值及key相等,也就意味着插入相同key值元素
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) {
//尾部插入(jdk1.7在头部插入)
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是否为null,不为null则代表之前存在相同key值
if (e != null) { // existing mapping for key
V oldValue = e.value;
//这也是上面我们的解释是为什么值为null,都会覆盖掉。
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//LinkedHashMap实现
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
//LinkedHashMap实现
afterNodeInsertion(evict);
return null;
}
3.resize() 方法
/**Table 扩容
** JDK1.8扩容时,采用头复制,避免链表循
**环死锁问题。**/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//对于最大长度限制
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果当前hash表长度 扩容1倍后不超过长度限制 则进行扩容
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//如果我们刚开始创建HashMap不指定长度,put 会进入这里
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//hash表扩容
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//oldTab[j] 为null,但是e指向oldTab[j],e不为null
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//树形结构
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
//hi存放扩容后的数据,链表中的数据可能在扩容后位置发生变动,附图解释
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
/**e.hash & oldCap,&运算 2个都为1结果才为1,因为从上面得知只
**能为2的幂oldCap ,结果只能为0或者oldCap,
**,*/
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
/**对于链表尾节点处理 ,假设链表存在 a→b→c→d元素,a→c继续落
** 到桶1,但是上面代码未对 c的next节点处理,会导致链表
** a→c→d存在,所以要对尾节点处理 **/
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
对于HashMap扩容链表中数据可能存在以下情况,扩容前
扩容后 元素位置如下
4.get()方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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;
}
查找方法JDK1.8增加对红黑树查找
5.remove()方法
remove方法我们不常用,这里我们看下逻辑
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//查找这个key所在hashtab中的位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
//对比第一个元素是否key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//否则去对比链表或树
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
//p为node的上个节点
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//如果要移除掉的节点是链表头结点,直接将它的下一个结点替换为桶节点
else if (node == p)
tab[index] = node.next;
else
//前面说过p为node上一个节点,所以这里可以将node移除
p.next = node.next;
++modCount;
--size;
//LinkedHashMap实现
afterNodeRemoval(node);
return node;
}
}
return null;
}
四、几个问题
1、HashMap为什么线程不安全
HashMap线程不安全主要体现2个方面
1.在调用put()方法时,如果有2个线程添加元素到相同桶中,因为新的元素会添加到Node next 属性,所以有可能造成数据缺失。HashMap链表插入会执行以下代码
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//尾部插入
p.next = newNode(hash, key, value, null);
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
我们假设HashMap中有个桶中存在2个相同hashcode元素a和b ,有2个线程t1和t2要对这个桶分别插入 c和d,桶的初始结构如下
假设 t1和t2 都运行到 p.next = newNode(hash, key, value, null)这句(假设已经完成newNode(hash, key, value, null),但是没指向p.next),此时p为b元素
,t1线程没有获得cpu运行,t2将d元素插入,t2插入后结构如下
这时t1获得cpu运行,t1将c 指向 p.next,插入后结构如下,导致d元素缺失
2.在resize()方法时
我们假设有2个线程t1和t2,假设扩容前HashMap结构如下(我们在resize()举例的)
假设扩容后a和c还继续在桶1,b和d在桶5
table = newTab;
//hash表扩容
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//oldTab[j] 为null,但是e指向oldTab[j],e不为null
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//树形结构
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
//hi存放扩容后的数据,链表中的数据可能在扩容后位置发生变动,附图解释
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do { 标记1
next = e.next;
/**e.hash & oldCap,&运算 2个都为1结果才为1,因为从上面得知只
**能为2的幂oldCap ,结果只能为0或者oldCap,
**,*/
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) { 标记2
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
假设t1先快速执行标记1 while循环
第一遍while循环
next = e.next = a.next =b;
/**我们假设a还是落到桶1 **/
loHead = e = a;
loTail = e = a;
第二遍while循环
next = e.next = b.next =c;
/**我们假设b还是落到桶5**/
hiHead = e = b;
hiTail = e = b;
第三遍while循环
next = c.next = c.next =d;
/**我们假设c还是落到桶1 loTail .next 此时相当于将a.next指向了c**/
loTail .next = a.next =c ;
loTail = e = c;
第四遍while循环
next = e.next =c.next =d;
/**我们假设b还是落到桶5 hiTail.next 此时相当于将a.next指向了d**/
hiTail.next= b.next = d;
hiTail = e =d;
t1循环执行完毕
此时t1没有继续往下执行代码,t2开始执行循环
第一遍while循环
next = e.next = a.next =c;
/**我们假设a还是落到桶1 **/
loHead = e = a;
loTail = e = a;
第二遍while循环
//没有标记2对尾节点处理 c的next是还指向d的/
next = c.next = c.next =d;
/**我们假设c还是落到桶1 loTail .next 此时相当于将a.next指向了c**/
loTail .next = a.next =c;
loTail = e = c;
第三遍while循环
next = e.next = d.next =null;
/**我们假设b还是落到桶5 hiTail.next 此时相当于将a.next指向了d**/
hiHead = e = d;
hiTail = e = d;
t2循环执行完毕
t1继续执行标记2代码 t2在t1执行完毕后再执行,最终HashMap结构如图,发生元素d缺失
2、链表插入为什么在尾节点插入新的数据
在插入hashcode相同但是key不同的数据时候,jdk1.7采用头部插入,但是1.8采用尾部插入,这样做有什么好处?,上面我们看了1.8的结构,这里简单对HashMap(JDK1.7)做了介绍https://www.jianshu.com/p/eab549ac0359
有很多人说1.8尾插法避免了1.7中扩容死循环问题,链表只是一种数据结构,尾插法和头插法,如果不考虑数据因素,并不会改变链表最终的数据结构,不会因为尾插法和头插法造成死循环,1.8解决扩容死循环问题在于1.8采用从链表头进行复制,复制迁移过程并没有像JDK1.7一样复制完链表逆序排列
关于1.8为什么采用尾插法,后续待补充