Map成员
- HashMap的详解
- LinkedHashMap的介绍
- TreeMap的介绍
- HashTable与HashMap的区别
- ConcurrentHashMap的详解
基于JDK1.8介绍（JDK1.7）
1.HashMap的详解
- 结构：数组+链表+红黑树
- 原理：HashMap是基于hashing的原理，通过put(k,v)存储对象到HashMap中，通过get(k)方式获取对象。当使用put(k,v)传递key、value的时候，首先调用hashCode()方法，计算，bucket位置来存储Node对象。
- put(k,v)过程：
- 对key求Hash值，计算下标。
- 如果没有碰撞存入桶中，碰撞则放入bucket的链表或者红黑树中。
- 如果链表超过阈值（默认链表数超过8，总Entry数超过64）则转换为红黑树，链表长度<6则转换回链表。
- key结点存在则替换旧值。
- 如果桶满（容量*加载因子），就要resize（扩容2倍后重排）。
- get(k)过程：
- 首先将 key hash 之后取得所定位的桶。
- 如果桶为空则直接返回 null 。
- 否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key，是就直接返回 value。
- 如果第一个不匹配，则判断它的下一个是红黑树还是链表。
- 红黑树就按照树的查找方式返回值。
- 不然就按照链表的方式遍历匹配返回值。
- put(k,v)过程：
相同hashcode处理
- 优化：减少碰撞。原理是如果两个不相等的对象返回不同的 hashcode 的话，那么碰撞的几率就会小些。这就意味着存链表结构减小，这样取值的话就不会频繁调用 equal 方法，从而提高 HashMap 的性能（扰动即 Hash 方法内部的算法实现，目的是让不同对象返回不同 hashcode）。使用不可变的、声明作 final 对象，并且采用合适的 equals() 和 hashCode() 方法，将会减少碰撞的发生。
- 多线程HashMap死循环问题：因为如果两个线程都发现 HashMap 需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来。因为在resize过程中，移动到新的 bucket 位置的时候，HashMap 并不会将元素放在链表的尾部，而是放在头部，使用的是队头插入方法。这是为了避免尾部遍历（tail traversing）。如果条件竞争发生了，那么就死循环了，这也是导致CPU飙升的原因，所以多线程的环境下不使用 HashMap，而是使用concurrentHashMap。
2.LinkedHashMap的介绍
- 原理：LinkedHashMap的实现就是HashMap+LinkedList的实现方式，以HashMap维护数据结构，以LinkList的方式维护数据插入顺序。LinkedHashMap通过维护一个运行所有条目的双向链表，LinkedHashMap保证了元素的迭代顺序。迭代顺序可以是插入顺序或者是访问顺序。
3.TreeMap的介绍
- 是一个有序的key-value集合，它是通过红黑树实现的。
- 继承于AbstractMap，所以它是一个Map，即一个key-value集合。
- 实现了NavigableMap接口，意味着它支持一系列的导航方法。比如返回有序的key集合。
- 实现了Cloneable接口，意味着它能被克隆。
- 实现了java.io.Serializable接口，意味着它支持序列化。
- 基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。
- 的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。
4.HashTable与HashMap的区别
- HashTable线程安全，HashMap线程不安全。
- HashTable不可存储null值，HashMap可以存储null值。
- HashMap去掉了HashTable的contains⽅方法，但是加上了 containsValue()和containsKey()⽅方法。
5. ConcurrentHashMap的详解
put(k,v)流程：
- 如果没有初始化就调用initTable()。
- 如果hash没有冲突就直接CAS插入。
- 如果还在进行扩容就继续扩容（多线程进行）。
- 如果存在hash冲突，就加锁来保证线程安全，这里有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入。
- 插入最后一个元素如果该链表的数量大于阈值8，就要先转换成黑红树的结构，break再一次进入循环。
- 如果添加成功就调用addCount（）方法统计size，并且检查是否需要扩容。
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()); //两次hash，减少hash冲突，可以均匀分布
int binCount = 0;
for (Node<K,V>[] tab = table;;) { //对这个table进行迭代
Node<K,V> f; int n, i, fh;
//这里就是上面构造方法没有进行初始化，在这里进行判断，为null就调用initTable进行初始化，属于懒汉模式初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {//如果i位置没有数据，就直接无锁插入
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;
//如果以上条件都不满足，那就要进行加锁操作，也就是存在hash冲突，锁住链表或者红黑树的头结点
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) { //表示该节点是链表结构
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
//这里涉及到相同的key进行put就会覆盖原先的value
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) { //如果链表的长度大于8时就会进行红黑树的转换
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);//统计size，并且检查是否需要扩容
return null;
}
get(k)流程：
- 计算hash值，定位到该table索引位置，如果是首节点符合就返回。
- 如果遇到扩容的时候，会调用标志正在扩容节点ForwardingNode的find方法，查找该节点，匹配就返回。
- 以上都不符合的话，就往下遍历节点，匹配就返回，否则最后就返回null。
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode()); //计算两次hash
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {//读取首节点的Node元素
if ((eh = e.hash) == h) { //如果该节点就是首节点就返回
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//hash值为负值表示正在扩容，这个时候查的是ForwardingNode的find方法来定位到nextTable来
//查找，查找到就返回
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {//既不是首节点也不是ForwardingNode，那就往下遍历
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
