Java Map

Java Map一共有5个类实现，分别是：HashMap、ConcurrentHashMap、HashTable、TreeMap和LinkedHashMap。

1．HashMap：数组+链表存储数据，线程不安全
HashMap基于键的HashCode值唯一标识一条数据，同时基于键的HashCode值进行数据的存取，因此可以快速地更新和查询数据，但其每次遍历的顺序无法保证相同。HashMap的key和value允许为null。

HashMap是非线程安全的，即在同一时刻有多个线程同时写HashMap时将可能导致数据的不一致。如果需要满足线程安全的条件，则可以用Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

HashMap的数据结构如下图所示，其内部是一个数组，数组中的每个元素都是一个单向链表，链表中的每个元素都是嵌套类Entry的实例，Entry实例包含4个属性：key、value、hash值和用于指向单向链表下一个元素的next。

HashMap常用的参数如下:

• capacity：当前数组的容量，默认为16，可以扩容，扩容后数组的大小为当前的两倍，因此该值始终为2ⁿ。
• loadFactor：负载因子，默认为0.75。
• threshold：扩容的阈值，其值等于capacity×loadFactor。

HashMap在查找数据时，根据HashMap的Hash值可以快速定位到数组的具体下标，但是在找到数组下标后需要对链表进行顺序遍历直到找到需要的数据，时间复杂度为O(n)。

为了减少链表遍历的开销，Java 8对HashMap进行了优化，将数据结构修改为数组+链表或红黑树。在链表中的元素超过8个以后，HashMap会将链表结构转换为红黑树结构以提高查询效率，因此其时间复杂度为O(log N)。Java 8 HashMap的数据结构如图所示:

2．ConcurrentHashMap：分段锁实现，线程安全
与HashMap不同，ConcurrentHashMap采用分段锁的思想实现并发操作，因此是线程安全的。ConcurrentHashMap由多个Segment组成（Segment的数量也是锁的并发度），每个Segment均继承自ReentrantLock并单独加锁，所以每次进行加锁操作时锁住的都是一个Segment，这样只要保证每个Segment都是线程安全的，也就实现了全局的线程安全。ConcurrentHashMap的数据结构如图所示:

在ConcurrentHashMap中有个concurrencyLevel参数表示并行级别，默认是16，也就是说ConcurrentHashMap默认由16个Segments组成，在这种情况下最多同时支持16个线程并发执行写操作，只要它们的操作分布在不同的Segment上即可。并行级别concurrencyLevel可以在初始化时设置，一旦初始化就不可更改。ConcurrentHashMap的每个Segment内部的数据结构都和HashMap相同。

Java 8在ConcurrentHashMap中引入了红黑树，具体的数据结构如图所示:

3．HashTable：线程安全
HashTable是遗留类，很多映射的常用功能都与HashMap类似，不同的是它继承自Dictionary类，并且是线程安全的，同一时刻只有一个线程能写HashTable，并发性不如ConcurrentHashMap。

4．TreeMap：基于二叉树数据结构
TreeMap基于二叉树数据结构存储数据，同时实现了SortedMap接口以保障元素的顺序存取，默认按键值的升序排序，也可以自定义排序比较器。

TreeMap常用于实现排序的映射列表。在使用TreeMap时其key必须实现Comparable接口或采用自定义的比较器，否则会抛出java.lang.ClassCastException异常。

5．LinkedHashMap：基于HashTable数据结构，使用链表保存插入顺序
LinkedHashMap为HashMap的子类，其内部使用链表保存元素的插入顺序，在通过Iterator遍历LinkedHashMap时，会按照元素的插入顺序访问元素。