java中有各种类型的map，每种类型的map实现方式不同，但接口都类似。所有的具体map类型必须实现Map接口或者其子类，AbstractMap实现了Map接口，并实现了Map接口的部分功能，因此一般具体Map类型只需继承AbstractMap就可以了。

1. HashMap

HashMap的实现方式是一个table数组，数组元素是一个Entry类型（java8 中是Node类型，Entry变成了一个接口)，Entry是一个内部类，类似c++的pair类型，b实际保存key 和value值，当put一个值，即调用put时，先计算key的hash值，通过这个hash值找到对应的table数组索引，如果hash冲突，采用的是拉链法解决冲突，即把所有同义词（hash值相等）存储在一个单链表中，因此Entry可以看作是一个单链表，next指向下一个同义词。一个好的hash应该尽量减少同义词，因为当出现hash冲突时，在同义词中查找是线性查找，效率很低。put方法代码为(java 7):

 public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null) /* null的话直接存放在table[0] */
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length); /*找到table索引 */
        for (Entry<K,V> e = table[i]; e != null; e = e.next) { /* 查找是否已经存在相同的key */
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { /* 如果hash冲突且key一样，则返回旧值，替换成新值 */
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);  //插入新的Entry
        return null; /* 没有替换，则返回null */
    }

从源码中可以看出HashMap允许null作为key值，相当于null的hash为0。当key相同时，则覆盖原来的值，并返回旧的value。判断key是否相同是调用key的equals，因此如果使用自己的类作为key，必须重载equals方法，否则引用相同时才相等。求hash值并不是直接使用key的hashCode方法，而是自己内部实现的hash方法，hash方法会调用key的hashCode方法，这样能够减少hash冲突，且保证hash值能在指定返回内，而hashCode返回的值有可能超出table的索引范围。因此自定义类要作为key还必须覆盖hashCode方法，尽量返回一个素数。

2. IdentityHashMap

上面说了HashMap的key值是否相同是调用equals方法，而IdentityHashMap原理类似，但判断key是否相同运用 == 运算符，即判断是否同一个引用，实现上也有些不同，table不再是Entry，而是一个Object对象数组（不会存在hash冲突）。put时先计算key的hash值，通过hash值找到table数组的索引i，然后table[i]存储key，table[i + 1]存储value，代码为：

  public V put(K key, V value) {
        Object k = maskNull(key);
        Object[] tab = table;
        int len = tab.length;
        int i = hash(k, len);

        Object item;
        while ( (item = tab[i]) != null) {
            if (item == k) {
                V oldValue = (V) tab[i + 1];
                tab[i + 1] = value;
                return oldValue;
            }
            i = nextKeyIndex(i, len);
        }

        modCount++;
        tab[i] = k;
        tab[i + 1] = value;
        if (++size >= threshold)
            resize(len); // len == 2 * current capacity.
        return null;
    }

因此IdentityHashMap用于存储key值重复的map。

3. Hashtable

Hashtable和HashMap类似，不过put方法是同步的，使用synchronized锁住整个方法，支持并发控制，但现在已经废弃了，因为效率太低了，取而代之的是ConcurrentHashMap。

4. ConcurrentHashMap

取代Hashtable，和Hashtable不同，它是使用段加锁的方法实现并发，而不是同步整个方法。和HashMap不同，HashMap所有的Entry保存在一个table数组中，而ConcurrentHashMap是保存在不同的Segment（段）中，通过hash值先定位到Segment（其实也是一个Segment数组），然后只需对这个Segment(继承了ReentrantLock)加锁就可以了，不影响其他Segment。

5.LinkedHashMap

LinkedHashMap是HashMap的子类，因此具有HashMap的所有特点。与HashMap不同的是，HashMap不记录顺序，迭代时不保证任何顺序，而LinkedHashMap Entry使用了一个双链表记录顺序，并且Entry多了before 和after指针,迭代默认根据插入的顺序，可以设置成按最近访问顺序，put效率会比HashMap低，毕竟会有记录顺序的开销，但迭代速度会更快，直接遍历整个双向链表即可。

6. EnumMap

EnumMap使用java Enum类型作为key，相对简单且高效，内部还是使用了table，table的值是Object类型，put时就是根据key的值（原始值，一个整型数）作为索引，直接插入，table的长度就是key的枚举个数，其put代码为：

 public V put(K key, V value) {
        typeCheck(key);

        int index = key.ordinal();
        Object oldValue = vals[index];
        vals[index] = maskNull(value);
        if (oldValue == null)
            size++;
        return unmaskNull(oldValue);
    }

首先是类型检查，判断key是否是初始化的枚举类型（构造方法必须指定枚举类型的类类型），如果value是null则映射成内部的NULL（也是一个Object对象）。由此可见EnumMap是非常高效的，插入删除访问都是O(1)，不存在冲突问题。

7. TreeMap

TreeMap和之前的Map类型使用的数据结构不一样，它实现的是SortedMap，即按照key值自然顺序排列的，内部使用的数据结构是红黑树，红黑树是一种类平衡二叉树（和传统严格的平衡树有点差别），put源码为：

 public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

首先判断根是否空，不为空则遍历红黑树，看是否已经存在key，存在则直接覆盖原来的值并返回旧值，否则插入新数据，并调整红黑树。

8. ConcurrentSkipListMap

ConcurrentSkipListMap也是默认根据key值排序的，并且支持高并发访问（比ConcurrentHashMap并发性能更好，存取速度相对比ConcurrentHashMap低）。不过实现并不是使用红黑树，而是跳表，跳表的性能和查找树性能相当。

题外话：

以上介绍了8中map，如何选择取决于实际应用，如果不关心顺序且是单线程操作，使用HashMap，如果需要key按顺序排列，则使用TreeMap, 如果需要关心插入顺序或者最近访问顺序，使用LinkedHashMap。当涉及并发访问时，不关心key顺序使用ConcurrentHashMap，高并发且关心key顺序，使用ConcurrentSkipListMap，尽量不要使用Hashtable。如果key是枚举类型，则使用EnumMap。另外几乎每个Map类型都有相对应的Set版本，Set一般就是继承自Map，Set的元素值作为Map的key，而Map的value默认为一个Object对象常量，当然其实Map的value是什么都无所谓。

• 相关文章
• 全局相关文章