人们对于任何事物的认知，往往都存在这么一个现象：只有你了解的东西，你才会感兴趣。

   HashMap之于Java开发者来说，也是如此。相信多数人在起初相当长的时间内，对HashMap的印象都是“Map接口的实现类，是基于哈希的，用于存放键-值对，允许null作为键和值，非线程安全的”，仅此而已。于是在程序编写过程中便“肆无忌惮”往里放键-值对。而只有你对HashMap的实现有了一定的了解之后，你才会有兴趣研究HashMap深层次的问题，比如“HashMap最多能放多少个键-值对？如何提高HashMap的使用效率？”。其实，我一直都对HashMap的“线性数组+链表”的实现机制充满好奇，刚刚有时间研究了一下源码，现把心得与大家分享。

 

   首先，我们来看看HashMap的数据结构：

    /**     *  初始容量，大小必须是2的指数次方，默认是16.     */    static final int DEFAULT_INITIAL_CAPACITY = 16;    /**     * 默认最大容量，值为1<<30     */    static final int MAXIMUM_CAPACITY = 1 << 30;    /**     * 哈希表的默认加载因子，值为0.75.     */    static final float DEFAULT_LOAD_FACTOR = 0.75f;    /**     * 存储元素的数组，大小必须是2的指数次方，默认是16.     */    transient Entry[] table;    /**     * THashMap中的存储的
     
      映射的数目.     */    transient int size;    /**     * threshold=容量*加载因子。当实际数目大于threshold时，HashMap就需要扩容.     * @serial     */    int threshold;    /**     * 哈希表的加载因子，如果创建时不指定loadFactor，则使用DEFAULT_LOAD_FACTOR.     *     * @serial     */    final float loadFactor;    //... ...    /**     *      * 
      
用一个静态内部类来定义数组项链表的元素
     *     * @author bruce.yang     * @version 1.0 Created on 2014-10-22 上午11:39:50     */    static class Entry
      
        implements Map.Entry
       
         {        final K key;        V value;        Entry
        
          next;        final 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 (key==null   ? 0 : key.hashCode()) ^                   (value==null ? 0 : value.hashCode());        }        public final String toString() {            return getKey() + "=" + getValue();        }

可以看出，HashMap正是采用数组(table)类存储数据的，而数组每一个元素则是一个被静态内部类Entry封装起来的对象，元素在数组中的下标则是根据key的hashcode计算出来的；当元素下标重复的时候，会在此下标处形成一个链表，而这个链表就是通过Entry结构来实现的。我们看到，这个Entry结构是一个单向链表，它只有一个next项指向下一个元素，此外，它还包含<K,V>对，同时还有一个哈希值hash。

 

   其次，当我们往hashmap中put元素的时候，先是根据key的hash值计算得出这个元素在数组中的位置（即下标），然后就可以把这个元素放到对应的位置中了。如果这个位子上已经存放有其他元素了，那么在同一个位子上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。源码：

   /**     * 建立指定key和value之间的映射：     * 如果已经存在key，则替换对应的value，并返回原来的value；如果原来没有建立映射，则建立映射，并返回null。     * 当然了，由于HashMap允许key和value为null，返回null还有可能就是原来的value为null。     */    public V put(K key, V value) {     //如果key==null，则调用专门的方法处理        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;    }    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-value项     */    void addEntry(int hash, K key, V value, int bucketIndex) {     Entry
       
         e = table[bucketIndex];     //加入该项到链表头部          table[bucketIndex] = new Entry
        
         (hash, key, value, e);        if (size++ >= threshold)            resize(2 * table.length);    }    /**     *扩充HashMap的容量     */    void resize(int newCapacity) {        Entry[] oldTable = table;        int oldCapacity = oldTable.length;        if (oldCapacity == MAXIMUM_CAPACITY) {            threshold = Integer.MAX_VALUE;            return;        }        Entry[] newTable = new Entry[newCapacity];        transfer(newTable);        table = newTable;        threshold = (int)(newCapacity * loadFactor);    }    /**     * 将原来数组中元素传输到新数组中     */    void transfer(Entry[] newTable) {        Entry[] src = table;        int newCapacity = newTable.length;        for (int j = 0; j < src.length; j++) {            Entry
         
           e = src[j];            if (e != null) {                src[j] = null;                do {                    Entry
          
            next = e.next;                    int i = indexFor(e.hash, newCapacity);                    e.next = newTable[i];                    newTable[i] = e;                    e = next;                } while (e != null);            }        }    }

可以看到,首先判断key是否为null:

      1).若为null，则调用专门的方法putForNullKey（value）处理并返回。
        1.1)如果事先已经存在key为null的映射，则替换后返回old value。
        1.2)如果不存在，则添加新的项到链表中
      2).若key不为null
        2.1)首先计算key的哈希值，然后根据哈希值和table数组的长度定位数组项。
        2.2)对数组项的链表进行遍历，如果key的哈希值与链表中的某一项的哈希值相等且key本身引用值相等或者引用值所指向的对象相等，则替换相应项的value值为新的value，并返回老的value。如果没有找到相同的key，则加入该项到链表中。
        2.3)addEntry方法直接将新的项加入到链表的头部，新项的next引用指向原来的链表项。此外判断是否需要扩容，如果此时存储的项数目size大于等于threshold，则扩大HashMap容量为原来的2倍。
        2.4)resize方法用来扩容HashMap。默认是扩容至原来的2倍大小。

 

   第三，当从hashmap中get元素时，首先计算key的hashcode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。源码：

   /**     * 根据key取得value     */    public V get(Object key) {        if (key == null)            return getForNullKey();        int hash = hash(key.hashCode());        for (Entry
     
       e = table[indexFor(hash, table.length)];             e != null;             e = e.next) {            Object k;            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))                return e.value;        }        return null;    }    private V getForNullKey() {        for (Entry
      
        e = table[0]; e != null; e = e.next) {            if (e.key == null)                return e.value;        }        return null;    }

可以看到，如果key为null，get方法与put方法对应，对null值也有特殊处理，即直接到table[0]中去找key为null对应的value。

    如果key不为null，则定位key所在数组项，然后遍历链表，如果存在key，则返回对应的value值，否则返回null。

 

   第四，HashMap的初始化：

   /**     *指定初始化容量和加载因子     */    public HashMap(int initialCapacity, float loadFactor) {     //initialCapacity不能小于0        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal initial capacity: " +                                               initialCapacity);        //如果指定容量大于默认最大容量，则按照默认最大容量创建        if (initialCapacity > MAXIMUM_CAPACITY)            initialCapacity = MAXIMUM_CAPACITY;        //loadFactor不能小于0        if (loadFactor <= 0 || Float.isNaN(loadFactor))            throw new IllegalArgumentException("Illegal load factor: " +                                               loadFactor);        //找最大于指定初始化容量的2的指数幂作为表的真实容量        int capacity = 1;        while (capacity < initialCapacity)            capacity <<= 1;        this.loadFactor = loadFactor;        threshold = (int)(capacity * loadFactor);        table = new Entry[capacity];        init();    }    /**     *只指定初始化容量，加载因子采用默认     */    public HashMap(int initialCapacity) {        this(initialCapacity, DEFAULT_LOAD_FACTOR);    }    /**     * 初始化容量和加载因子都采用默认     */    public HashMap() {        this.loadFactor = DEFAULT_LOAD_FACTOR;        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);        table = new Entry[DEFAULT_INITIAL_CAPACITY];        init();    }

只看源码和注释就一目了然了，这里所要特别注意一下带两个参数的构造方法，其初始化时的初始大小不一定是你所指定的大小。

 

   最后，文章开头提出的那两个问题已经不再成为问题了：

 1).HashMap最大容量是1 << 30，
 2).而影响HashMap性能的两个因素是：初始容量和加载因子。这里借用书中的一段话来表述：容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
通常，默认加载因子 (0.75)在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap类的操作中，包括 get 和 put操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash操作。
读到这里，相信你对HashMap已经有了一个更深刻的认识。

   各位，晚安，好梦。