本文共 8744 字，大约阅读时间需要 29 分钟。

前言

Map接口储存一组成对的键-值对象，提供key（键）到value（值）的映射，Map中的key不要求有序，不允许重复。value同样不要求有序，但可以重复。

最常见的Map实现类是HashMap，他的储存方式是哈希表，优点是查询指定元素效率高。Map接口提供了将键映射到集合的对象，一个映射不能包含重复的键，每个键最多只能映射到一个值。

Map接口中同样提供了集合的常用方法，如clear()方法，isEmpty()方法，Size()方法等。

Map接口

public interface Map
   
     {    int size();    boolean isEmpty();    boolean containsKey(Object var1);    boolean containsValue(Object var1);    V get(Object var1);    V put(K var1, V var2);    V remove(Object var1);    void putAll(Map
     var1);    void clear();    Set
    
      keySet();    Collection
     
       values();    Set
      
       
        > entrySet();    boolean equals(Object var1);    int hashCode();    ……}
       
      
     
    
   

常用实现类

Map|------HashTable|           |-------WeakHashTable|------HashMap|           |-------LinkedHashMap|------TreeMap|------WeakHashMap

HashMap

HashMap是基于哈希表的 Map 接口的实现，可以说是平时用途最广泛的Map实现类。从内部结构上来讲，传统的HashMap是一种“数组+链表”的结构，通过对象的hashcode定位数组中的位置，调用equal方法存取数据，JDK1.8中加入了红黑树处理逻辑。

内部成员

//初始容量为16    DEFAULT_INITIAL_CAPACITY = 1 << 4;     //最大容量    static final int MAXIMUM_CAPACITY = 1 << 30;    //默认平衡因子    static final float DEFAULT_LOAD_FACTOR = 0.75f;    //桶的树化阈值，当桶中元素个数超过这个值时，需要使用红黑树节点替换链表节点    static final int TREEIFY_THRESHOLD = 8;    //树的链表还原阈值，当扩容时，桶中元素个数小于这个值，就会把树形的桶元素 还原（切分）为链表结构    static final int UNTREEIFY_THRESHOLD = 6;    //当哈希表中的容量大于这个值时，表中的桶才能进行树形化,否则桶内元素太多时会扩容，而不是树形化为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD    static final int MIN_TREEIFY_CAPACITY = 64;

初始化

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);        this.loadFactor = loadFactor;        this.threshold = tableSizeFor(initialCapacity);    }    public HashMap(int initialCapacity) {        this(initialCapacity, DEFAULT_LOAD_FACTOR);    }    public HashMap() {        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted    }    public HashMap(Map
    m) {        this.loadFactor = DEFAULT_LOAD_FACTOR;        putMapEntries(m, false);    }

HashMap初始化时需要两个参数：capacity和loadfactor，前者指HashMap的容量，初始化时会调用tableSizeFor方法，此方法的返回值为大于且最接近capacity的2的次幂，即最终桶的数量，也就是数组的实际长度。后者是平衡因子，是键值对数量除以数组的长度。

如果在初始化时不提供上述两个参数，HashMap便会使用默认值，比如初始容量是16，平衡因子是0.75。

关键方法

put方法

HashMap的特点在于快速存取元素，我们可以使用put方法添加元素，如下为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;    }    static int indexFor(int h, int length) {        return h & (length-1);    }
   

具体步骤如下：

• 1，调用hash(key)方法获取key的hashcode，再调用indexFor(hash, table.length)获取数组索引；
• 2，判断table[i]是否为null，如果是null，直接新建节点添加，并转向4，如果table[i]不为null，转向3；
• 3，遍历整个链表，判断链表元素是否和key一样，如果相同直接覆盖value，否则转向4，这里的相同指的是hashCode以及equals；
• 4，先判断插入成功后实际存在的键值对数量size是否超多了最大容量threshold，如果超过，则扩大数组长度为原先的两倍；
• 5，创建新结点，新节点的next指向原先数组相应链表的头结点。

需要注意的是，HashMap是先插入再扩容，这与有些Map实现类有所不同。同时，JDK1.8以后，在put实现逻辑中加入了树化的过程，读者可以另外查询相关资料信息。

get方法

HashMap的get方法实现逻辑如下：

public V get(Object key) {        if (key == null)            return getForNullKey();        Entry
   
     entry = getEntry(key);        return null == entry ? null : entry.getValue();    }    private V getForNullKey() {        if (size == 0) {            return null;        }        for (Entry
    
      e = table[0]; e != null; e = e.next) {            if (e.key == null)                return e.value;        }        return null;    }    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;    }
      
     
    
   

其实get方法的实现逻辑与put方法中寻找相应节点类似，从大体过程上来讲，分为两步：

• 1，根据hashcode定位数组位置；
• 2，遍历整个链表，使用equal方法判断key是否相同，相同则返回对应的value，若不存在，则返回null。

值得注意的是，HashMap允许存在key和value为null的情况，所以使用get方法返回值为null具有歧义，当需要判断是否存在指定key的键值对，请使用containsKey方法。

LinkedHashMap

LinkedHashMap是HashMap的子类，与HashMap有着同样的存储结构，但它加入了一个双向链表的头结点，将所有put到LinkedHashmap的节点一一串成了一个双向循环链表，此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。

内部成员

private transient Entry
   
     header;    private final boolean accessOrder;
   

除了继承于HashMap的内部成员变量，LinkedHashMap额外多了两个成员变量。header是内部双向链表的头结点，accessOrder表示的是LinkedHashMap的迭代顺序，默认为false。当为false时表示按照插入顺序，当为true时表示按照访问顺序。后者经常用于LRU（最近最少使用）算法。

初始化

LinkedHashMap提供如下四种构造方法：

public LinkedHashMap(int initialCapacity, float loadFactor) {        super(initialCapacity, loadFactor);        accessOrder = false;    }    public LinkedHashMap(int initialCapacity) {        super(initialCapacity);        accessOrder = false;    }    public LinkedHashMap() {        super();        accessOrder = false;    }    public LinkedHashMap(Map
    m) {        super(m);        accessOrder = false;    }    public LinkedHashMap(int initialCapacity,                         float loadFactor,                         boolean accessOrder) {        super(initialCapacity, loadFactor);        this.accessOrder = accessOrder;    }

可以看出，由于LinkedHashMap继承自HashMap，因此LinkedHashMap的初始化过程其实就是HashMap的初始化过程，最后设置accessOrder成员变量。

除此之外，LinkedHashMap内部的Entry< K, V >也继承自HashMap，并且增加了before和after两个引用，增加了双向链表的节点新增删除操作。

private static class Entry
   
     extends HashMap.Entry
    
      {
           Entry
     
       before, after;        Entry(int hash, K key, V value, HashMap.Entry
      
        next) {            super(hash, key, value, next);        }        private void remove() {            before.after = after;            after.before = before;        }        private void addBefore(Entry
       
         existingEntry) {            after  = existingEntry;            before = existingEntry.before;            before.after = this;            after.before = this;        }        void recordAccess(HashMap
        
          m) { LinkedHashMap
         
           lm = (LinkedHashMap
          
           )m; if (lm.accessOrder) { lm.modCount++; remove(); addBefore(lm.header); } } void recordRemoval(HashMap
           
             m) { remove(); } }
           
          
         
        
       
      
     
    
   

关键方法

LinkedHashMap继承于HashMap，保留了HashMap的put、get方法逻辑。由于内部维护了双向链表，在新增、删除和读取的过程中额外新增了链表操作。

put方法

在put方法中，当需要新增entry时，会调用addEntry(int, K, V, int)方法和createEntry(int, K, V, int)，LinkedHashMap重写了该方法：

void addEntry(int hash, K key, V value, int bucketIndex) {        super.addEntry(hash, key, value, bucketIndex);        // Remove eldest entry if instructed        Entry
   
     eldest = header.after;        if (removeEldestEntry(eldest)) {            removeEntryForKey(eldest.key);        }    }    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;        e.addBefore(header);        size++;    }
     
    
   

LinkedHashMap在原先HashMap的基础上，按照新增的顺序将entry加入到双向链表中。

get方法

当调用get方法时，LinkedHashMap除了按照HashMap的逻辑获取value之外，会根据accessOrder的值，对内部的双向链表进行维护。

public V get(Object key) {        Entry
   
     e = (Entry
    
     )getEntry(key);        if (e == null)            return null;        e.recordAccess(this);        return e.value;    }    void recordAccess(HashMap
     
       m) {            LinkedHashMap
      
        lm = (LinkedHashMap
       
        )m;            if (lm.accessOrder) {                lm.modCount++;                remove();                addBefore(lm.header);            }        }
       
      
     
    
   

当迭代顺序为访问顺序时，LinkedHashMap会将返回的entry置为双向链表的头结点。

remove方法

LinkedHashMap的remove方法跟HashMap差不多，只是需要额外维护内部的双向链表。

void recordRemoval(HashMap
   
     m) {            remove();        }     private void remove() {            before.after = after;            after.before = before;        }
   

总结

本文主要基于JDK1.7而阐述，JDK1.8对HashMap有诸多改动，后续会有相关文章列举。平时HashMap的时候，大多数都是知其然却不知其所以然，希望本文能帮助读者对HashMap有深入的了解。

转载地址：http://ssgmi.baihongyu.com/