Map
- 定义：给定一个键和一个值，你可以将该值存储在一个Map对象. 之后，你可以通过键来访问对应的值
常用Map
| Map | 简介 | 优缺 |
|---|---|---|
| HashMap | 散列桶(数组+链表[+红黑树]) | O(1)~O(lgN)，遍历效率不高 |
| HashTable | synchronized+数组+链表 | |
| LinkedHashMap | HashMap+双向链表 | 插入或查找顺序排序 |
| TreeMap | 红黑树 | key顺序排序 |
| ConcurrentHashMap | 线程安全的HashMap | |
graph TD
A[Map]
B1[HashMap]
B2[HashTable]
B3[TreeMap]
C11[LinkedHashMap]
A-->B1
A-->B2
A-->B3
B1-->C11HashMap
HashMap工作原理
put
- 求Hash值，计算下标
- 如果没有碰撞，放入桶中
- 如果碰撞，以链表方式链接到后面
- [1.8+]如果链表长度超过阈值(8)，就把链表转化为红黑树，链表长度低于阈值(6)，就转回链表。
- 如果节点已经存在，就替换旧值。
- 如果桶满了[容量(16)*加载因子(0.75)],就resize（扩容2倍，重排）
get
- 求Hash值，计算下标
- 调用keys.equals()方法找到链表(红黑树)中正确的节点
resize
- 将数组扩大两倍
- 重新计算每个元素在数组的位置
- 1.7- 采用队头插入，避免尾部遍历，并可以将最近数据放在链表表头，提高热点数据查询效率。
- 1.8+ 采用队尾插入遍历，并增加tail指针，避免了死锁，也避免了尾部遍历，提高了效率。
HashMap深入思考
HashMap hash函数的实现为什么不用简单的‘%’进行取模运算
- 模运算消耗较大(除法，浮点数，十进制转二进制等多种原因)。
- hashMap计算模具体本质:
hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
index = (length - 1) & hash
三次位运算即可得出结果，效率较高。减少碰撞方案
- 扰动函数减少碰撞，即尽可能不同对象尽可能返回不同的hashcode，减少调用equal方法次数。
- 使用final对象，并采取合适的equals和hashCode方法，减少碰撞发生。
- hashMap没有采用的一种解决方案：开放定址法
JDK1.8+ 为什么采取红黑树(RBT)解决链表过深问题而不用其它树结构如二叉查找树(BST)、平衡二叉树(AVL)等。
- BST时间复杂度为n，RBT和AVL为log2N。
- 在插入操作时，AVL可以保证最多仅需三次旋转就平衡，AVL插入次数不可预知。
多线程情况下hashMap在resize时为什么会可能出现死循环。
1.7会发生死循环原因:
void transfer(Entry newTable) {
Entry[] srv = table;
int newCapacity = newTale.length;
for (int j = 0; j < table.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while(e != null);
}
}
}采用队头插入方式，避免了尾部遍历，但当多线程同时操作情况下，可能会产生环形链表(因为在队头插入过程中，会将尾部节点指针指向头部，如果此时通知执行resize操作，即有可能形成环形链表，然后再get操作的时候形成循环死链)
链接
A->B
在头部后面的节点正常来说不会再次从头部插入，但特殊情况下，线程1操作A，线程2以更快速度操作完B->A。 此时，1线程执行，将A放入到链表头部，并指向B，形成环形链表。
hashMap其它设计方案
开放定址法：在散列算法得到一个存储地址之后，如果发生冲突，不是在原处创建一个链表而是按照一定规则寻找周围可用的地址进行插入。
- 根据开放定址法，我们可以使用三个数组即可实现Map，其中，used表示对应的地址是否被使用，即：
keys[], values[], used[]- 分析1步骤，其实used[] 数组是没有必要的，我们可以使用keys=0代表空节点，keys=1代表删除节点的方案取消used[],对于实际keys为0/1的数据单独创建一个合作哨兵对象（sentinel object）即可。这样，map被简化为
keys[]，values[]- 分析2步骤，通常我们的map不会超过Integer.MAX，那么对于部分特殊的Map(例如：Int2IntMaps),我们可以将key和value存储在同一个long中，key存储在低32位，value存储在高32位，这样map被我们进一步简化：
keyValues[]- 继续分析2步骤，单独创建的哨兵对象会增加复杂度，那么可以在初始化阶段随机选择一个int，作为标记，当插入该随机值的数据时，可以返回map中不存在的其它随机值即可。
ps:具体实现可参考：FastUtil、Goldman Sachs Collections、HPPC、Koloboke、Trove
ConcurrentHashMap
1.7版本
Segment分段锁
原理是将原来两层的map结构(数组+链表)变为三层结构(Segment数组 + HashEntry数组 + 链表)，在hashEntry层加锁，就可以实现最大Segment.length的并发度。
size操作
先尝试将所有的Segment元素中的count相加，这样执行两次，然后将两次的结果对比，如果两次结果相等则直接返回；而如果两次结果不同，则再将所有Segment加锁，然后再执行统计得到对应的size值。
1.8版本
放弃分段锁，采用CAS保证数据准确，
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
