@toc
1. 磨刀不误砍柴功 ：Map简介
Map 是个接口 他会有许多实现如下：
-
HashMap
基本介绍：
1. 用于存储Key-Value键值对的集合（每一个键值对也叫做一个Entry）（无顺序）。
2. 根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值。
3. 键key为null的记录至多只允许一条，值value为null的记录可以有多条。
4. 非线程安全。
5. HashMap是由数组+链表+红黑树（JDK1.8后增加了红黑树部分，链表长度超过阈值（8）时会将链表转换为红黑树）实现的。
6. HashMap与Hashtable区别：
Hashtable是synchronized的。
Hashtable不可以接受为null的键值(key)和值(value)。简单例子：
public static void main(String[] args) {
Map<String,String> map = new HashMap();
map.put("1","1");
System.out.println(map.isEmpty());
System.out.println(map.keySet());
}JDK版本 实现方式 节点数>=8 节点数<=6
1.8以前 数组+单向链表 数组+单向链表 数组+单向链表
1.8以后 数组+单向链表+红黑树 数组+红黑树 数组+单向链表
- Hastable
1. 和HashMap一样，Hashtable 也是一个散列表，它存储的内容是键值对(key-value)映射。
2. Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。
3. Hashtable 的函数都是同步的，这意味着它是线程安全的。它的key、value都不可以为null。此外，Hashtable中的映射不是有序的。很多功能他和HashMap是一致的，但是他是线程安全的
- LinkedHashMap
基础介绍
1. LinkedHashMap是HashMap的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用LinkedHashMap。
2. LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
3. LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。
注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。
- TreeMap
基础介绍
1. TreeMap 是一个有序的key-value集合，它是通过红黑树实现的。
2. TreeMap 继承于AbstractMap，所以它是一个Map，即一个key-value集合。
3. TreeMap 实现了NavigableMap接口，意味着它支持一系列的导航方法。比如返回有序的key集合。
4. TreeMap 实现了Cloneable接口，意味着它能被克隆。
5. TreeMap 实现了java.io.Serializable接口，意味着它支持序列化。
6. TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。
7. TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。
另外，TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。2. 为什么需要ConcurrentHashMap
1.我们先思考一个问题，我们为什么要用ConcurrentHashMap,而不用Collections.synchronizedMap() 或者 Hashtable
: 加了锁对我们性能造成很大的影响
- 为什么HashMap是线程不安全的呢？
: 同时put碰撞导致数据丢失
: 同时put扩容导致数据丢失
: 死循环造成CPU100%
3. 九层之台，起于累土，罗马不是一天建成的：HashMap分析
- HashMap是应用更广泛的哈希表实现，而且大部分情况下，都能在常数时间性能的情况下进行put和get操作。要掌握HashMap，主要从如下几点来把握：
- jdk1.7中底层是由数组（也有叫做“位桶”的）+链表实现；jdk1.8中底层是由数组+链表/红黑树实现
- 可以存储null键和null值，线程不安全 初始size为16，扩容：newsize = oldsize*2，size一定为2的n次幂
- 扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入
- 插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容）
- 当Map中元素总数超过Entry数组的75%，触发扩容操作，为了减少链表长度，元素分配更均匀
1.7 实现图
1.8实现图
延伸：红黑树
- [ ] 他是一个二叉查找数，一种平衡策略
- [ ] 左边的值要比这个节点要小，右边则大
- [ ] 会自动平衡，防止极端不平衡从而影响查找效率的情况发生
- [ ] 每个节点要们是红色，要么是黑色，但跟节点永远是黑色
- [ ] 红色节点不能连续
- [ ] 从任一节点到其子数中每个叶子节点的路径都包含相同数量的黑色节点
- [ ] 所有的叶节点都是黑色的
4. JDK1.7 中 ConcurrentHashMap 实现和分析
1.7 数据结构
1.7 的特点
- Java 1.7 中ConcurrentHashMap最外层是多个segment，每个segment底层数据结构与HashMap类似，ren仍然是数组+链表的 拉链法
- 每个segment独立ReentrantLock，每个segment 互不影响，提高链并发效率
- ConcurrentHashMap 有16个 segment，所以同时支持 16个线程并发写，这个默认值可以在初始化的时候设置为其他值，但是一旦初始化后，是不可以扩容的
5. JDK1.8 中 ConcurrentHashMap 实现和源码分析
数据结构
ConcurrentHashMap 借鉴链 1.8 HashMap 实现
源码分析
- put
/**
* 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);
}putVal 是 put 方法和核心
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 不允许key value 出现 空否则 抛出空指针异常
if (key == null || value == null) throw new NullPointerException();
//计算hashcode值
int hash = spread(key.hashCode());
int binCount = 0;
// 用for循环进行处理 完成值的插入工作
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//判断 tab 是否初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//已经被初始化 并且在这个位置是空的 执行cas操作直接放进去
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//cas操作把值放进去
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// 判断hash值是否 MOVED MOVED代表扩容
else if ((fh = f.hash) == MOVED)
//帮助进行扩容
tab = helpTransfer(tab, f);
else {
V oldVal = null;
//否则使用synchronized保证值线程的安全
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
//进行链表的操作
for (Node<K,V> e = f;; ++binCount) {
K ek;
//判断当前是否存在key
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;
}- get
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code key.equals(k)},
* then this method returns {@code v}; otherwise it returns
* {@code null}. (There can be at most one such mapping.)
*
* @throws NullPointerException if the specified key is null
*/
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
//算出hash值
int h = spread(key.hashCode());
//判断值
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
//如果槽点的hash值符合 返回val 找到值了
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// 如果是负数，说明是红黑树节点，
else if (eh < 0)
//用find方法找到对应的value
return (p = e.find(h, key)) != null ? p.val : null;
// 遍历链表 找到值返回
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
6. 对比1.7 与 1.8 ，为什么要把1.7的结构改成1.8的结构
- 数据结构的区别
- Java 1.7 中ConcurrentHashMap最外层是多个segment，每个segment底层数据结构与HashMap类似 最多 16个
- Java 1.8 使用 数组+链表+红黑树的结构 每个 Node，提高了并发性
- hash碰撞
- 转变为 数组 + 链表 + 红黑树
- 保证并发安全
- java1.8 通过 cas + synchronized 实现
个人博客地址：http://blog.yanxiaolong.cn/