1. Map

Map 是一个用于保存键值对(key-value)的接口。Map 中不能包含重复的键；每个键最多只能映射到一个值。

HashMap

#

put 方法大致的思路为：​

• 对 key 的 hashCode() 做 hash 计算，然后根据 hash 值再计算 Node 的存储位置;​

• 如果没有哈希碰撞，直接放到桶里；如果有哈希碰撞，以链表的形式存在桶后。​

• 如果哈希碰撞导致链表过长(大于等于 TREEIFY_THRESHOLD，数值为 8）并且满足容量大于等于64，就把链表转换成红黑树（“链表树化”是Java8开始做的优化）；如果容量不满足大于等于64的条件，那就触发扩容，扩容会将原来为8的链表节点分散开，缩短链表长度。

Java8: 数据结构采用（数组+链表+红黑树）实现。

线程安全

• 死循环​
• 数据丢失

Hashtable

#

HashTable基于Dictionary类，而HashMap是基于AbstractMap。Dictionary是任何可以键映射到相应值的类的抽象类，而AbstractMap是基于Map接口的实现，它以减少实现此接口所需的工作。​

HashMap 的 key 和 value 都允许为 null，而 Hashtable 的 key 和 value 都不允许为 null。HashMap 遇到 key 为 null 的时候，调用 putForNullKey 方法进行处理，而对 value 没有处理；Hashtable 遇到 null，直接返回 NullPointerException。​

HashTable是同步的，而HashMap则不是。我们可以看一下源码，HashTable中的几乎所有公共的方法都是synchronized的，而有些方法也是在内部通过synchronized代码来实现的。所以有人一般都建议如果在多线程同步时使用HashTable，而不涉及就使用HashMap

TreeMap

#

• TreeMap 是有序的。它的排序规则是：根据 map 中的 key 的自然语义顺序或提供的比较器（Comparator）的自定义比较顺序。​

• TreeMap 不是线程安全的。​

• TreeMap底层通过红黑树(Red-Black tree)实现，也就意味着containsKey(), get(), put(), remove()都有着log(n)的时间复杂度。

LinkedHashMap ​

#

HashMap 本身并不保证键值对的顺序，如果我们需要按照插入顺序或访问顺序来遍历键值对，就需要使用 LinkedHashMap 了。

LinkedHashMap 通过维护一对 LinkedHashMap.Entry<K,V> 类型的头尾指针，以双链表形式，保存所有数据。