java集合——Map

Map不由Collection接口派生，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个 value。与Map接口相关的部分UML类图如下：

其具体实现类主要有：HashMap、LinkedHashMap、TreeMap、HashTable。

HashMap

1、允许null键/值。
2、非线程安全。
3、不保证有序(比如插入的顺序)、也不保证序不随时间变化。

LinkedHashMap

1、LinkedHashMap是基于HashMap实现的，它继承了HashMap。
2、内部节点是双向的，从而保证了迭代顺序是插入的顺序；如果accessOrder为true，则维护了最近访问的顺序。
3、LinkedHashMap会在节点插入、节点访问、节点移除后做一些事情，即更新链表，把最近访问的放到最后。

TreeMap

1、通过Comparator对象，来保持我们想要维护的key的大小顺序。
2、使用平衡二叉树——红黑树来存储元素，红黑树的特性决定了它的查询、插入、删除操作的时间复杂度均为O(log n)。

HashTable

1、Hashtable不允许key或者value使用null值。
2、Hashtable的大部分方法做了同步，因此是线程安全的。
3、key的hash算法以及index的计算方法跟HashMap不同。

同步问题

1、HashMap、LinkedHashMap、TreeMap都是非线程安全的，如果在多线程中使用，可以通过 Collections.synchronizedMap(Map<K,V> m) 来实现线程安全，其内部是通过 synchronized 关键字来修饰方法来达到同步的目的。

2、HashMap 提供了对应的 ConcurrentHashMap 这个线程安全的类，重要通过以下三个方面来达到高并发的目的（参考）：

1、用分离锁实现多个线程间的更深层次的共享访问。

• 在 ConcurrentHashMap 中，线程对映射表做读操作时，一般情况下不需要加锁就可以完成，对容器做结构性修改的操作才需要加锁。

• 使用 Segment 类（继承于 ReentrantLock 类），加锁操作是针对（键的 hash 值对应的）某个具体的 Segment，锁定的是该 Segment 而不是整个 ConcurrentHashMap。因为插入键 / 值对操作只是在这个 Segment 包含的某个桶中完成，不需要锁定整个ConcurrentHashMap。此时，其他写线程对另外 15 个Segment 的加锁并不会因为当前线程对这个 Segment 的加锁而阻塞。同时，所有读线程几乎不会因本线程的加锁而阻塞（除非读线程刚好读到这个 Segment 中某个 HashEntry 的 value 域的值为 null，此时需要加锁后重新读取该值）。

2、用 HashEntery 对象的不变性来降低执行读操作的线程在遍历链表期间对加锁的需求。

3、通过对同一个 Volatile 变量的写 / 读访问，协调不同线程间读 / 写操作的内存可见性。（在 value 字段添加 volatile 修饰符）

通过减小请求同一个锁的频率和尽量减少持有锁的时间 ，使得 ConcurrentHashMap 的并发性相对于 HashTable 和用同步包装器包装的 HashMap有了质的提高，so，优先使用 ConcurrentHashMap。