Java中的Collection和Map(三)--Map体系

　　Map集合，即我们常用的key-Value 集合，Map以键值对的形式来存储数据，我们常用Map集合有：HashMap,TreeMap,WeakHashMap,EnumMap,LinkedHahMap,HashTable。他们都是以key-Value键值对形式存储数据。

1、HashMap

　　HashMap 底层采用Hash表结构来存储数据的。

　　 /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry[] table = (Entry[]) EMPTY_TABLE;

　　我们存储的数据就存放在Entry 类型的table数组中，Entry 是HashMap一内部类，他实现了接口Map.Entry 接口。Entry结构跟我们前面说链表Node有点相似。

static class Entry implements Map.Entry {
        final K key;
        V value;
        Entry next;
        int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        public final int hashCode() {
            return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
        }

        public final String toString() {
            return getKey() + "=" + getValue();
        }

        /**
         * This method is invoked whenever the value in an entry is
         * overwritten by an invocation of put(k,v) for a key k that's already
         * in the HashMap.
         */
        void recordAccess(HashMap m) {
        }

        /**
         * This method is invoked whenever the entry is
         * removed from the table.
         */
        void recordRemoval(HashMap m) {
        }
    }

　　当我们使用 new HashMap(); 构造方法来创建一HashMap 时，检测参数是否合法，内部初始化了一些成员变量。　

public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
 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);

        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }

　　　当我们调用put(K k,V v) 方法的时候，底册又是如何做的呢：

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry 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;
    }

　　从上面的代码中我们可以看出，当我们首次向一个新创建的Map 中put 数据的时候，首先是通过 inflateTable 方法用来初始化用来存数据table数组的长度。初始化长度的同时通过initHashSeedAsNeeded 方法 来初始化哈希掩码值。

private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }

　　　如果我们存放的 key-Value 键值对中的键值为null, 调用用putForNullKey(value) 方法 来存放我们的键值对。

 private V putForNullKey(V value) {
        for (Entry e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

　　从代码中我们可以看到，如果key 已存在于原来的map 中，将原来key所对应的value替换为我们新的value，并将原来的value 返回。如过不存在，则调用addEntry方法将我们的key-value 存入 ，并返回null(key)。

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

　　addEntry 方法首先要做的事情是判断是否需要 扩充table 的长度。如果需要的话调用resize 方法来扩充table 的长度，算出hash ，通过indexFor 方法算出元素所要存放于数组中对应的下标，通过createEntry 方法将元素存入Mpa中。

void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

　　如果 存如的 key-value 键值对key 不为空。首先通过indexFor  方法算出方法算出元素所要存放于数组中对应的下标i， 从i 开始向后查找元素是否存在于map中如果存在替换原map 中key 所对应的value 值，并将 旧值返回。如果不存在调用addEntry 方法存入。

　　以上就是map put 值得过程。而当我们通过  value get(Key key)  方法来取值的时候是如何做的呢。

 public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }
final Entry getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        for (Entry e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

　　知道了put 的流程，get 方法理解起来就一目了然了。

　　下面我们再来看下我们通常用的 containsKey(Key key) 和containsValue(Value value)方法。

 public boolean containsKey(Object key) {
        return getEntry(key) != null;
    }
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;
    }

　　是不是有种一目了然地感觉。

　　综上所述：我们知道了HashMap 底层数据结构是hash 表结构。我们讲到了put 方法、get方法 以及containsValue 和containsKey 方法的内部实现。唯独没有说到Hash表到底是中结构，底层的hash 算法是如何实现的。这些会在后面的章节中慢慢说明。

2、TreeMap

　　TreeMap 底层机构是一种属结构。TreeMap 具有排序排序功能。 我们在使用TreeMap 的时候可以传入我们自己的比较器，对其进行排序。如果不传入的话TreeMap 会使用自己key 默认的比较器进行排序。如果我们想要是用自己定义的类型来作为TreeMap的key 的话 ，我们自定义的类需要实现Comparable 接口实现其compareTo(T o) 方法。或者在使用的时候我们传入我们自己定义的比较器。下面我们就来看下TreeMap 的底层结构：

　　跟HashMap 一样TreeMap 底层也是用 Entry来存储数据的，但是TreeMap 有自己的Entry 实现(树）。

static final class Entry implements Map.Entry {
        K key;
        V value;
        Entry left = null;
        Entry right = null;
        Entry parent;
        boolean color = BLACK;

        /**
         * Make a new cell with given key, value, and parent, and with
         * {@code null} child links, and BLACK color.
         */
        Entry(K key, V value, Entry parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }

        /**
         * Returns the key.
         *
         * @return the key
         */
        public K getKey() {
            return key;
        }

        /**
         * Returns the value associated with the key.
         *
         * @return the value associated with the key
         */
        public V getValue() {
            return value;
        }

        /**
         * Replaces the value currently associated with the key with the given
         * value.
         *
         * @return the value associated with the key before this method was
         *         called
         */
        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;

            return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
        }

        public int hashCode() {
            int keyHash = (key==null ? 0 : key.hashCode());
            int valueHash = (value==null ? 0 : value.hashCode());
            return keyHash ^ valueHash;
        }

        public String toString() {
            return key + "=" + value;
        }
    }

　　知道了TreeMap 底层Entry 的实现我们再来看下  put 方法是如何向TreeMap 中存放数据的。

public V put(K key, V value) {
        Entry 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 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 e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

　　当我们想一TreeMap 中存入第一个元素的时候，底层树种不存在节点，这是我们创建一个节点做为树的根节点。节点存放有key 和value 的值（Entry）。以后每次put 分为两种情况。1、如果在我门 new TreeMap 的时候传入了我们自己的比较器 ，就采用我们自己定义的比较器来比较key 值得大小，来确定元素在书中存放的位置。2、如果没有传入我们自己定义的比较器（这中情况下 我们的key 类型需要实现Comparable 接口）使用key 默认实现的 比较方法。

　　在来看以下 TreeMap 的get 方法：

public V get(Object key) {
        Entry p = getEntry(key);
        return (p==null ? null : p.value);
    }
 final Entry getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        Comparable<? super K> k = (Comparable<? super K>) key;
        Entry p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }

　　上面我们看到了 get 方法的实现。无非就是 通过我们自己传入的比较器，或者key 自身的比较方法来来寻找相同的key 值。找到的话返回当前key 所对应的 value  找不到的话返回null。

　　同样containsKey 和 containsValue 实现思路差不多。

3、WeakHashMap

　　WeakHashMap实现了Map接口，是HashMap的一种实现，他使用弱引用作为内部数据的存储方案，WeakHashMap可以作为简单缓存表的解决方案，当系统内存不够的时候，垃圾收集器会自动的清除没有在其他任何地方被引用的键值对。

　　如果需要用一张很大的HashMap作为缓存表，那么可以考虑使用WeakHashMap，当键值不存在的时候添加到表中，存在即取出其值。

WeakHashMap weakMap = new WeakHashMap();
for(int i = 0; i < 100000; i++){
Integer ii = new Integer(i);
weakMap.put(ii, new byte[i]);
}

HashMap map = new HashMap();
　　for (int i = 0; i < 10000; i++) {
  Integer ii = new Integer(i);
  map.put(ii, new byte[i]);
}

　　这2段代码分别用-Xmx2M的参数运行，运行的结果是第一段代码可以很好的运行，第二段代码会出现“Java Heap Space”的错误，这说明用WeakHashMap存储，在系统内存不够用的时候会自动回收内存。

　　如果WeakHashMap的key在系统内持有强引用，那么WeakHashMap就退化为HashMap，所有的表项无法被垃圾收集器自动清理。

4、EnumMap

　　与枚举类型键一起使用的专用 Map 实现。枚举映射中所有键都必须来自单个枚举类型，该枚举类型在创建映射时显式或隐式地指定。枚举映射在内部表示为数组。此表示形式非常紧凑且高效。

枚举映射根据其键的自然顺序 来维护（该顺序是声明枚举常量的顺序）。在 collection 视图（keySet()、entrySet() 和 values()）所返回的迭代器中反映了这一点。

由 collection 视图返回的迭代器是弱一致 的：它们不会抛出 ConcurrentModificationException，也不一定显示在迭代进行时发生的任何映射修改的效果。

不允许使用 null 键。试图插入 null 键将抛出 NullPointerException。但是，试图测试是否出现 null 键或移除 null 键将不会抛出异常。允许使用 null 值。

像大多数 collection 一样，EnumMap 是不同步的。如果多个线程同时访问一个枚举映射，并且至少有一个线程修改该映射，则此枚举映射在外部应该是同步的。这一般通过对自然封装该枚举映射的某个对象进行同步来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap(java.util.Map) 方法来“包装”该枚举。最好在创建时完成这一操作，以防止意外的非同步访问：

     Map m
         = Collections.synchronizedMap(new EnumMap(...));
 

实现注意事项：所有基本操作都在固定时间内执行。虽然并不保证，但它们很可能比其 HashMap 副本更快。

　　下面我们简单来看下 EnumMap 底层简单实现：

　　先从构造方法：

private final Class keyType;
private transient K[] keyUniverse;
private transient Object[] vals; 
public EnumMap(Class keyType) {
        this.keyType = keyType;
        keyUniverse = getKeyUniverse(keyType);
        vals = new Object[keyUniverse.length];
    }
public EnumMap(EnumMap m) {
        keyType = m.keyType;
        keyUniverse = m.keyUniverse;
        vals = m.vals.clone();
        size = m.size;
    }
public EnumMap(Map m) {
        if (m instanceof EnumMap) {
            EnumMap em = (EnumMap) m;
            keyType = em.keyType;
            keyUniverse = em.keyUniverse;
            vals = em.vals.clone();
            size = em.size;
        } else {
            if (m.isEmpty())
                throw new IllegalArgumentException("Specified map is empty");
            keyType = m.keySet().iterator().next().getDeclaringClass();
            keyUniverse = getKeyUniverse(keyType);
            vals = new Object[keyUniverse.length];
            putAll(m);
        }
    }

　　EnumMap 提供了三种不同参数的构造方法。

　　再来看下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);
    }
private Object maskNull(Object value) {
        return (value == null ? NULL : value);
    }
private V unmaskNull(Object value) {
        return (V) (value == NULL ? null : value);
    }

　　从中我们可以看出put 方法插入值得时候 是想vals 数组中加入了数据。

　　再看get 方法：

public V get(Object key) {
        return (isValidKey(key) ?
                unmaskNull(vals[((Enum)key).ordinal()]) : null);
    }
private boolean isValidKey(Object key) {
        if (key == null)
            return false;

        // Cheaper than instanceof Enum followed by getDeclaringClass
        Class keyClass = key.getClass();
        return keyClass == keyType || keyClass.getSuperclass() == keyType;
    }

　　从上面我们可以看出：枚举映射在内部表示为数组。

5、LinkedHashMap

　LinkedHashMap是HashMap的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用LinkedHashMap。

   LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
   LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。

　　对于LinkedHashMap而言，它继承与HashMap、底层使用哈希表与双向链表来保存所有元素。其基本操作与父类HashMap相似，它通过重写父类相关的方法，来实现自己的链接列表特性。下面我们来分析LinkedHashMap的源代码：

public class LinkedHashMap extends HashMap implements Map  

　　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 before, after;  
    ……  
}  

　　HashMap.Entry:

static class Entry implements Map.Entry {  
        final K key;  
        V value;  
        Entry next;  
        final int hash;  
  
        Entry(int h, K k, V v, Entry n) {  
            value = v;  
            next = n;  
            key = k;  
            hash = h;  
        }  
}  

　　通过源代码可以看出，在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<>(-1, null, null, null);
        header.before = header.after = header;
    }

　　 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 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 lm = (LinkedHashMap)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 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 old = table[bucketIndex];  
    Entry e = new Entry(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;  
}  

6、HashTable 和HashMap 的区别：

　　HashTable 和HashMap 大致相同，我们这部在累述，在这只说下他们的区别：

public class Hashtable
    extends Dictionary
    implements Map, Cloneable, java.io.Serializable 

public class HashMap
    extends AbstractMap
    implements Map, Cloneable, Serializable

　Hashtable 继承自Dictionary HashMap 继承自AbstractMap。

　HashTable 的put 方法：

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                V old = e.value;
                e.value = value;
                return old;
            }
        }

        modCount++;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();

            tab = table;
            hash = hash(key);
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        Entry e = tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        return null;
    }

　　注意1 方法是同步的
　　注意2 方法不允许value==null
　　注意3 方法调用了key的hashCode方法，如果key==null,会抛出空指针异常 HashMap的put方法如下

　　HashMap 的put

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry 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;
    }

　　注意1 方法是非同步的
　　注意2 方法允许key==null
　　注意3 方法并没有对value进行任何调用，所以允许为null