HashMap继承AbstractMap,实现了Map接口,Map接口定义了所有Map子类必须实现的方法。

1 public class HashMap
     
       extends AbstractMap
      
        implements Map
       
        , Cloneable, Serializable
       
      
     

　　HashMap的实例有两个参数影响其性能：初始容量和加载因子。初始容量只是哈希表在创建时的容量。加载因子是哈希表再其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行rehash操作（扩容操作）。

　　HashMap中定义的属性：

1     /** 2       * 默认的初始容量16. 3       */ 4      static final int DEFAULT_INITIAL_CAPACITY = 16; 5      /** 6       * 最大容量 7       */ 8      static final int MAXIMUM_CAPACITY = 1 << 30; 9      /**10       * 默认装载因子0.75f.11       */12      static final float DEFAULT_LOAD_FACTOR = 0.75f;13      /**14       * 存储数据的Entry数组15       */16      transient Entry[] table;17      /**18       * map中保存的键值对的数量19       */20      transient int size;21      /**22       * 需要调整大小的极限值（容量*装载因子）23       */24      int threshold;25      /**26       *装载因子,当HashMap的数据大小>=容量*加载因子时，HashMap会将容量扩容27       */28      final float loadFactor;29      /**30       * map结构被改变的次数31       */32      transient volatile int modCount;

　　HashMap的构造方法。

1     /** 2      *使用默认的容量及装载因子构造一个空的HashMap 3      */ 4     public HashMap() { 5         this.loadFactor = DEFAULT_LOAD_FACTOR; 6         threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); 7         table = new Entry[DEFAULT_INITIAL_CAPACITY];//根据默认容量（16）初始化table 8         init(); 9     }10 　　/**11      * 根据给定的初始容量的装载因子创建一个空的HashMap12      * 初始容量小于0或装载因子小于等于0将报异常 13      */14     public HashMap(int initialCapacity, float loadFactor) {15         if (initialCapacity < 0)16             throw new IllegalArgumentException("Illegal initial capacity: " +17                                                initialCapacity);18         if (initialCapacity > MAXIMUM_CAPACITY)19             initialCapacity = MAXIMUM_CAPACITY;20         if (loadFactor <= 0 || Float.isNaN(loadFactor))21             throw new IllegalArgumentException("Illegal load factor: " +22                                                loadFactor);23         int capacity = 1;24         //设置capacity为大于initialCapacity且是2的幂的最小值25         while (capacity < initialCapacity)26             capacity <<= 1;27         this.loadFactor = loadFactor;28         threshold = (int)(capacity * loadFactor);29         table = new Entry[capacity];30         init();31     }32 　　/**33      *根据指定容量创建一个空的HashMap34      */35     public HashMap(int initialCapacity) {36         this(initialCapacity, DEFAULT_LOAD_FACTOR);//调用上面的构造方法，容量为指定的容量，装载因子是默认值37     }38 　　/**39      *通过传入的map创建一个HashMap，容量为默认容量（16）和(map.zise()/DEFAULT_LOAD_FACTORY)+1的较大者，装载因子为默认值40      */41     public HashMap(Map
      m) {42         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,43                       DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);44         putAllForCreate(m);45     }

　　这里需要注意一个小问题，在第二个构造方法中，capacity才是初始容量，而不是initialCapacity，即如果执行new HashMap(9,0.75),那么HashMap的初始容量是16，而不是9。

　　在初始化table的时候都使用了Entry,这是HashMap的一个内部类。

　　Map.Entry接口定义的方法

1 K getKey();2 V getValue();3 V setValue();4 boolean equals(Object o);5 int hashCode();

　　HashMap.Entry类的具体实现

1 static class Entry
     
       implements Map.Entry
      
        { 2          final K key; 3          V value; 4          Entry
       
         next;//对下一个节点的引用 5          final int hash; 6   7          Entry(int h, K k, V v, Entry
        
          n) { 8              value = v; 9              next = n;10              key = k;11              hash = h;12          }13  14          public final K getKey() {15              return key;16          }17  18          public final V getValue() {19              return value;20          }21  22          public final V setValue(V newValue) {23          　　V oldValue = value;24              value = newValue;25              return oldValue;//返回的是之前的Value26          }27  28          public final boolean equals(Object o) {29              if (!(o instanceof Map.Entry))//先判断类型是否一致30                  return false;31              Map.Entry e = (Map.Entry)o;32              Object k1 = getKey();33              Object k2 = e.getKey();34  　　　　　　　// Key相等且Value相等则两个Entry相等35              if (k1 == k2 || (k1 != null && k1.equals(k2))) {36                  Object v1 = getValue();37                  Object v2 = e.getValue();38                  if (v1 == v2 || (v1 != null && v1.equals(v2)))39                      return true;40              }41              return false;42          }43          // hashCode是Key的hashCode和Value的hashCode的异或的结果44          public final int hashCode() {45              return (key==null   ? 0 : key.hashCode()) ^46                     (value==null ? 0 : value.hashCode());47          }48          // 重写toString方法，是输出更清晰49          public final String toString() {50              return getKey() + "=" + getValue();51          }52  56          void recordAccess(HashMap
         
           m) {57          }58  62          void recordRemoval(HashMap
          
            m) {63 }64 }
          
         
        
       
      
     

　　put()

1 public V put(K key, V value) { 2          if (key == null) 3              return putForNullKey(value); 4          int hash = hash(key.hashCode()); 5          int i = indexFor(hash, table.length); 6          for (Entry
     
       e = table[i]; e != null; e = e.next) { 7              Object k; 8              if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 9                  V oldValue = e.value;10                  e.value = value;11                  e.recordAccess(this);12                  return oldValue;13              }14          }15  16          modCount++;17          addEntry(hash, key, value, i);18          return null;19      }
     

　　当待put的key为null的时候会调用putForNullKey(value)方法,暂且绕过，先来看看如何hash。HashMap并不是直接将对象的hashcode作为哈希值，而是把key的hashcode做一些运算以得到最终的哈希值，而且得到的哈希值也不是在数组中的位置，无论是get还是put还是别的方法，计算哈希值都是：

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

1 static int hash(int h) {2          // This function ensures that hashCodes that differ only by3          // constant multiples at each bit position have a bounded4          // number of collisions (approximately 8 at default load factor).5          h ^= (h >>> 20) ^ (h >>> 12);6          return h ^ (h >>> 7) ^ (h >>> 4);7      }

　　hash方法为什么要这样取值，有待探讨，但是作用肯定是防止冲突。如何确定数据在数组中的位置：

1 int hash = hash(k.hashCode());2 int i = indexFor(hash,table.length);

　　第一行，得到哈希值，第二行，根据哈希值计算元素在数组中的位置。

1 static int indexFor(int h,int length){2        return h & (length - 1);  3 }

　　"h&(length-1)"其实这里有点小巧妙，为什么是做与运算？

　　首先我们要确定，HashMap的数组长度永远是偶数，所以length-1一定是一个奇数，假设现在的长度是16，length-1就是15，对应的二进制是：1111。

　　假设有两个元素，一个哈希值是8，二进制是1000，一个哈希值是9，二进制是1001。和1111与运算后，分别还是1000和1001，他们被分配在了数组的不同位置，这样，哈希的分布非常均匀。

　　那么如果数组的长度是奇数，减去1后就是偶数了，偶数对应的二进制最低位一定是0，例如14二进制1110。对上面两个数字分别与运算，得到1000和1000。这样，哈希值8和9的元素会被存储在数组同一个位置的链表中。在操作的时候，链表中的元素越多，效率就会越低，因为要不停的对链表循环比较。

　　在找到元素在数组中的索引位置以后，会循环遍历table[i]所在的链表，如果找到key值与传入的key值相同的对象，则替换并返回原对象；若找不到，则通过addEntry(hash,key,value,i)添加新的对象。

1 void addEntry(int hash, K key, V value, int bucketIndex) {     　　　　Entry
     
       e = table[bucketIndex];2      table[bucketIndex] = new Entry
      
       (hash, key, value, e);3      if (size++ >= threshold)4      　　resize(2 * table.length);5     }
      
     

　　以上过程就是新建一个Entry对象，并放在当前位置的Entry链表的头部。然后判断size是否达到了需要扩容的界限并让size增加1，如果达到了扩容的界限则调用resize(int capacity)方法。

1 void resize(int newCapacity) { 2          Entry[] oldTable = table; 3          int oldCapacity = oldTable.length; 4          // 这个if块表明，如果容量已经到达允许的最大值，即MAXIMUN_CAPACITY，则不再拓展容量，而将装载拓展的界限值设为计算机允许的最大值。 5          // 不会再触发resize方法，而是不断的向map中添加内容，即table数组中的链表可以不断变长，但数组长度不再改变 6          if (oldCapacity == MAXIMUM_CAPACITY) { 7              threshold = Integer.MAX_VALUE; 8              return; 9          }10          // 创建新数组，容量为指定的容量11          Entry[] newTable = new Entry[newCapacity];12          transfer(newTable);13          table = newTable;14          // 设置下一次需要调整数组大小的界限15          threshold = (int)(newCapacity * loadFactor);16      }

　　这里需要重点看看transfer方法：

1 void transfer(Entry[] newTable) { 2          // 保留原数组的引用到src中， 3          Entry[] src = table; 4          // 新容量使新数组的长度 5          int newCapacity = newTable.length; 6  　　　　　// 遍历原数组 7          for (int j = 0; j < src.length; j++) { 8              // 获取元素e 9              Entry
     
       e = src[j];10              if (e != null) {11                  // 将原数组中的元素置为null12                  src[j] = null;13                  // 遍历原数组中j位置指向的链表14                  do {15                      Entry
      
        next = e.next;16                      // 根据新的容量计算e在新数组中的位置17                      int i = indexFor(e.hash, newCapacity);18                      // 将e插入到newTable[i]指向的链表的头部19                      e.next = newTable[i];20                      newTable[i] = e;21                      e = next;22                  } while (e != null);23              }24          }25      }
      
     

　　tranfer方法将所有的元素重新哈希，因为新的容量变大，所以每个元素的哈希值和位置都是不一样的。

　　如果key值为空，我们来看看putForNullKey的处理过程：

1 private V putForNullKey(V value) { 2          for (Entry
     
       e = table[0]; e != null; e = e.next) { 3              if (e.key == null) { 4                  V oldValue = e.value; 5                  e.value = value; 6                  e.recordAccess(this); 7                  return oldValue; 8              } 9          }10          modCount++;11          addEntry(0, null, value, 0);12          return null;13      }
     

　　这是一个私有方法，在put方法中被调用。它首先遍历table数组，如果找到key为null的元素，则替换值并返回oldValue；否则通过addEntry方法添加元素，并返回null。

　　正确的使用HashMap

　　1.不要再并发场景中使用HashMap

　　　HashMap是线程不安全的，如果被多个线程共享的操作，将会引发不可预知的问题。据sun的说法，在扩容时，会引起链表的闭环，在get元素时，就会无限循环。

1 public V get(Object key) { 2     if (key == null) 3         return getForNullKey(); 4         int hash = hash(key.hashCode()); 5         for (Entry
     
       e = table[indexFor(hash, table.length)]; 6              e != null; 7              e = e.next) { 8             Object k; 9             if (e.hash == hash && ((k = e.key) == key || key.equals(k)))10                 return e.value;11         }12         return null;13     }
     

　　2.如果数据大小是固定的，那么最好给HashMap设定一个合理的容量值。

　　本文大量参考借鉴杭州.Mark童鞋HashMap源码分析这篇文章，如有冒犯，还请见谅。