HashMap 是开发中常用的经典数据结构，在查询问题上效率极高。本文对 HashMap 的相关问题做一次总结。
JDK1.7中 HashMap 的底层结构为数组 + 链表的形式。
我们知道，数组的查询和修改速度很快，但是增加一个元素或者删除一个元素就很慢，但是链表就反过来，链表是增加和删除一个元素很快，查询和修改就很慢。而 HashMap 将两者结合起来，旨在提高查询效率。那它的工作原理是什么呢？
简单来说， HashMap 为 key : value 类型的数据结构，我们存放数据（假定为(key, value))时，调用 put 方法， HashMap 会计算 key 的 hash 值，经过某些操作计算出特定的数组索引，再将数据散列到索引处。这样就完成一次数据的存储。那链表在哪里使用呢？
当 put 方法在对不同的 key 进行 hash 操作时，可能会计算出相同的 hash 值（这时候 hash 算法的设计就尤为重要了），如果数组的索引处已经被相同 hash 值的数据占有了该怎么办呢？这时候就要用到链表了。前面提到过，链表在查询和修改数据的时候很慢，但是它在插入和删除数据的时候却很快，那么利用这个特性，我们将相同的 hash 值对应的数据装进同一个桶（bucket）中，在这个桶中形成一个链表，将它们全都链接在一起，这样就可以解决相同 hash 值的问题了。
这样一来，存放在 HashMap 中的数据就可以被高效查询了，如果冲突很少的情况下，或者说理想情况下，其时间复杂度为 O(1) ，是不是非常快？
但是问题呢，也出在这里，不然1.8为什么还要去优化 HashMap 呢？
其实在日常开发中，理想情况基本上是不存在的。如果插入的数据冲突严重，那么桶里的链表会越来越长，这样在查询时的效率就会越来越低，时间复杂度为 O(n)（链表查询的时间复杂度为 O(n) ）。
JDK1.8对HashMap的查询效率进行了大幅优化，时间复杂度可已达到 O(logn) ，而在1.7中，这个值为 O(n) 。那么JDK到底怎么优化了呢？
1.8中 HashMap 为链表长度设置了一个阈值，长度超过这个阈值的链表将会被转换为红黑树。阅读1.8的 HashMap 源码，就可以从两个核心方法 (get/put )看出 1.8 中对大链表做了优化，修改为红黑树之后查询效率直接提高到了 O(logn) 。
HashMap的遍历方式
//method 1
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());
}
//method 2
Iterator<String> iterator = map.keySet().iterator();
while (iterator.hasNext()){
String key = iterator.next();
System.out.println("key=" + key + " value=" + map.get(key));
}
建议使用第一种方法遍历 HashMap ，原因是每次遍历都可以同时拿到 Map 中的 key 和 value ，效率较高；而第二种方法只能先拿到 key ，然后再通过 key 计算 value ，效率不及第一种方法。
分析一下method1这种遍历方法：
Map接口提供了一个 entrySet() 的方法，这个方法将出现在 map 中的 mappings ，也就是 map 中所有的 Entry<K, V> 都存放在一个 Set 集合中，并最终返回这个Set集合。
我们为这个Set初始化一个泛型迭代器，迭代循环 Set 中的 Entry<K, V> ，最终取得相应的键值对。
经过优化的 HashMap 查询效率的确是高了很多，但是 HashMap 原有的问题也都存在，比如在并发场景下使用时容易出现死循环。
final HashMap<String, String> map = new HashMap<String, String>();
for (int i = 0; i < 1000; i++) {
new Thread(new Runnable() {
@Override
public void run() {
map.put(UUID.randomUUID().toString(), "");
}
}).start();
}
但是为什么呢？简单分析下。
HashMap 在扩容的时候会调用 resize() 方法，就是这里的并发操作容易在一个桶上形成环形链表；这样当获取一个不存在的 key 时，计算出的 index 正好是环形链表的下标就会出现死循环（其实链表此时成环）。
不过我觉得这不能算是Bug，因为HashMap本身就是非线程安全的，在单线程中使用它是没有任何问题的。如果要在多线程中使用和HashMap相同的功能，ConcurrentHashMap了解一下？
