写在前面
jdk1.7-jdk1.8hashmap变化：
TREEIFY_THRESHOLD 用于判断是否需要将链表转换为红黑树的阈值。（默认8）
HashEntry 修改为 Node。
node（Entry）数据结构
hash 存放的是当前 key 的 hashcode。
key 就是写入时的键。
value 自然就是值。
开始的时候就提到 HashMap 是由数组和链表组成，所以这个 next 就是用于实现链表结构。
HashMap阅读
hashmap常见问题
1. 谈谈你理解的 HashMap，讲讲其中的 get put 过程。
2. 1.8 做了什么优化？
3. 是线程安全的嘛？
4. 不安全会导致哪些问题？
5. 如何解决？有没有线程安全的并发容器？
6. ConcurrentHashMap 是如何实现的？ 1.7、1.8 实现有何不同？为什么这么做？
开始解毒
HashMap的get put 过程。
HashMap 底层是基于 数组 + 链表 组成的，不过在 jdk1.7 和 1.8 中具体实现稍有不同。
这里只讲1.8的过程：
JDK1.8-put过程
过程解毒：
1. 判断当前桶(node[])是否为空，空的就需要初始化（resize 中会判断是否进行初始化）。
2. 根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空，为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。
3. 如果当前桶有值（ Hash 冲突），那么就要比较当前桶中的 key、key 的 hashcode 与写入的 key 是否相等，相等就赋值给 e(Node<K,V> e),在第 8 步的时候会统一进行赋值及返回
4. 如果当前桶为红黑树，那就要按照红黑树的方式写入数据。
5. 如果是个链表，就需要将当前的 key、value 封装成一个新节点写入到当前桶的后面（形成链表）。
6. 接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。
7. 如果在遍历过程中找到 key 相同时直接退出遍历。
8. 如果 e != null 就相当于存在相同的 key,那就需要将值覆盖。
9. 最后判断是否需要进行扩容。
JDK1.8-get过程
1. 首先根据key算出hash值之后取得所定位的桶。
2. 如果桶为空则直接返回 null 。
3. 否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key，是就直接返回 value。
4. 如果第一个不匹配，则判断它的下一个是红黑树还是链表。
5. 红黑树就按照树的查找方式返回值。
6. 不然就按照链表的方式遍历匹配返回值。
JDK1.8 做了什么优化？
从这两个核心方法（get/put）可以看出 1.8 中对大链表做了优化，修改为红黑树之后查询效率直接提高到了 O(logn)。
是线程安全的嘛？
hashMap不是线程安全的；concurrentHashMap是线程安全的
不安全会导致哪些问题？
线程不安全在并发场景下使用时容易出现死循环。HashMap 扩容的时候会调用 resize() 方法，就是这里的并发操作容易在一个桶上形成环形链表；这样当获取一个不存在的 key 时，计算出的 index 正好是环形链表的下标就会出现死循环。
如何解决？有没有线程安全的并发容器？
1.ConCurrentHashMap 来替代同步的HashMap 实现
2.CopyOnWriteArrayList 是List的同步实现
3.Queue 和 BlockQueue 接口
4.ConCurrentLinkedQueue 一个并发优先级的队列注意： java6中加入ConCurrentSkipListMap 和 ConCurrentSkipListSet 用来作为同步的SortedMap 和SortedSet ..
ConcurrentHashMap 实现
1.7、1.8 实现有所不同。
Base 1.7
数据结构：
ConcurrentHashMap 和 HashMap 非常类似，唯一的区别就是其中的核心数据如 value ，以及链表都是 volatile 修饰的，保证了获取时的可见性。
原理上来说：ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。
1.7put过程：
- 将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。
- 遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value。
- 不为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。
- 最后会解除在 1 中所获取当前 Segment 的锁。
1.7get过程：
只需要将 Key 通过 Hash 之后定位到具体的 Segment ，再通过一次 Hash 定位到具体的元素上。由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值。ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。
ps：1.7 已经解决了并发问题，并且能支持 N 个 Segment 这么多次数的并发，但依然存在 HashMap 在 1.7 版本中的问题。那就是查询遍历链表效率太低。
Base 1.8
与hashMap1.8结构相似，其中抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。
也将 1.7 中存放数据的 HashEntry 改为 Node，但作用都是相同的。其中的 val和next 都用了 volatile 修饰，保证了可见性。
JDK1.8之后的改进：
1.链表改成了红黑树，当链表中的结点达到一个阀值TREEIFY_THRESHOLD时，会将链表转换为红黑树，查询效率提从原来的O(n)，提高为O(logn)
2.将每个segment的分段锁ReentrantLock改为CAS+Synchronized
1.8put过程：
1. 根据 key 计算出 hashcode 。
2. 判断是否需要进行初始化。
3. f 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
4. 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
5. 如果都不满足，则利用 synchronized 锁写入数据。
6. 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。
1.8get过程：
1. 根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
2. 如果是红黑树那就按照树的方式获取值。
3. 就不满足那就按照链表的方式遍历获取值。
1.8 在 1.7 的数据结构上做了大的改动，采用红黑树之后可以保证查询效率（O(logn)），甚至取消了 ReentrantLock 改为了 synchronized，这样可以看出在新版的 JDK 中对 synchronized 优化是很到位的。
总结
HashMap 的遍历方式，通常有以下几种：
Iterator<Map.Entry<String, Integer>> entryIterator = map.entrySet().iterator(); while (entryIterator.hasNext()) { Map.Entry<String, Integer> next = entryIterator.next(); System.out.println("key=" + next.getKey() + " value=" + next.getValue()); } Iterator<String> iterator = map.keySet().iterator(); while (iterator.hasNext()){ String key = iterator.next(); System.out.println("key=" + key + " value=" + map.get(key)); }
强烈建议使用第一种 EntrySet 进行遍历。
第一种可以把 key value 同时取出，第二种还得需要通过 key 取一次 value，效率较低。
简单总结下 HashMap：无论是 1.7 还是 1.8 其实都能看出 JDK 没有对它做任何的同步操作，所以并发会出问题，甚至出现死循环导致系统不可用。
（完）