HashMap是一个散列桶（数组和链表或数组和红黑树），它存储的内容是键值对(key-value)映射,不是线程安全的，HashTable是线程安全的
首先，我们先看下HashMap结构
image.png
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值并不一定相同
**/
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;
}
}
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)
resize();
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扩容链表中数据可能存在以下情况，扩容前
image.png
扩容后 元素位置如下
image.png
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增加对红黑树查找
四、几个问题
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，桶的初始结构如下
image.png
假设 t1和t2 都运行到 p.next = newNode(hash, key, value, null)这句（假设已经完成newNode(hash, key, value, null)，但是没指向p.next），此时p为b元素
，t1线程没有获得cpu运行，t2将d元素插入，t2插入后结构如下
image.png
这时t1获得cpu运行，t1将c 指向 p.next，插入后结构如下，导致d元素缺失
image.png
2.在resize()方法时
我们假设有2个线程t1和t2,假设扩容前HashMap结构如下（我们在resize()举例的）
假设扩容后a和c还继续在桶1，b和d在桶5
image.png
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缺失
image.png
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为什么采用尾插法，后续待补充
网友评论