HashMap 相关问题总结
1. 基本概念
1.1 HashMap：
HashMap是一个实现了Map接口的基于哈希表的类。
查找时，给出一个关键字key，我们可以根据hash算法计算出key-value的存储位置然后取出value。
存储时，我们根据哈希算法计算出该键值对应该存储的位置，将其存进去。
HashMap是以键值对的形式存储和操作数据的容器类型。插入和查询“键值对”的开销是固定的，可以通过构造器设置容量和加载因子，以调整容器性能。
推介加载因子为0.75，0.75是一个折中选择后的推介值，能解决大多数场景问题。
1.2 HashTable：
HashTable是线程安全的，用了synchronized限制了每个方法，并且Key和Value都不能是Null。其它和HashMap没什么差别。
1.3 LinkHashMap：
LinkHashMap 类似HashMap，但是迭代遍历他的时候，取得“键值对”的顺序是其插入的顺序，可以理解为“桶结构” 。
速度比hashMap慢一点，而迭代的访问速度反而更快，用链表来维护内部数据。
LinkedHashMap是HashMap的子类，意味着它继承了HashMap的特性。
除此之外，LinkedHashMap还保存了插入顺序。
1.4 TreeMap：
TreeMap则是基于红黑树的一种提供顺序访问的Map。
和HashMap不同，它的get、put、remove之类操作都是O（log(n)）的时间复杂度，具体顺序可以由指定 的Comparator来决定（String对象已经实现Comparator），或者根据键的自然顺序来判断。
TreeMap得到的结果都经过排序的。
TreeMap是Map中唯一一个带有subMap（）方法的Map，它可以返回一个子树。
1.5 ConcurrentHashMap：
2. HashMap、HashTable和ConcurrentHashMap的线程安全问题
| 类型 | 安全问题 |
|---|---|
| HashMap | 线程不安全的 |
| HashTable | 锁住整张hash表，让线程独占。hashMap允许为空。通过分析Hashtable就知道，synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，安全的背后是巨大的资源浪费 |
| ConcurrentHashMap | 一个更快的hashmap，它提供了好得多的并发性。多个读操作几乎总可以并发地执行。他是锁段（默认：把hash表分为16个段），在get，put，remove等操作中，ConcurrentHashMap只锁定当前需要用到的段，只有在求size的时候才锁定整张hash表。 |