浅谈java 之 Map

先来一张Map的类继承图

Map ：Hashtable 、HashMap 、LinkedHashMap 、TreeMap 的比较  

1、Hashtable的方法实现了synchronized 是线程安全的，而HashMap没有，所以相对来多效率高

2、Hashtable 不允许key或value为null

3、LinkedzHashMap 是继承HashMap ,但是LinkedHashMa是有顺序的

4、LinkedHashMap是基于进入的顺序排序的，TreeMap 是按照固有顺序排序的（按照Key的类的compareTo 定义的顺序）HashMap是线程不安全的。

要实现线程安全有两种方式：

1） 使用ConcurrentHashMap      高性能的并发容器

2） 使用public static Map m=Collections.synchronizedMap(new HashMap());  

Collections.synchronizedMap是将HashMap的方法加了synchronized ，但是但是大数量并发时会很影响性能。

hashMap的简单介绍：

HashMap也是我们使用非常多的Collection，它是基于哈希表的 Map 接口的实现，以key-value的形式存在。在HashMap中，key-value总是会当做一个整体来处理，系统会根据hash算法来来计算key-value的存储位置，我们总是可以通过key快速地存、取value。HashMap是一个“链表散列”，底层实现是数组，只是数组的每一项都是一条链，它的数据结构如下：

HashMap保存数据的过程为：首先判断key是否为null，若为null，则直接调用putForNullKey方法。若不为空则先计算key的hash值，先计算key的hash值，然后根据hash值搜索在table数组中的索引位置，如果table数组在该位置处有元素，则通过比较是否存在相同的key，若存在则覆盖原来key的value，否则将该元素保存在链头（最先保存的元素放在链尾）。若table在该处没有元素，则直接保存。

接下来谈谈ConcurrentHashMap

首先看看为什么使用ConcurrentHashMap

1. HashMap在高并发的环境下，执行put操作会导致HashMap的Entry链表形成环形数据结构，从而导致Entry的next节点始终不为空，因此产生死循环获取Entry

2. HashTable虽然是线程安全的，但是效率低下，当一个线程访问HashTable的同步方法时，其他线程如果也访问HashTable的同步方法，那么会进入阻塞或者轮训状态。

在jdk1.6中ConcurrentHashMap使用锁分段技术提高并发访问效率。首先将数据分成一段一段地存储，然后给每一段数据配一个锁，当一个线程占用锁访问其中一段数据时，其他段的数据也能被其他线程访问。然而在jdk1.8中的实现已经抛弃了Segment分段锁机制，利用CAS+Synchronized来保证并发更新的安全，底层依然采用数组+链表+红黑树的存储结构。

JDK1.8分析

首先看看为什么使用ConcurrentHashMap

改进一：取消segments字段，直接采用transient volatile HashEntry<K,V> table来保存数据，采用table数组元素作为锁，从而使实现了对每一行数据进行加锁，进一步减少并发冲突的概率。

改进二：将原先table数组+单向链表的数据结构，变更为table数组+单向链表+红黑树的结构。对于hash表来说，最核心的能力在于将key hash之后能均与的分布在数组中。如果hash之后散列的很均匀，那么table数组中的每个队列长度主要为0或者1。但实际过程中还是会存在一些队列长度过长的情况，如果还是采用单向列表的方式，那么查询某个节点的时间复杂度为O(n)；因此，对于个数超过8（默认值）的列表，jdk1.8中采用了红黑树的结构，查询的时间复杂度可以降低到O(logN),可以改进性能。