1.Map
- 键不能重复，否则会覆盖原来的值
- Map使用场景
词典；统计单词频数；配置项；人员信息等等
2.HashMap
1）默认大小为16，负载因子为0.75，threshold在resize()中赋值为16x0.75 = 12
2）HashMap是在put时分配，具体在resize()中分配
3）索引数组位置
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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))))
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) {
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;
}
- 关于hash()
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- tableSizeFor(cap)保证为与cap最接近的2次幂
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;
}
001xxxxxxx
-> 0011xxxxxx
-> 001111xxxx
-> 0011111111
最后再加上1，就是2的幂次方
- if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))先比较hash，效率更高，hash不等比较直接完毕
- 树化：MIN_TREEIFY_CAPACITY=64，桶中bin被树化的最小hash表容量，若没有达到，且桶中bin的数量达到8，则resize()扩容
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
- 扩容resize()
16 - 0000 1111
32 - 0001 1111
根据e.hash & oldCap是否为0将槽拆分为两个表，为0放到loHead，为1放到hiHead，插入新槽的j和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;
}
}
- get()
返回值为null有两种情况：a）<key, null>值为null；b）不存在该key
需要通过containsKey()方法来进行区别
HashMap的键和值均可为null. - HashMap多线程对象丢失与死链分析
对象丢失：并发put时，竞争覆盖；扩容resize-transfer，新增元素放在已遍历区间，或者并发扩容时新表被覆盖
死链：逆序插入。扩容时，线程1获取了链表的视图（原来的顺序），线程2完成了扩容将链表逆序插入（新的顺序与原来的顺序相反），thread1又重新插入导致循环死链 - JDK8与JDK7的改变
a）插入链表尾部
b）增加了红黑树
c）扩容，保证插入有序性；不重新计算hash，使用e.hash&oldCap来判断插入哪个槽
3.TreeMap
- 插入key必须实现Comparable或提供Comparator，因此key不允许null，但是value可以
- HashMap使用hashCode/equals实现去重；
TreeMap依靠Comparable/Comparator实现排序
