源码分析之Map（四）Map实现类特性对比

TreeMap

　　TreeMap是红黑树的java实现。相比HashMap来说，TreeMap多实现了一个接口NavigableMap，也就是这个接口，决定了TreeMap与HashMap的不同：HashMap的key是无序的，TreeMap的key是有序的。

　源码展示：

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
    /**
     * The comparator used to maintain order in this tree map, or null if it uses the natural ordering of its keys.
     */
    private final Comparator<? super K> comparator;

    private transient Entry<K,V> root; //根节点

    /**
     * The number of entries in the tree
     */
    private transient int size = 0;

    /**
     * The number of structural modifications to the tree.
     */
    private transient int modCount = 0;

    /**
     * Constructs a new, empty tree map, using the natural ordering of its keys.*/
    public TreeMap() {
        comparator = null;
    }

    /**
     * Constructs a new, empty tree map, ordered according to the given comparator. */
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

    /**
     * Constructs a new tree map containing the same mappings as the given map, ordered according to the <em>natural ordering</em> of its keys.*/
    public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }

    /**
     * Constructs a new tree map containing the same mappings and using the same ordering as the specified sorted map.This method runs in linear time.*/
    public TreeMap(SortedMap<K, ? extends V> m) {
        comparator = m.comparator();
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }
}

View Code

　红黑树相关操作可见源码分析之Map（三）HashMap

LinkedHashMap

　　LinkedHashMap是HashMap的子类，所以也具备HashMap的诸多特性。不同的是，LinkedHashMap还维护了一个双向链表，以保证通过Iterator遍历时顺序与插入顺序一致。除此之外，它还支持Access Order，即按照元素被访问的顺序来排序

　源码展示：

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{
    /**
     * HashMap.Node subclass for normal LinkedHashMap entries. 存储元素的结构
     */
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
/**
     * The head (eldest) of the doubly linked list. 双向链表的头节点
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list. 双向链表的尾节点
     */
    transient LinkedHashMap.Entry<K,V> tail;

    /**
     * The iteration ordering method for this linked hash map: <tt>true</tt>
     * for access-order, <tt>false</tt> for insertion-order. true为访问顺序  false为插入顺序
     *
     * @serial
     */
    final boolean accessOrder;
     
    /**
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance with the specified initial capacity and load factor.*/
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    /**
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance with the specified initial capacity and a default load factor (0.75).*/
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    /**
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance with the default initial capacity (16) and load factor (0.75).
     */
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    /**
     * Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with the same mappings as the specified map. */
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }

    /**
     * Constructs an empty <tt>LinkedHashMap</tt> instance with the specified initial capacity, load factor and ordering mode.*/
    public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
    
}

View Code

特性对比

	HashMap	LinkedHashMap	TreeMap	concurrentHashMap
原理	HashMap内部是基于哈希表实现的键值对存储。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。hashcode相同时，会储存在同一个bucket位置的LinkedList中，在一定条件下，LinkedList会转为红黑树	LinkedHashMap是继承自HashMap，底层使用哈希表与双向链表来保存所有元素。顺序可以分为插入顺序和访问顺序，是根据成员变量accessOrder决定的。其访问顺序可以实现LRU	TreeMap实现了SotredMap接口，它是有序的集合。而且是一个红黑树结构，每个key-value都作为一个红黑树的节点。如果在调用TreeMap的构造函数时没有指定比较器，则根据key执行自然排序。	ConcurrentHashMap相比HashMap而言，是多线程安全的，其底层数据与HashMap的数据结构相同。而HashTable虽然是线程安全的，方法都是用Synchronized修饰的，但争夺的都是同一个对象锁，在高并发的情况下，会产生效率低，等待时间长的问题。concurrentHashMap 很多地方使用了cas操作和分段加锁，加锁的最小单位是Hash桶，这使得ConcurrentHashMap效率大大提升.
线程安全	否	否	否	是
初始容量	16	16	0	16
存储结构	数组+链表/红黑树	数组+链表/红黑树,HashMap子类	红黑树	数组+链表/红黑树
顺序规则	无序	访问顺序或插入顺序	key的自然顺序或自定义顺序	无序
存储特点	最多一条记录的key为null	最多一条记录的key为null	key的自然顺序时不能为null	不能存null
插入效率	高	高	较高（需要比较排序）	较高
时间复杂度	O(1)	O(n)	O(log(n))	O(1)