Java容器-Map
Java容器-Map
- AbstractMap
- 参考资料
- HashMap、Hashtable、ConcurrentHashMap
- HashMap 的数据结构？
- HashMap 的工作原理？
- HashMap 中两个对象的 hashcode 相同时会发生什么？
- HashMap为什么不直接使用hashCode()作为其哈希数组的下标？
- HashMap 的 table 的容量如何确定？loadFactor 是什么？该容量如何变化？这种变化会带来什么问题？
- HashMap 和 HashTable 有什么区别？
- 1. 线程安全性不同
- 2. 效率不同
- 3. Hash 数组初始化大小不同
- 4. Hash 数组扩容大小不同
- 5. 放入对象时，hashcode 的获取方式不同
- 6. 放入对象时，键-值为空情况不同
- 参考资料
- HashMap，LinkedHashMap，TreeMap 有什么区别？
- HashMap & TreeMap & LinkedHashMap 使用场景？
- Java 中另一个线程安全的、与 HashMap 极其类似的类是什么？同样是线程安全，它与 Hashtable 在线程同步上有什么不同？
- HashMap 与 ConcurrentHashMap 的区别？
AbstractMap
HashMap
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
参考资料
Java8 HashMap源码分析
java8 HashMap源码 详细研读
Java 基础：hashCode方法
深入解析Java对象的hashCode和hashCode在HashMap的底层数据结构的应用
Java提高篇——equals()与hashCode()方法详解
Map的四种遍历方式
Map.Entry
Map是Java中的接口，Map.Entry是Map中的一个内部接口；
Map.Entry是Map声明的一个内部接口，此接口为泛型，定义为Entry<K,V>。它表示Map中的一个实体（一个key-value对）。接口中有getKey(),getValue方法。
Hashtable
HashMap
WeakHashMap
HashMap、Hashtable、ConcurrentHashMap
HashMap 的数据结构？
哈希表结构（链表散列：数组+链表）实现，结合数组和链表的优点。当链表长度超过 8 时，链表转换为红黑树。
/**
* 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.)
*
*/
transient Node<K,V>[] table;
HashMap 的工作原理？
HashMap 底层是 hash 数组和单向链表实现，数组中的每个元素都是链表，由 Node 内部类（实现 Map.Entry接口）实现，HashMap 通过 put & get 方法存储和获取。
存储对象时，将 K/V 键值传给 put() 方法：
①、调用 hash(K) 方法计算 K 的 hash 值，然后结合数组长度，计算得数组下标；
②、调整数组大小（当容器中的元素个数大于 capacity * loadfactor 时，容器会进行扩容resize 为 2n）；
③、 i.如果 K 的 hash 值在 HashMap 中不存在，则执行插入，若存在，则发生碰撞；
ii.如果 K 的 hash 值在 HashMap 中存在，且它们两者 equals 返回 true，则更新键值对；
iii. 如果 K 的 hash 值在 HashMap 中存在，且它们两者 equals 返回 false，则插入链表的尾部（尾插法）或者红黑树中（树的添加方式）。（JDK 1.7 之前使用头插法、JDK 1.8 使用尾插法）（注意：当碰撞导致链表大于 TREEIFY_THRESHOLD = 8 时，就把链表转换成红黑树）
获取对象时，将 K 传给 get() 方法：
①、调用 hash(K) 方法（计算 K 的 hash 值）从而获取该键值所在链表的数组下标；
②、顺序遍历链表，equals()方法查找相同 Node 链表中 K 值对应的 V 值。
hashCode 是定位的，存储位置；equals是定性的，比较两者是否相等。
面试：HashMap 夺命二十一问！鸡哥都扛不住~ 问题2
HashMap 中两个对象的 hashcode 相同时会发生什么？
在 HashMap 中，当两个对象的 hashcode 相同时，这两个对象在哈希数组中的下标相同，会发生"哈希碰撞"；当发生哈希碰撞时，这两个对象会被存储到数组下标对应的链表中。
HashMap面试必问的数据结构相关知识总结 3.当两个对象的 hashCode 相同会发生什么？
HashMap 是怎么解决哈希冲突的？
你知道 hash 的实现吗？为什么要这样实现？
为什么要用异或运算符？
HashMap为什么不直接使用hashCode()作为其哈希数组的下标？
hashcode() 方法的返回值是 int 类型，int 类型的取值范围为 -2^31 ~ 2^31 - 1，而 HashMap 的哈希数组的大小范围在 16~1^30；
很明显，hashcode() 方法生成的哈希值是大于 HashMap 的哈希数组的有效空间的，也就是说，通过 hashcode() 方法生成的哈希值可能落不到哈希数组的有效空间上，因此 HashMap 没有直接使用 hashcode() 的哈希值作为哈希数组的下标
不直接使用 hashcode()作为哈希数组的下标，那 HashMap 是怎么处理其哈希数组的下标的呢？
请你解释 HashMap 的容量为什么是2的n次幂？
那为什么是两次扰动呢？
Java集合必会14问（精选面试题整理） 6）HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？
HashMap 的 table 的容量如何确定？loadFactor 是什么？该容量如何变化？这种变化会带来什么问题？
①、table 数组大小是由 capacity 这个参数确定的，默认是16，也可以构造时传入，最大限制是1<<30；
②、loadFactor 是装载因子，主要目的是用来确认table 数组是否需要动态扩展，默认值是0.75，比如table 数组大小为 16，装载因子为 0.75 时，threshold 就是12，当 table 的实际大小超过 12 时，table就需要动态扩容；
③、扩容时，调用 resize() 方法，将 table 长度变为原来的两倍（注意是 table 长度，而不是 threshold）
④、如果数据很大的情况下，扩展时将会带来性能的损失，在性能要求很高的地方，这种损失很可能很致命。
HashMap中put()方法的过程？
- 调用 hash() 方法获取 key 对应的 hash 值，并根据 hash 值计算数组下标；
- 如果没有出现哈希冲突，则直接放入数组；
如果出现哈希冲突，则判断结点的 key 是否已存在，如果节点已存在，则替换其value；
如果出现哈希冲突，则判断节点的 key 是否已存在，如果节点不存在， 则以尾插法放在链表后面；
如果元素个数超过阀值( TREEIFY THRESHOLD==8)，就把链表转成红黑树；如果元素个数低于6，就把红黑树转回链表； - 如果 hash 数组大小大于 threshold，则调用 resize() 方法进行扩容；
HashMap 中 put() 方法源代码如下：
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
// 1.1 调用 hash 方法计算 key 对应的 hash 值
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) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 1.2 根据 hash 值计算数组下标
if ((p = tab[i = (n - 1) & hash]) == null) // 2.1 如果没有出现 hash 冲突，则直接放入数组
tab[i] = newNode(hash, key, value, null);
else { // 如果出现 hash 冲突
Node<K,V> e; K k;
if (p.hash == hash && // 2.2 如果节点的 key 已存在，则替换其 value
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode) // 直接将节点放入红黑树
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // 2.3 如果出现 hash 冲突，则以尾插法放在链表后面
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 2.4 如果元素个数大于 8，则将链表转换为红-黑树；
// 如果元素个数小于6，则将红-黑树转回链表（扩容时判断并操作）；
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;
// 3. 如果 hash 数组大小大于 threshold, 则调用 resize() 方法进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Hash数组扩容的过程？
创建一个新的数组，其容量为旧数组的两倍，并重新计算旧数组中结点的存储位置。结点在新数组中的位置只有两种，原下标位置或原下标+旧数组的大小。
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
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;
}
// 扩容为原数组的 2 倍大小
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
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;
@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)
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;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
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);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
HashMap 和 HashTable 有什么区别？
1. 线程安全性不同
HashMap 是线程不安全的，而Hashtable 是线程安全的；
HashMap 是 1.2 版本开始加入 JDK 的，是线程不安全的 Map 接口的实现类，具体体现为 HashMap 中的所有方法都没有使用 synchronized 进行修饰；
Hashtable 是 1.0 版本开始加入 JDK 的，是线程安全的 Map 接口的实现类，具体体现为 Hashtable 中的所有方法都有使用 synchronized 进行修饰；
2. 效率不同
由于线程安全，所以 HashTable 的效率比不上 HashMap；
由于线程安全，Hashtable 中的所有方法都有使用 synchronized 进行修饰，而 HashMap 中的所有方法都没有使用 synchronized 进行修饰；synchronized 虽然可以保证线程的安全性，但是其性能消耗较大，因此，Hashtable 相对 HashMap 来说性能更差；
3. Hash 数组初始化大小不同
HashMap 默认初始话大小为16，而 Hashtable 默认初始化大小为 11；
HashMap 默认初始化大小如下：
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
Hashtable 默认初始化大小如下：
/**
* Constructs a new, empty hashtable with a default initial capacity (11)
* and load factor (0.75).
*/
public Hashtable() {
this(11, 0.75f);
}
4. Hash 数组扩容大小不同
HashMap 扩容时，resize 为原大小的 2 倍；Hashtable 扩容时，rehash 为原大小的 2 倍+1；
HashMap 扩若时大小如下：
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
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;
}
// HashMap 扩容时，扩容为原大小的 2 倍
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
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// ......
// ......
// ......
return newTab;
}
Hashtable 扩若时大小如下：
/**
* Increases the capacity of and internally reorganizes this
* hashtable, in order to accommodate and access its entries more
* efficiently. This method is called automatically when the
* number of keys in the hashtable exceeds this hashtable's capacity
* and load factor.
*/
@SuppressWarnings("unchecked")
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// Hashtable 扩容时扩容为原大小的 2倍+1
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
// ......
// ......
// ......
}
5. 放入对象时，hashcode 的获取方式不同
在放入对象时，HashMap 会重新计算 hash 值，而 Hashtable 直接使用对象的 hashcode 作为 hash 值；
HashMap 放入对象时 hashcode 的获取方式如下：
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
// 在放入对象时，HashMap 会重新计算 hash 值
return putVal(hash(key), key, value, false, true);
}
Hashtable 放入对象时 hashcode 的获取方式如下：
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
// 在放入对象时，Hashtable 直接使用对象的 hashcode 作为 hash 值
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
6. 放入对象时，键-值为空情况不同
HashMap最多只允许一条记录的键为null，允许多条记录的值为null，而 Hashtable不允许键-值为空；
放入对象时，HashMap 的键-值要求如下：
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* 放入对象时，HashMap 的键-值都可为空
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
放入对象时，Hashtable 的键-值要求如下：
/**
* Maps the specified <code>key</code> to the specified
* <code>value</code> in this hashtable. Neither the key nor the
* value can be <code>null</code>. <p>
*
* 放入对象时，Hashtable 的键-值都不能为空
*
* The value can be retrieved by calling the <code>get</code> method
* with a key that is equal to the original key.
*
* @param key the hashtable key
* @param value the value
* @return the previous value of the specified key in this hashtable,
* or <code>null</code> if it did not have one
* @exception NullPointerException if the key or value is
* <code>null</code>
* @see Object#equals(Object)
* @see #get(Object)
*/
public synchronized V put(K key, V value) {}
参考资料
面试：HashMap 夺命二十一问！鸡哥都扛不住~ 问题14
HashMap，LinkedHashMap，TreeMap 有什么区别？
HashMap 参考其他问题；
LinkedHashMap 保存了记录的插入顺序，在用 Iterator 遍历时，先取到的记录肯定是先插入的；遍历比 HashMap 慢；
TreeMap 实现 SortMap 接口，能够把它保存的记录根据键排序（默认按键值升序排序，也可以指定排序的比较器）
HashMap面试必问的数据结构相关知识总结 问题12
HashMap & TreeMap & LinkedHashMap 使用场景？
一般情况下，使用最多的是 HashMap。
HashMap：在 Map 中插入、删除和定位元素时；
TreeMap：在需要按自然顺序或自定义顺序遍历键的情况下；
LinkedHashMap：在需要输出的顺序和输入的顺序相同的情况下。
HashMap面试必问的数据结构相关知识总结 问题13
Java 中另一个线程安全的、与 HashMap 极其类似的类是什么？同样是线程安全，它与 Hashtable 在线程同步上有什么不同？
Java 中另一个与 HashMap 极其相似并且线程安全的类是 ConcurrentHashMap 类。
ConcurrentHashMap 与 Hashtable 的不同主要体现在加锁的方式上：
Hashtable 是使用 synchronized 关键字进行加锁，性能较差；
而 ConcurrentHashMap 在 JDK 1.7 中采用的是分段锁，在 JDK 1.8 中采用的是CAS（比较交换）+ synchronized。
HashMap面试必问的数据结构相关知识总结 问题15
HashMap 与 ConcurrentHashMap 的区别？
1. 线程安全性不同
HashMap 是线程不安全的，而 ConcurrentHashMap 是线程安全的；
HashMap 中没有使用任何加锁手段保证线程安全性，而 ConcurrentHashMap 在 JDK1.7 中主要使用分段锁进行加锁，在 JDK1.8 中主要使用 CAS(比较交换) + synchronized 进行加锁；
ConcurrentHashMap 在 JDK1.8 中使用 CAS + synchronized 加锁的源码如下：
/**
* Maps the specified key to the specified value in this table.
* Neither the key nor the value can be null.
*
* <p>The value can be retrieved by calling the {@code get} method
* with a key that is equal to the original key.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}
* @throws NullPointerException if the specified key or value is null
*/
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
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) {
// ConcurrentHashMap 中使用 CAS 保证线程安全性的场景
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)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// ConcurrentHashMap 中使用 synchronized 关键字进行加锁的场景
synchronized (f) {
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)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
2. 放入对象时，键值对为空情况不同
放入对象时，HashMap 中键-值都可为空，而 ConcurrentHashMap 中键-值都不能为空；
放入对象时，HashMap 中键-值都可为空的源码如下：
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* HashMap 中的键-值都可为空
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
放入对象时，ConcurrentHashMap 中键-值都不可为空的源码如下：
/**
* Maps the specified key to the specified value in this table.
* Neither the key nor the value can be null.
*
* ConcurrentHashMap 中键-值都不能为空
*
* <p>The value can be retrieved by calling the {@code get} method
* with a key that is equal to the original key.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}
* @throws NullPointerException if the specified key or value is null
*/
public V put(K key, V value) {
return putVal(key, value, false);
}
参考资料
17.为什么 ConcurrentHashMap 比 Hashtable 效率要高？
HashTable 使用一把锁（锁住整个链表结构）处理并发问题，多个线程竞争一把锁，容易阻塞；
ConcurrentHashMap JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一个 HashMap 分成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基于 Segment，包含多个 HashEntry。
JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度：Node（首结点）（实现 Map.Entry<K,V>）。锁粒度降低了。