[@倚贤][¥20]TreeMap、HashMap、LindedHashMap的区别

1.具体区别如下：

我们在开发的过程中使用HashMap比较多，在Map中在Map 中插入、删除和定位元素，HashMap 是最好的选择。

但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。

如果需要输出的顺序和输入的相同,那么用LinkedHashMap 可以实现,它还可以按读取顺序来排列.

HashMap是一个最常用的Map，它根据键的hashCode值存储数据，根据键可以直

接获取它的值，具有很快的访问速度。HashMap最多只允许一条记录的键为null，

允许多条记录的值为null。HashMap不支持线程同步，即任一时刻可以有多个线程

同时写HashMap，可能会导致数据的不一致性。如果需要同步，可以用Collections的

synchronizedMap方法使HashMap具有同步的能力。

Hashtable与HashMap类似，不同的是：它不允许记录的键或者值为空；它支持线程的

同步，即任一时刻只有一个线程能写Hashtable，因此也导致了Hashtable在写入时会比较慢。

LinkedHashMap保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的

记录肯定是先插入的。

在遍历的时候会比HashMap慢TreeMap能够把它保存的记录根据键排序，默认是按升序排序，

也可以指定排序的比较器。当用Iterator遍历TreeMap时，得到的记录是排过序的。

2.LinkedHashMap简述：

     LinkedHashMap是HashMap的一个子类，它保留插入的顺序，如果需要输出的顺序和

输入时的相同，那么就选用LinkedHashMap。

     LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现

提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保

证该顺序恒久不变。

     LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双

重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。

注意：此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结

构上修改了该映射，则它必须保持外部同步。

根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用get方法)的链表。

默认是按插入顺序排序，如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素

移至链表尾部，不断访问可以形成按访问顺序排序的链表。 可以重写removeEldestEntry方法返

回true值指定插入元素时移除最老的元素。

3.LinkedHashMap的实现：

      对于LinkedHashMap而言，它继承与HashMap、底层使用哈希表与双向链表来保存所有元

素。其基本操作与父类HashMap相似，它通过重写父类相关的方法，来实现自己的链接列表特性。

下面我们来分析LinkedHashMap的源代码：

类结构：
public class LinkedHashMap extends HashMap implements Map

1) 成员变量：

LinkedHashMap采用的hash算法和HashMap相同，但是它重新定义了数组中保存的元素Entry，

该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而

在哈希表的基础上又构成了双向链接列表。看源代码：

//true表示按照访问顺序迭代，false时表示按照插入顺序

private final boolean accessOrder;
/**

• 双向链表的表头元素。
  */

private transient Entry header;

/**

• LinkedHashMap的Entry元素。
• 继承HashMap的Entry元素，又保存了其上一个元素before和下一个元素after的引用。
  */

private static class Entry extends HashMap.Entry {

Entry<K,V> before, after;  
……  

}
HashMap.Entry:

static class Entry implements Map.Entry {

    final K key;  
    V value;  
    Entry<K,V> next;  
    final int hash;  

    Entry(int h, K k, V v, Entry<K,V> n) {  
        value = v;  
        next = n;  
        key = k;  
        hash = h;  
    }  

}

2) 初始化：

通过源代码可以看出，在LinkedHashMap的构造方法中，实际调用了父类HashMap的

相关构造方法来构造一个底层存放的table数组。如：

public LinkedHashMap(int initialCapacity, float loadFactor) {

super(initialCapacity, loadFactor);  

accessOrder = false;  

}
HashMap中的相关构造方法：

public HashMap(int initialCapacity, float loadFactor) {

if (initialCapacity < 0)  

    throw new IllegalArgumentException("Illegal initial capacity: " +   initialCapacity);  

if (initialCapacity > MAXIMUM_CAPACITY)  

    initialCapacity = MAXIMUM_CAPACITY;  

if (loadFactor <= 0 || Float.isNaN(loadFactor))  

    throw new IllegalArgumentException("Illegal load factor: " +  loadFactor); 

// Find a power of 2 >= initialCapacity  

int capacity = 1;  

while (capacity < initialCapacity)  

    capacity <<= 1;  
this.loadFactor = loadFactor;  

threshold = (int)(capacity * loadFactor);  

table = new Entry[capacity];  

init();  

}

我们已经知道LinkedHashMap的Entry元素继承HashMap的Entry，提供了双向链表

的功能。在上述HashMap的构造器中，最后会调用init()方法，进行相关的初始化，这个

方法在HashMap的实现中并无意义，只是提供给子类实现相关的初始化调用。

    LinkedHashMap重写了init()方法，在调用父类的构造方法完成构造后，进一步实现

了对其元素Entry的初始化操作。

void init() {

header = new Entry<K,V>(-1, null, null, null);  

header.before = header.after = header;  

}

3) 存储：

LinkedHashMap并未重写父类HashMap的put方法，而是重写了父类HashMap的put方法

调用的子方法void recordAccess(HashMap m) ，void addEntry(int hash, K key, V value,

int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己

特有的双向链接列表的实现。

HashMap.put:

public V put(K key, V value) {

    if (key == null)  

        return putForNullKey(value);  

    int hash = hash(key.hashCode());  

    int i = indexFor(hash, table.length);  

    for (Entry<K,V> e = table[i]; e != null; e = e.next) {  

        Object k;  

        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  

            V oldValue = e.value;  

            e.value = value;  

            e.recordAccess(this);  

            return oldValue;  

        }  
    }  

    modCount++;  

    addEntry(hash, key, value, i);  

    return null;  
}  

重写方法：

void recordAccess(HashMap m) {

        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;  

        if (lm.accessOrder) {  

            lm.modCount++;  

            remove();  

            addBefore(lm.header);  

        }  
    }  

void addEntry(int hash, K key, V value, int bucketIndex) {

// 调用create方法，将新元素以双向链表的的形式加入到映射中。  

createEntry(hash, key, value, bucketIndex);  

// 删除最近最少使用元素的策略定义  

Entry<K,V> eldest = header.after;  

if (removeEldestEntry(eldest)) {  

    removeEntryForKey(eldest.key);  

} else {  

    if (size >= threshold)  

        resize(2 * table.length);  

}  

}
void createEntry(int hash, K key, V value, int bucketIndex) {

HashMap.Entry<K,V> old = table[bucketIndex];  

Entry<K,V> e = new Entry<K,V>(hash, key, value, old);  

table[bucketIndex] = e;  

// 调用元素的addBrefore方法，将元素加入到哈希、双向链接列表。  

e.addBefore(header);  

size++;  

}

private void addBefore(Entry existingEntry) {

after  = existingEntry;  

before = existingEntry.before;  

before.after = this;  

after.before = this;  

}

4) 读取：

LinkedHashMap重写了父类HashMap的get方法，实际在调用父类getEntry()方法取得

查找的元素后，再判断当排序模式accessOrder为true时，记录访问顺序，将最新访问的

元素添加到双向链表的表头，并从原来的位置删除。由于的链表的增加、删除操作是常

量级的，故并不会带来性能的损失。

HashMap.containsValue:

public boolean containsValue(Object value) {

if (value == null)  

        return containsNullValue();  

Entry[] tab = table;  

    for (int i = 0; i < tab.length ; i++)  

        for (Entry e = tab[i] ; e != null ; e = e.next)  

            if (value.equals(e.value))  

                return true;  

return false;  

}  

/*查找Map中是否包含给定的value，还是考虑到，LinkedHashMap拥有的双链表，

在这里Override是为了提高迭代的效率。

*/
public boolean containsValue(Object value) {

    // Overridden to take advantage of faster iterator  

    if (value==null) {  

        for (Entry e = header.after; e != header; e = e.after)  

            if (e.value==null)  

                return true;  

    } else {  

        for (Entry e = header.after; e != header; e = e.after)  

            if (value.equals(e.value))  

                return true;  
    }  

    return false;  

}  

/*该transfer()是HashMap中的实现：遍历整个表的各个桶位，然后对桶进行遍历得到

每一个Entry，重新hash到newTable中，

//放在这里是为了和下面LinkedHashMap重写该法的比较，

void transfer(Entry[] newTable) {

    Entry[] src = table; 

    int newCapacity = newTable.length; 

    for (int j = 0; j < src.length; j++) { 

        Entry<K,V> e = src[j]; 

        if (e != null) { 

            src[j] = null; 

            do { 

                Entry<K,V> next = e.next; 

                int i = indexFor(e.hash, newCapacity); 

                e.next = newTable[i]; 

                newTable[i] = e; 

                e = next; 

            } while (e != null); 

        } 

    } 

} 

*/
/**
*transfer()方法是其父类HashMap调用resize()的时候调用的方法，它的作用是表扩容后，

把旧表中的key重新hash到新的表中。

*这里从写了父类HashMap中的该方法，是因为考虑到，LinkedHashMap拥有的双链表，

在这里Override是为了提高迭代的效率。
*/
void transfer(HashMap.Entry[] newTable) {

int newCapacity = newTable.length;

for (Entry e = header.after; e != header; e = e.after) {

 int index = indexFor(e.hash, newCapacity);  

 e.next = newTable[index];  

 newTable[index] = e;  

}

}

public V get(Object key) {

// 调用父类HashMap的getEntry()方法，取得要查找的元素。  

Entry<K,V> e = (Entry<K,V>)getEntry(key);  

if (e == null)  

    return null;  

// 记录访问顺序。  

e.recordAccess(this);  

return e.value;  

}

void recordAccess(HashMap m) {

LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;  

// 如果定义了LinkedHashMap的迭代顺序为访问顺序，  

// 则删除以前位置上的元素，并将最新访问的元素添加到链表表头。  

if (lm.accessOrder) {  

    lm.modCount++;  

    remove();  

    addBefore(lm.header);  

}  

}

/**

     * Removes this entry from the linked list. 

     */  
    private void remove() {  

        before.after = after;  

        after.before = before;  

    }  

/*clear链表，设置header为初始状态/

public void clear() {

super.clear();

header.before = header.after = header;

}

5) 排序模式：

LinkedHashMap定义了排序模式accessOrder，该属性为boolean型变量，对于访问

顺序，为true；对于插入顺序，则为false。

private final boolean accessOrder;
一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。看LinkedHashMap

的构造方法，如：

public LinkedHashMap(int initialCapacity, float loadFactor) {

super(initialCapacity, loadFactor);  

accessOrder = false;  

}

这些构造方法都会默认指定排序模式为插入顺序。如果你想构造一个LinkedHashMap，

并打算按从近期访问最少到近期访问最多的顺序（即访问顺序）来保存元素，那么请使用

下面的构造方法构造LinkedHashMap：

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {

super(initialCapacity, loadFactor);  

this.accessOrder = accessOrder;  

}

该哈希映射的迭代顺序就是最后访问其条目的顺序，这种映射很适合构建LRU缓存。

LinkedHashMap提供了removeEldestEntry(Map.Entry eldest)方法。该方法可以提供

在每次添加新条目时移除最旧条目的实现程序，默认返回false，这样，此映射的行为将类

似于正常映射，即永远不能移除最旧的元素。

当有新元素加入Map的时候会调用Entry的addEntry方法，会调用removeEldestEntry方法，

这里就是实现LRU元素过期机制的地方，默认的情况下removeEldestEntry方法只返回false

表示元素永远不过期。

/**

* This override alters behavior of superclass put method. It causes newly 

* allocated entry to get inserted at the end of the linked list and 

* removes the eldest entry if appropriate. 

*/  

void addEntry(int hash, K key, V value, int bucketIndex) {

   createEntry(hash, key, value, bucketIndex);  
   // Remove eldest entry if instructed, else grow capacity if appropriate  

   Entry<K,V> eldest = header.after;  

   if (removeEldestEntry(eldest)) {  

       removeEntryForKey(eldest.key);  

   } else {  

       if (size >= threshold)   

           resize(2 * table.length);  

   }  

}

/**

* This override differs from addEntry in that it doesn't resize the 

* table or remove the eldest entry. 

*/  

void createEntry(int hash, K key, V value, int bucketIndex) {

   HashMap.Entry<K,V> old = table[bucketIndex];  

Entry e = new Entry(hash, key, value, old);

   table[bucketIndex] = e;  

   e.addBefore(header);  

   size++;  

}

protected boolean removeEldestEntry(Map.Entry eldest) {

   return false;  

}
此方法通常不以任何方式修改映射，相反允许映射在其返回值的指引下进行自我修改。

如果用此映射构建LRU缓存，则非常方便，它允许映射通过删除旧条目来减少内存损耗。

例如：重写此方法，维持此映射只保存100个条目的稳定状态，在每次添加新条目时

删除最旧的条目。

private static final int MAX_ENTRIES = 100;

protected boolean removeEldestEntry(Map.Entry eldest) {

return size() > MAX_ENTRIES;  

}

其实LinkedHashMap几乎和HashMap一样，不同的是它定义了一个Entry header，

这个header不是放在Table里，它是额外独立出来的。LinkedHashMap通过继承hashMap

中的Entry,并添加两个属性Entry before,after,和header结合起来组成一个双

向链表，来实现按插入顺序或访问顺序排序