人们对于任何事物的认知，往往都存在这么一个现象：只有你了解的东西，你才会感兴趣。
   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中的存储的<K,V>映射的数目.*/transient int size;/*** threshold=容量*加载因子。当实际数目大于threshold时，HashMap就需要扩容.* @serial*/int threshold;/*** 哈希表的加载因子，如果创建时不指定loadFactor，则使用DEFAULT_LOAD_FACTOR.** @serial*/final float loadFactor;//... .../*** * <p>用一个静态内部类来定义数组项链表的元素</p>** @author bruce.yang* @version 1.0 Created on 2014-10-22 上午11:39:50*/static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;final int hash;/*** Creates new entry.*/Entry(int h, K k, V v, Entry<K,V> 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<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;}private V putForNullKey(V value) {for (Entry<K,V> 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<K,V> e = table[bucketIndex];//加入该项到链表头部  table[bucketIndex] = new Entry<K,V>(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<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);}}}

可以看到,首先判断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<K,V> 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<K,V> 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不能小于0if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);//如果指定容量大于默认最大容量，则按照默认最大容量创建if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;//loadFactor不能小于0if (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已经有了一个更深刻的认识。

   各位，晚安，好梦。