JAVA中的Map

HashMap

HashMap类在之前的文章有较为详细的介绍，作为最常用的Map数据结构，了解HashMap也是了解JAVA中其他Map的基础。

HashTable

HashTable是一个遗留类，现较少使用。使用单线程使用Map结构一般使用HashMap，多线程则使用ConcurrencyHashMap。不过可以通过了解HashTable了解到为什么它被淘汰以及对在并发编程中线程安全与效率的安全性的进步。
下面从HashTable与HashMap的对比了解HashTable。

线程安全
HashMap是线程不安全的类，多线程下会造成并发冲突，但单线程下运行效率较高；HashTable是线程安全的类，但很多方法都是用synchronized修饰，因此导致并发效率低下，单线程环境效率也十分低。
null值
HashMap允许有一个键为null，允许多个值为null；但HashTable不允许键或值为null。
容量
HashMap底层数组长度必须为2的幂，这样做是为了hash准备，默认为16；而HashTable底层数组长度可以为任意值，这就造成了hash算法散射不均匀，容易造成hash冲突，默认为11。
哈希算法
在对HashMap的介绍中认识到，HashMap由于有“容量为2的n次幂”的前提，哈希算法得以通过使用位与运算代替取模运算，减少运算消耗；而HashTable的哈希算法取得哈希值后，再通过对容量取模得到下标，使用取模运算无疑使性能下降。
扩容
HashMap（1.8）创建一个为原先2倍的数组，然后对原数组进行遍历以及rehash（扩容的rehash计算代价很小），用尾插法拷贝旧链表到新链表；HashTable扩容则和将创建一个原长度2倍的数组，对原数组遍历及rehash（计算代价比HashMap大）后，使用头插法拷贝旧链表，会导致拷贝后的链表反序。
为什么HashMap1.8扩容后的rehash计算代价小？同样可参考之前的文章。
使用数据结构
HashMap（1.8）是由数组+链表+红黑树形成。HashTable一直都是数组+链表。

总结：HashTable线程安全，初始容量11，扩容容量*2，使用数组+链表。效率低，原因有：频繁加锁、容量任意导致容易冲突、哈希算法取模开销大。

ConcurrentHashMap

ConcurrentHashMap最大的特点就是它是一个线程安全的Map，且效率比同为线程安全的HashTable高，在目前多线程使用Map的情况下一般会选用。

HashTable和ConcurrentHashMap

之所以ConcurrentHashMap的效率更高，是因为ConcurrentHashMap将数组分成了不同的Segment（段），在并发访问Map时，HashTable会将整个Map加锁，而ConcurrentHashMap则只会对数据所对应的段加锁。ConcurrentHashMap的段时这样定义的：
图片说明
可以看到与HashTable不同的是ConcurrentHashMap将数组分为16个段（默认值，可以初始化时显式指定，后期无法更改），每个Segment里面可以近似看成一个HashMap，每个Segment块都有自己独立的ReentrantLock锁，所以并发操作时每个Segment互不影响。因此锁的粒度降低了，提高了并发度。同时多线程读时不会阻塞，因此效率大大提高。

ConcurrentHashMap 1.7与1.8的区别

在上文对ConcurrentHashMap与HashTable的比较中我们对ConcurrentHashMap已经有一定了解并且知道为什么它能够取缔HashTable。下面继续介绍ConcurrentHashMap中1.7与1.8的区别。

数据结构

1.7中使用数组+链表，1.8使用数组+链表+红黑树。这点和HashMap相似。好处是降低了查询复杂度（O(n)->O(logn)）

锁的粒度

1.7使用了segment粒度加锁，每个segment内是一个小的HashMap。1.8进一步降低锁的粒度，实现Node粒度的锁。简单理解即1.7的segment锁会锁数组中的多个元素，而1.8的锁直接锁的就是数组的一个元素。因此并发度进一步提高。

同步的实现

1.7使用ReentrantLock+Segment方式实现同步，1.8则使用synchronized +CAS 方式实现。原因有下：

因为粒度降低了，在相对而言的低粒度加锁方式，synchronized并不比ReentrantLock差。在粗粒度加锁中ReentrantLock可能通过Condition来定义各个低粒度的边界，使得锁粒度更细、更加灵活。而在本身就是低粒度的加锁中，Condition的优势没有了。
基于JVM的synchronized优化空间更大，使用内嵌的关键字比使用API更加自然。
在大量的数据操作下，对于JVM的内存压力，基于API的ReentrantLock会开销更多的内存。

ConcurrentHashMap源码解析（1.8）

put方法工作过程

key-value的检验，不允许为空，否则抛出异常；
用while(true)无限重试put动作，直到put成功；
如果数组没有初始化过则先进行初始化工作；
如果数组中该hashcode对应位置不存在元素，则将该元素以CAS方式放入，对应的casTabAt()方法；
如果数组中存在元素，用synchronized块保证同步操作，循环判断链表中是否存在该value，存在则返回oldValue，不存在则插入链表末端，put成功跳出循环；
如果是红黑树，则将元素放入红黑树节点中；
put完成后根据链表长度是否大于8且数组长度是否大于64来判断是否将链表转换成红黑树；
返回oldValue值；

// ConcurrentHashMap.put()
public V put(K var1, V var2) {
        return this.putVal(var1, var2, false);
    }

    final V putVal(K var1, V var2, boolean var3) {
        if (var1 != null && var2 != null) {
            int var4 = spread(var1.hashCode());
            int var5 = 0;
            ConcurrentHashMap.Node[] var6 = this.table;

            while(true) {
                int var8;
                while(var6 == null || (var8 = var6.length) == 0) {
                    var6 = this.initTable();
                }

                ConcurrentHashMap.Node var7;
                int var9;
                if ((var7 = tabAt(var6, var9 = var8 - 1 & var4)) == null) {
                    if (casTabAt(var6, var9, (ConcurrentHashMap.Node)null, new ConcurrentHashMap.Node(var4, var1, var2, (ConcurrentHashMap.Node)null))) {
                        break;
                    }
                } else {
                    int var10 = var7.hash;
                    if (var7.hash == -1) {
                        var6 = this.helpTransfer(var6, var7);
                    } else {
                        Object var11 = null;
                        synchronized(var7) {
                            if (tabAt(var6, var9) == var7) {
                                if (var10 < 0) {
                                    if (var7 instanceof ConcurrentHashMap.TreeBin) {
                                        var5 = 2;
                                        ConcurrentHashMap.TreeNode var18;
                                        if ((var18 = ((ConcurrentHashMap.TreeBin)var7).putTreeVal(var4, var1, var2)) != null) {
                                            var11 = var18.val;
                                            if (!var3) {
                                                var18.val = var2;
                                            }
                                        }
                                    }
                                } else {
                                    var5 = 1;
                                    ConcurrentHashMap.Node var13 = var7;

                                    while(true) {
                                        if (var13.hash == var4) {
                                            Object var14 = var13.key;
                                            if (var13.key == var1 || var14 != null && var1.equals(var14)) {
                                                var11 = var13.val;
                                                if (!var3) {
                                                    var13.val = var2;
                                                }
                                                break;
                                            }
                                        }

                                        ConcurrentHashMap.Node var15 = var13;
                                        if ((var13 = var13.next) == null) {
                                            var15.next = new ConcurrentHashMap.Node(var4, var1, var2, (ConcurrentHashMap.Node)null);
                                            break;
                                        }

                                        ++var5;
                                    }
                                }
                            }
                        }

                        if (var5 != 0) {
                            if (var5 >= 8) {
                                this.treeifyBin(var6, var9);
                            }

                            if (var11 != null) {
                                return var11;
                            }
                            break;
                        }
                    }
                }
            }

            this.addCount(1L, var5);
            return null;
        } else {
            throw new NullPointerException();
        }
    }

get()方法

判断数组是否为空，为空直接返回null；
根据hash值查找，如果hash值相等且key也相等，则直接返回value值；
如果key的hash值小于0，说明是红黑树，则进入红黑树查找到该节点值；

否则进入循环链表读取该value值并返回；

//ConcurrentHashMap.get()
 public V get(Object var1) {
     int var8 = spread(var1.hashCode());
     ConcurrentHashMap.Node[] var2 = this.table;
     ConcurrentHashMap.Node var3;
     int var5;
     if (this.table != null && (var5 = var2.length) > 0 && (var3 = tabAt(var2, var5 - 1 & var8)) != null) {
         int var6 = var3.hash;
         Object var7;
         if (var3.hash == var8) {
             var7 = var3.key;
             if (var3.key == var1 || var7 != null && var1.equals(var7)) {
                 return var3.val;
             }
         } else if (var6 < 0) {
             ConcurrentHashMap.Node var4;
             return (var4 = var3.find(var8, var1)) != null ? var4.val : null;
         }
         while((var3 = var3.next) != null) {
             if (var3.hash == var8) {
                 var7 = var3.key;
                 if (var3.key == var1 || var7 != null && var1.equals(var7)) {
                     return var3.val;
                 }
             }
         }
     }
     return null;
}

LinkedHashMap

LinkedHashMap继承自HashMap，在HashMap基础上，通过维护一条双向链表，解决了HashMap不能随时保持遍历顺序和插入顺序一致的问题。在实现上，LinkedHashMap 很多方法直接继承自 HashMap，底层仍然是基于数组+链表+红黑树组成，仅为维护双向链表重写了部分方法。
总结：当我们希望有顺序地（按照插入的顺序）去存储key-value时，就需要使用LinkedHashMap了。

TreeMap

TreeMap也是存储键值对，但它不是以哈希的方法进行存储了。它通过维护一个红黑树的数据结构，实现有序地存储键值对。TreeMap可以对元素的排序方式，可以按照默认的排序方式，也可以自己指定排序方式。
指定自定义的排序方式方法如下：

要自定义排序的类（也就是存储到TreeMap中的key的类）实现java.lang.Comparable接口，实现其compareTo()方法，从而自定义key之间的大小关系。
写一个比较器类（如MyCompatator）实现java.util.Comparator接口，并实现compare()方法，然后将MyCompatator类实例对象作为TreeMap的构造方法参数进行传参。
总结：TreeMap即有Map的特性，即根据key检索value，也能实现键值对的有序存储。具体的使用可以参考此链接。

collections.synchronizedMap代理类

collections.synchronizedMap对传入的Map进行包装后，返回一个线程安全的Map。因此它是一个实现了Map接口的代理类（从JDK动态代理中我们了解了代理模式）。可以从下面源码中了解到它的实现方式是对Map接口中的方法使用synchronized包装，以保证对被代理的Map的操作是线程安全的。

private static class SynchronizedMap<K,V>
    implements Map<K,V>, Serializable {
    // use serialVersionUID from JDK 1.2.2 for interoperability
    private static final long serialVersionUID = 1978198479659022715L;

    private final Map<K,V> m;     // Backing Map
        final Object      mutex;    // Object on which to synchronize

    SynchronizedMap(Map<K,V> m) {
            if (m==null)
                throw new NullPointerException();
            this.m = m;
            mutex = this;
        }

    SynchronizedMap(Map<K,V> m, Object mutex) {
            this.m = m;
            this.mutex = mutex;
        }

    public int size() {
        synchronized(mutex) {return m.size();}
        }
    public boolean isEmpty(){
        synchronized(mutex) {return m.isEmpty();}
        }
    public boolean containsKey(Object key) {
        synchronized(mutex) {return m.containsKey(key);}
        }
    public boolean containsValue(Object value){
        synchronized(mutex) {return m.containsValue(value);}
        }
    public V get(Object key) {
        synchronized(mutex) {return m.get(key);}
        }

    public V put(K key, V value) {
        synchronized(mutex) {return m.put(key, value);}
        }
    public V remove(Object key) {
        synchronized(mutex) {return m.remove(key);}
        }
    public void putAll(Map<? extends K, ? extends V> map) {
        synchronized(mutex) {m.putAll(map);}
        }
    public void clear() {
        synchronized(mutex) {m.clear();}
    }

    private transient Set<K> keySet = null;
    private transient Set<Map.Entry<K,V>> entrySet = null;
    private transient Collection<V> values = null;

    public Set<K> keySet() {
            synchronized(mutex) {
                if (keySet==null)
                    keySet = new SynchronizedSet<K>(m.keySet(), mutex);
                return keySet;
            }
    }

    public Set<Map.Entry<K,V>> entrySet() {
            synchronized(mutex) {
                if (entrySet==null)
                    entrySet = new SynchronizedSet<Map.Entry<K,V>>(m.entrySet(), mutex);
                return entrySet;
            }
    }

    public Collection<V> values() {
            synchronized(mutex) {
                if (values==null)
                    values = new SynchronizedCollection<V>(m.values(), mutex);
                return values;
            }
        }

    public boolean equals(Object o) {
            if (this == o)
                return true;
            synchronized(mutex) {return m.equals(o);}
        }
    public int hashCode() {
            synchronized(mutex) {return m.hashCode();}
        }
    public String toString() {
        synchronized(mutex) {return m.toString();}
        }
        private void writeObject(ObjectOutputStream s) throws IOException {
        synchronized(mutex) {s.defaultWriteObject();}
        }
    }

结合上述源码，回过头思考在JDK动态代理一文中说到的代理模式，collections.synchronizedMap正是一种静态代理。从代理模式的角度来说，它与被代理对象（即传入的Map对象）同时实现了Map接口，在代理类重写Map中方法中，以put()为例，用synchronized包装被代理对象实现的put()方法，从而通过这种方式使线程不安全被代理类在使用代理后，变得线程安全。