一、HashMap的关键参数及部分源码解析
1.1 HashMap的几个关键参数
HashMap的源码中存下以下几个常量
//默认容量，默认为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量，最大为2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//负载因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//变为红黑树的阈值，jdk1.8的参数，当链的长度大于8时，则从链表变为红黑树
static final int TREEIFY_THRESHOLD = 8;
//jdk1.8的参数，当红黑树的节点小于6时，则从红黑树转变为链表
static final int UNTREEIFY_THRESHOLD = 6;
//jdk1.8的参数，最小树形化容量阈值，当整个hash表容量大于64时则从链表转变为红黑树
static final int MIN_TREEIFY_CAPACITY = 64;
1.2HashMap的部分源码解析
几个构造方法
1.2.1无参构造
默认给初始容量（16）和负载因子（0.75）
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
1.2.2按容量初始化
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
1.2.3按容量和负载因子初始化
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
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;
//得到比给定initialCapacity大的最接近的2的幂
this.threshold = tableSizeFor(initialCapacity);
}
需要注意的是，这里最终初始化的HashMap的容量不一定是传进来的initialCapacity，而是比该值大的最接近的一个2的幂，这里关键要看下tableSizeFor方法
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;
}
这里解释下为什么会出现5次无符号右移，
假设cap=1，那int n = cap - 1就是0，无论经过多少次右移都是0，最终返回n+1=1也就是2的0次幂；
假设cap>1，那int n = cap - 1后，n>0，在二进制表示中，最高为一定是1，例如00010000，当经过第一次无符号右移一位，并进行或运算后就成了00011000，第二次右移两位或运算，00011110，第三次右移思维或运算，00011111，此后无论怎么右移再进行或运算都会变成00011111，可以看出，每次进行右移或运算，其实就相当于在把最高位后的每一位变成1，这样当最终返回n+1时，就自然而然比最高位还高一位变为1，后面都是0，也就是一个恰好比原给定数大的2的幂次方数。
那为什么最多右移16位呢，因为右移16位并进行或运算，相当于是容量到了2的32次方了，而HashMap的最大容量MAXIMUM_CAPACITY 是2的30次方。
1.2.4按照指定Map初始化一个HashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
可以看到真正核心的方法就是最后这个putVal，这个方法其实就涉及到了HashMap的实现原理，我们接下来详细看
二、HashMap实现原理简述
2.1 数组+链表+红黑树
JDK1.8HashMap数据结构.png
HashMap的底层实际是一张HashTable，也就是会先根据key值来hash，并根据不同的hash结果将原来的key,value键值对放到hashTable这个数组的不同区域，对于相同hash值的key，则使用链表来解决，在jdk1.8后如果链表的长度超过8，则会转化为红黑树。
回到前文1.2.4按照指定Map初始化一个HashMap源码中，这里有两个方法令人在意，一个是 resize();另一个是 putVal(hash(key), key, value, false, evict);
先来看 resize();
2.2 resize()
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;
}
//这里在判断条件中容量也翻倍了
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
//oldCap为0，但阈值不为0时，此时将容量设置为阈值大小即可
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//旧阈值和容量均小于等于0时，此时将容量设置为默认容量，阈值设置为默认容量*默认容量因子0.75
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;
//用新的容量创建新的hashTable数组，并将其赋值给Map中的table
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//如果旧的数组不为空，则遍历旧的数组赋值到新数组上
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
//如果节点是单个节点，则直接将节点定位到新的table上即可
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果节点是红黑树，则需要对红黑树进行rehash操作，红黑树的rehash其实原理上和链表的rehash类似，这里就只以链表为例，在下一个else分支中详解
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//如果节点是链表，则需要对链表进行rehash
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//根据(e.hash & oldCap) 是否为0将链表分为两个部分
do {
next = e.next;
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);
//因为扩容是左移扩容的2倍，所以，新的节点要么还在原位置，要么就是在原位置+原容量的位置上,是否在原位置，取决于(e.hash & oldCap)，如果为0，则表示最高位没有发生变化，还在原位置，否则最高位为1随着左移也扩容了，则在原位置+原容量的位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
2.3 putVal(hash(key), key, value, false, evict)
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 {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果该位置是单节点，且目前的节点的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) {
//直到链表的末尾也没找到相同key的节点，则为新的节点，添加一个node
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//如果长度已经到了需要转变为红黑树的长度-1了，那此时需要转变为红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//如果找到了相同key的节点，则不需要再遍历了
break;
p = e;
}
}
if (e != null) { // existing mapping for key
//e不为空，说明以前map中存在同样的key，将旧值替换
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
//如果size增加后已经超过阈值，则扩容
resize();
afterNodeInsertion(evict);
return null;
}
2.4其他需要说明的
通过上述源码及标注在源码中的注释可以看出来，hashMap的底层其实是数组+链表+红黑树的形式，这里需要说明的是，红黑树是jdk1.8以后才引入到hashMap中的，1.8以前只是单纯的数组+链表的形式。
另外也正是因为这一点变化，jdk1.8后在插入节点时，是采用的尾端插入，而在1.8以前其实是头插入。
三、为什么HashMap是线程不安全的
3.1 putVal时存在数据不一致的可能
通过刚刚的源码可以看出来，hashMap在put值时，是先找到原来的hashtable，取到原来的hash(key)所在位置的链表or红黑树，并遍历找到原来key的数据进行修改或在末尾插入，如果此时两个线程A和B同时进来，并同时取到了hash(key)所在位置的链表or红黑树(此时还没有任何一个线程修改map成功)，假设A和B操作的是同一个key，则会出现ABA问题，如果A和B操作的是不同key且最终都是在队尾新增，则A刚刚在队尾新增的记录，会被B在同样位置新增的数据覆盖，导致A的数据丢失。
3.2 resize()可能导致的死循环
如果两个线程同时发现需要扩容，同时操作某一链表时，可能会导致该链表变成循环链表，此时再去get时就会发生死循环
四、ConcurrentHashMap原理
为了解决HashMap的线程不安全问题，java提供了线程安全的HashMap——ConcurrentHashMap。
ConcurrentHashMap在jdk1.8以前和1.8以后原理上有一定的区别，jdk1.8以前采用的是分段加锁的方式实现，1.8以后则采用CAS写入数据+同步代码块来实现，这里只贴上1.8及1.8以后put值的代码
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//找到的位置为空，则CAS写入数据，确保写入的时候table没有发生变更
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
//需要扩容,底层也是CAS操作+synchronized ，这里不赘述
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
//利用 synchronized 锁写入数据
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
//如果超过阈值，则需要转变为红黑树，这里和HashMap有一点小区别，HashMap是在循环体内部进行的判断，而这里实在循环体外，所以并没有-1
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
网友评论