HashMap 源码解析

HashMap简介：

　　HashMap在日常的开发中应用的非常之广泛，它是基于Hash表，实现了Map接口，以键值对(key-value)形式进行数据存储，HashMap在数据结构上使用的是数组+链表。允许null键和null值，不保证键值对的顺序。

HashMap检索数据的大致流程：

　　当我们使用HashMap搜索key所对应的value时，HashMap会根据Hash算法对key进行计算，得到一个key的hash值，再根据hash值算出该key在数组中存储的位置index，然后获取数组在index位置的键值对e,再使用链表对e进行遍历，查找遍历的元素是否和给定的key相符合，若有符合的，则返回其value值。

 自己手动画了一个HashMap的数据结构图：

HashMap源码分析：

　　HashMap是存储键值对的集合，实现了Map接口,下面我们看一下Map接口的定义：

/***映射key到value的顶级接口，不能包含重复的key，一个key最多可以映射到一个value,键和值均可为null*/public interface Map<K,V> {  //返回该map包含的键值对的个数，如果键值对的个数超过了Integer.MAX_VALUE,则返会Integer.MAX_VALUE  int size();  //如果该Map没有包含键值对，则返回true，否则返回false  boolean isEmpty();  //判断该map是否包含指定的key所对应的键值对，key可以为null  boolean containsKey(Object key);  //判断该map是否包含指定的value所对应的键值对,若map中包含有一个及以上的key,对应指定的value,则返回true，value可以为null  boolean containsValue(Object value);  //返回指定的key所对应的value，若key不存在，则返回null;但是返回null的key,不代表key在map中不存在，有可能是key所对应的value为null  V get(Object key);  //将指定的key和value映射为一个键值对，放入map中；若之前该map中包含了指定的Key,则该key所对应的老的值oldValue将会被替换为value  V put(K key, V value);  //删除指定的key所对应的键值对，并返回该key对应的value  V remove(Object key);  //将指定的map中的键值对复制到当前map中  void putAll(Map<? extends K, ? extends V> m);  //清除map中所有的键值对，该操作完成后，该map就是空的了  void clear();  //将map中所有的key返回，由于map中的key是不能重复的，所以用Set集合的方式装载所有的key  Set<K> keySet();  //将map中所有的value返回，由于map中的value是可重复的，所以用Collection集合的方式装载所有的value  Collection<V> values();  //将map中所有的键值对Entry返回，由于map中的键值对是不可重复的（key不可重复），所以用Set集合的方式装载所有的value  Set<Map.Entry<K, V>> entrySet();  //Map中承载键值对的数据结构Entry  interface Entry<K,V> {    //返回键值对的键值key    K getKey();    //返回键值对的value值    V getValue();    //将当前键值对的value值 替换为指定的value值    V setValue(V value);    //判断指定的对象和当前键值对是否equals相等，若相等，则代表是同一个键值对；    boolean equals(Object o);    //返回当前键值对的hashCode值    int hashCode();  }  //判断指定对象和当前Map的equals是否相等  boolean equals(Object o);  //返回当前Map的hashCode  int hashCode();}

下面我们具体的看一下HashMap：

  //HashMap是基于hash表来实现Map接口的，HashMap维护了下面几个变量：  //HashMap默认的初始化大小为16  static final int DEFAULT_INITIAL_CAPACITY = 16;  //HashMap包含键值对的最大容量为2^30,HashMap的容量一定要是2的整数次幂  static final int MAXIMUM_CAPACITY = 1 << 30;  //默认的加载因子为0.75  static final float DEFAULT_LOAD_FACTOR = 0.75f;  //装载键值对的内部容器Entry数组，长度一定得是2的幂  transient Entry[] table;  //HashMap中包含的键值对的个数  transient int size;  //HashMap的极限 当键值对的个数达到threshold时，数组table要扩容的  int threshold;  //加载因子  final float loadFactor;  //HashMap结构上被改变的次数，结构上的改变包括：键值对的大小的改变，修改HashMap的内部结构（比较进行了rehash操作），此属性用来保持fail-fast  transient volatile int modCount;

接下来我们看一下HashMap的构造函数：

/***根据指定的容量initialCapacity和加载因子loadFactor构造HashMap*/  public HashMap(int initialCapacity, float loadFactor) {    //对initialCapacity进行参数校验，若小于0，则抛出IllegalArgumentException异常    if (initialCapacity < 0)      throw new IllegalArgumentException("Illegal initial capacity: " +                        initialCapacity);    //若initialCapacity大于MAXIMUM_CAPACITY(2^30),则将MAXIMUM_CAPACITY赋值给initialCapacity    if (initialCapacity > MAXIMUM_CAPACITY)      initialCapacity = MAXIMUM_CAPACITY;    //对参数loadFactor进行有效性校验，不能<=0,不能非数字，否则抛出IllegalArgumentException异常    if (loadFactor <= 0 || Float.isNaN(loadFactor))      throw new IllegalArgumentException("Illegal load factor: " +                        loadFactor);    // Find a power of 2 >= initialCapacity 找到一个2的幂的数capacity，使其不小于参数initialCapacity    int capacity = 1;    //若capacity小于initialCapacity,则将capacity扩大一倍    while (capacity < initialCapacity)      capacity <<= 1;    this.loadFactor = loadFactor;    //设置极限，大小为 capacity * loadFactor,即(容量*负载因子)    threshold = (int)(capacity * loadFactor);    //创建一个大小为capacity的Entry数组table,用来保存键值对    table = new Entry[capacity];    //调用方法init(),进行额外的初始化操作    init();  }  //init方法是空的，如果你定制额外的初始化操作，可以继承HashMap，覆盖init()方法  void init() {  }  //通过指定的容量initialCapacity来构造HashMap，这里使用了默认的加载因子DEFAULT_LOAD_FACTOR 0.75  public HashMap(int initialCapacity) {      this(initialCapacity, DEFAULT_LOAD_FACTOR);  }  //无参的构造函数 加载因子为DEFAULT_LOAD_FACTOR 0.75，容量为默认的DEFAULT_INITIAL_CAPACITY 16，极限为 16*0.75=12  public HashMap() {      this.loadFactor = DEFAULT_LOAD_FACTOR;      threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);      table = new Entry[DEFAULT_INITIAL_CAPACITY];      init();  }

下面我们看一下HashMap中承载键值对的数据结构Entry的实现,Entry<K,V>是HashMap的一个静态内部类

/***Entry是HashMap里面承载键值对数据的数据结构，实现了Map接口里面的Entry接口，除了方法recordAccess(HashMap<K,V> m),recordRemoval(HashMap<K,V> m)外，其他方法均为final方法，表示即使是子类也不能覆写这些方法。*/static class Entry<K,V> implements Map.Entry<K,V> {    //键值,被final修饰，表明一旦赋值，不可修改    final K key;    //value值    V value;    //下一个键值对的引用    Entry<K,V> next;    //当前键值对中键值的hash值    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;    }    //设置value值，返回原来的value值    public final V setValue(V newValue) {    　　V oldValue = value;      value = newValue;      return oldValue;    }    //比较键值对是否equals相等，只有键、值都相等的情况下，才equals相等    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();      //若k1 == k2(k1,k2引用同一个对象),或者k1.equals(k2)为true时，进而判断value值是否相等      if (k1 == k2 || (k1 != null && k1.equals(k2))) {        Object v1 = getValue();        Object v2 = e.getValue();        //若v1 == v2(v1,v2引用同一个对象),或者v1.equals(v2)为true时，此时才能说当前的键值对和指定的的对象equals相等        if (v1 == v2 || (v1 != null && v1.equals(v2)))          return true;      }      //其他均为false      return false;    }    public final int hashCode() {      return (key==null  ? 0 : key.hashCode()) ^          (value==null ? 0 : value.hashCode());    }    public final String toString() {      return getKey() + "=" + getValue();    }    //此方法只有在key已存在的时候调用m.put(key,value)方法时，才会被调用，即覆盖原来key所对应的value值时被调用    void recordAccess(HashMap<K,V> m) {    }    //此方法在当前键值对被remove时调用    void recordRemoval(HashMap<K,V> m) {    }}

下面是Hash的put方法的实现：

/***将指定的键key,值value放到HashMap中*/public V put(K key, V value) {  //首先判断键key是否为null,若为null,则调用putForNullKey(V v)方法完成put  if (key == null)    return putForNullKey(value);  //程序走到这，说明key不为null了，先调用hash(int)方法，计算key.hashCode的hash值  int hash = hash(key.hashCode());  //再调用indexFor(int,int)方法求出此hash值对应在table数组的哪个下标i上 (bucket桶)  int i = indexFor(hash, table.length);  //遍历bucket桶上面的链表元素，找出HashMap中是否有相同的key存在，若存在，则替换其value值，返回原来的value值  for (Entry<K,V> e = table[i]; e != null; e = e.next) {    Object k;    //若元素e.hash值和上面计算的hash值相等，并且(e.key == 入参key,或者入参key equals 相等 e.key)，则说明HashMap中存在了和入参相同的key了，执行替换操作    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {      V oldValue = e.value;      e.value = value;      //在执行替换操作的时候，调用Entry对象的recordAccess(HashMap<K,V> m)方法，这个上面说过了      e.recordAccess(this);      return oldValue;    }  }  //程序走到这，说明原来HashMap中不存在key,则直接将键值对插入即可，由于插入元素，修改了HashMap的结构，因此将modeCount+1  modCount++;  //调用addEntry(int,K,V,int)方法进行键值对的插入  addEntry(hash, key, value, i);  //由于原来HashMap中不存在key，则不存在替换value值问题，因此返回null  return null;}

当key为null时，HashMap是这样进行数据插入的：

//先看看HashMap中原先是否有key为null的键值对存在，若存在，则替换原来的value值；若不存在，则将key为null的键值对插入到Entry数组的第一个位置table[0]private V putForNullKey(V value) {  //获取Entry数组的第一个元素:table[0],然后通过e.next进行链表的遍历，若遍历过程中有元素e.key为null,则替换该元素的值  for (Entry<K,V> e = table[0]; e != null; e = e.next) {    //说明原来之前HashMap中就已经存在key问null的键值对了，现在又插入了一个key为null的新元素，则替换掉原来的key为null的value值    if (e.key == null) {      V oldValue = e.value;      e.value = value;      //在执行替换操作的时候，调用Entry对象的recordAccess(HashMap<K,V> m)方法，这个上面说过了      e.recordAccess(this);      return oldValue;    }  }  //程序走到这，说明HashMap中原来没有key为null的键值对，需要直接插入元素，由于插入元素，修改了HashMap的结构，因此将modeCount+1  modCount++;  //调用addEntry(int,K,V,int)方法进行键值对的插入,这里将入参hash设置为0，K为null,插入的位置index也为0，说明key为null的元素插入在bucket[0]第一个桶上  addEntry(0, null, value, 0);  return null;}

HashMap在插入数据之前，要根据key值和hash算法来计算key所对应的hash值

//根据key的hashCode值，来计算key的hash值static int hash(int h) {  // This function ensures that hashCodes that differ only by  // constant multiples at each bit position have a bounded  // number of collisions (approximately 8 at default load factor).  h ^= (h >>> 20) ^ (h >>> 12);  return h ^ (h >>> 7) ^ (h >>> 4);}

/***在HashMap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置,如何计算这个位置就是hash算法.*HashMap的数据结构是数组和链表的结合,所以我们当然希望这个HashMap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个,*那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表.*所以我们首先想到的就是把hashcode对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的,但是，“模”运算的消耗还是比较大的，*能不能找一种更快速，消耗更小的方式那？java中时这样做的 :将hash值和数组长度按照位与&来运算*/static int indexFor(int h, int length) {  return h & (length-1);}

下面我们看一看实际进行数据添加的操作addEntry方法

/***将指定的key,value,hash,bucketIndex 插入键值对，若此时size 大于极限threshold,则将Entry数组table扩容到原来容量的两倍*/void addEntry(int hash, K key, V value, int bucketIndex) {  //取出原来bucketIndex处的键值对e  Entry<K,V> e = table[bucketIndex];  //创建一个新的键值对，使用给定的hash、key、value,并将新键值对的next属性指向e,最后将新键值对放在bucketIndex处  table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  //将size+1,若此时size 大于极限threshold,则将Entry数组table扩容到原来容量的两倍  if (size++ >= threshold)    //调用resize(int)方法，进行数组的扩容    resize(2 * table.length);}

我们知道HashMap采用的数组+链表来实现的，当HashMap中元素的个数size大于极限threshold时，会进行数组的扩容操作，这个操作使用resize(int newCapacity)方法实现的：

/***将HashMap中Entry数组table的容量扩容至新容量newCapacity,数组的扩容不但涉及到数组元素的复制，还要将原数组中的元素rehash到新的数组中，很耗时;如果能预估到放入HashMap中元素的大小，最好使用new HashMap(size)方式创建足够容量的HashMap，避免不必要的数组扩容(rehash操作)，提高效率*/void resize(int newCapacity) {  Entry[] oldTable = table;  int oldCapacity = oldTable.length;  //如果原数组的大小已经为允许的最大值MAXIMUM_CAPACITY了，则不能进行扩容了，这里仅仅将极限threshold设置为Integer.MAX_VALUE，然后返回  if (oldCapacity == MAXIMUM_CAPACITY) {    //将极限threshold设置为Integer.MAX_VALUE    threshold = Integer.MAX_VALUE;    return;  }  //程序走到这，说明可以进行扩容，先创建容量为newCapacity的新Entry数组newTable  Entry[] newTable = new Entry[newCapacity];  //调用tranfer(Entry[] newTable)方法，进行数组元素的移动和rehashing  transfer(newTable);  //将新数组newTable赋值给table  table = newTable;  //计算极限threshold的最新值  threshold = (int)(newCapacity * loadFactor);}//将原Entry数组table中的所有键值对迁移到新Entry数组newTable上void transfer(Entry[] newTable) {  //原数组赋值给src  Entry[] src = table;  //新数组长度为newCapacity  int newCapacity = newTable.length;  //遍历原数组  for (int j = 0; j < src.length; j++) {    //获取原数组中的元素(键值对),赋值给e    Entry<K,V> e = src[j];    //若元素e不为null    if (e != null) {      //将当前元素设值为null      src[j] = null;      //遍历元素e所对应的bucket桶内的所有元素      do {        //获取下一个元素next        Entry<K,V> next = e.next;        //重新计算键值对e在新数组newTable中的bucketIndex位置(即rehash操作)        int i = indexFor(e.hash, newCapacity);        //这步操作，说实话，没看懂，有清楚的，请不吝赐教        e.next = newTable[i];        //将当前元素e放入新数组的i位置        newTable[i] = e;        //将下一个元素next赋值给当前元素，以便完成遍历        e = next;      } while (e != null);    }  }}

下面我们看一下HashMap检索数据的操作：

//获取指定key所对应的value值public V get(Object key) {  //若key==null,则直接调用getForNullKey()方法  if (key == null)    return getForNullKey();  //到这说明key != null,先获取key的hash值  int hash = hash(key.hashCode());  //在indexFor(int hash,int length)获取key落在Entry数组的哪个bucket桶上，获取该bucket桶上的元素e,进而遍历e的链表，找相对应的key,若找到则返回key所对应的value值，找不到则返回null  for (Entry<K,V> e = table[indexFor(hash, table.length)];     e != null;     e = e.next) {    Object k;    //若元素e.hash == 上面计算的hash值，并且(e.key 和入参key是同一个对象的引用，或者e.key和入参key equals相等)，    //则认为入参key和当前遍历的元素e的key是同一个,返回e的value值    if (e.hash == hash && ((k = e.key) == key || key.equals(k)))      return e.value;  }  //上面遍历了一遍也没有找到，则返回null  return null;}//获取key为null的value值，由上面putForNullKey方法可知，key为null的键值对，被放在了Entry数组table的第一个bucket桶(table[0])private V getForNullKey() {  //获取Entry数组table的第一个元素e,从e开始往下遍历，若找到元素e.key 为null的，则直接返回该元素e.value值  for (Entry<K,V> e = table[0]; e != null; e = e.next) {    //找到元素e.key 为null的，则直接返回该元素e.value值    if (e.key == null)      return e.value;  }  //从table[0]开始，遍历链表一遍，没有找到key为null的，则返回null  return null;}//获取指定key所对应的键值对Entry,先获取key的hash值，再获取该hash值应放入哪个hash桶，然后遍历该桶中的键值对，若有则返回该键值对；若没有则返回nullfinal Entry<K,V> getEntry(Object key) {  //若key为null,则hash值为0；若key != null,则利用hash(int)计算key的hash值  int hash = (key == null) ? 0 : hash(key.hashCode());  //获取该hash值应放入哪个hash桶,并遍历该hash桶  for (Entry<K,V> e = table[indexFor(hash, table.length)];     e != null;     e = e.next) {    Object k;    //若元素e.hash == hash,并且(e.key == key，或者 key.equals(e.key)为true)，则认为入参key和当前遍历的元素e.key是同一个，返回该元素e    if (e.hash == hash &&      ((k = e.key) == key || (key != null && key.equals(k))))      return e;  }  //若没有则返回null  return null;}

//判断HashMap中是否含有指定key的键值对，内部用getEntry(Object key)来实现public boolean containsKey(Object key) {  return getEntry(key) != null;}

//将指定Map中的所有元素(键值对)拷贝到当前HashMap中，对于当前HashMap中存在的key,则进行value值的替换public void putAll(Map<? extends K, ? extends V> m) {  //若指定的Map中没有元素，则直接返回  int numKeysToBeAdded = m.size();  if (numKeysToBeAdded == 0)    return;  //若必要，则进行数组的扩容  if (numKeysToBeAdded > threshold) {    int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);    if (targetCapacity > MAXIMUM_CAPACITY)      targetCapacity = MAXIMUM_CAPACITY;    //计算新的容量    int newCapacity = table.length;    while (newCapacity < targetCapacity)      newCapacity <<= 1;    //若新容量大于目前数组的长度，则调用resize(int)进行扩容    if (newCapacity > table.length)      resize(newCapacity);  }  //获取指定Map的迭代器，循环调用put(K k,V v)方法，进行键值对的插入  for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {    Map.Entry<? extends K, ? extends V> e = i.next();    put(e.getKey(), e.getValue());  }}

下面看下HashMap的remove操作：

/*** 删除指定key所对应的元素  */public V remove(Object key) {  //调用方法reomveEntryForKey(Object key)来删除并获取指定的entry  Entry<K,V> e = removeEntryForKey(key);  //若entry为null，则返回null；否则返回entry的value值  return (e == null ? null : e.value);}/***移除并返回指定key所关联的键值对entry,若HashMap中没有键值对和指定的key相关联，则返回null*/final Entry<K,V> removeEntryForKey(Object key) {  //若key为null,则hash值为0；若key != null,则利用hash(int)计算key的hash值  int hash = (key == null) ? 0 : hash(key.hashCode());  //获取key应放入的在数组中的位置索引i  int i = indexFor(hash, table.length);  //标识前一个元素  Entry<K,V> prev = table[i];  //标识遍历过程中的当前元素  Entry<K,V> e = prev;  //遍历bucket桶table[i]中的元素，寻找对应的key  while (e != null) {    //当前元素的下一个元素    Entry<K,V> next = e.next;    Object k;    //元素e.hash和上面计算的hash值相等，并且(key == e.key 或者key.equals(e.key) 为true)，说明找到了指定key所对应的键值对    if (e.hash == hash &&      ((k = e.key) == key || (key != null && key.equals(k)))) {      //由于删除了一个元素，修改了HashMap的结构，因此将modCount+1      modCount++;      //将size-1      size--;      //若待查找的元素为桶内的第一个元素，则当前元素的下一个元素next放入数组中位置i中      if (prev == e)        table[i] = next;      //否则将上一个元素的next属性指向 当前元素的next      else        prev.next = next;      //当元素被remove时，调用Entry对象的recordRemove(Map<K,V> m)方法      e.recordRemoval(this);      //返回找到的当前元素      return e;    }    //程序走到这，说明当前元素不是要查找的元素；则将当前元素赋值给上一个元素，将下一个元素赋值给当前元素，以完成遍历    prev = e;    e = next;  }  return e;}

//判断HashMap中是否包含指定的对象valuepublic boolean containsValue(Object value) {  //若value为null，则调用containsNullValue()方法处理  if (value == null)    return containsNullValue();  //将数组table赋值给tab  Entry[] tab = table;  //遍历数组tab的每个索引位置(此层循环对应数组结构)  for (int i = 0; i < tab.length ; i++)    //对应指定的索引位置i,遍历在索引位置i上的元素(此层循环对应链表结构)    for (Entry e = tab[i] ; e != null ; e = e.next)      //若某个元素e.value和指定的value equals相等，则返回true      if (value.equals(e.value))        return true;  //遍历完成没有找到对应的value值，返回false  return false;}//判断HashMap是否包含value为null的元素private boolean containsNullValue() {  //将数组table赋值给tab  Entry[] tab = table;  //遍历数组tab的每个索引位置(此层循环对应数组结构)  for (int i = 0; i < tab.length ; i++)    //对应指定的索引位置i,遍历在索引位置i上的元素(此层循环对应链表结构)    for (Entry e = tab[i] ; e != null ; e = e.next)      //若某个元素e.value == null，则返回true      if (e.value == null)        return true;  //没有找到value值为null的，返回false  return false;}

//清除HashMap中所有的键值对，此操作过后，HashMap就是空的了public void clear() {  //要删除所有的元素，肯定会对HashMap的结构造成改变，因此modCount+1  modCount++;  Entry[] tab = table;  //遍历数组，将数组中每个索引位置的设置为null  for (int i = 0; i < tab.length; i++)    tab[i] = null;  //将size 修改为0  size = 0;}

现在看一下上面没有讲的一个构造函数:

//构造一个新的HashMap，以承载指定Map中所有的键值对，使用默认的加载因子DEFAULT_LOAD_FACTORpublic HashMap(Map<? extends K, ? extends V> m) {  this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,         DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);  //调用putAllForCreate(Map<? extends K, ? extends V>)方法完成元素的迁移  putAllForCreate(m);}private void putAllForCreate(Map<? extends K, ? extends V> m) {  for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {    Map.Entry<? extends K, ? extends V> e = i.next();    //在迭代器循环中调用putForCreate(K k,V v)来实现元素的创建    putForCreate(e.getKey(), e.getValue());  }}//该方法和put方法不同，它不会进行数组的扩容resize,和对modCount的检查private void putForCreate(K key, V value) {  //若key为null,则hash值为0；若key != null,则利用hash(int)计算key的hash值  int hash = (key == null) ? 0 : hash(key.hashCode());  //求key应该放入哪个hash桶(bucket)内  int i = indexFor(hash, table.length);  //遍历链表，若key之前在Map中已经有了，则直接返回  for (Entry<K,V> e = table[i]; e != null; e = e.next) {    Object k;    if (e.hash == hash &&      ((k = e.key) == key || (key != null && key.equals(k)))) {      e.value = value;      return;    }  }  //调用createEntry(int hash,K k,V v,int bucketIndex)方法完成键值对的创建并加入到链表中  createEntry(hash, key, value, i);}void createEntry(int hash, K key, V value, int bucketIndex) {  //将bucketIndex位置的元素取出来  Entry<K,V> e = table[bucketIndex];  //创建一个新的键值对，使用给定的hash、key、value,并将新键值对next指向e,最后将新键值对放在bucketIndex处  table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  //将数组大小size + 1  size++;}

　　下面我们讲下HashMap的负载因子loadfactor, 所谓负载因子就是散列表的实际元素数目(n)/散列表的容量(m), 它衡量的是一个散列表的空间的使用程度，默认情况下loadfactor是0.75，它的作用是当HashMap中元素的个数size 大于(HashMap的容量capacity * 负载因子loadfactor)时，该HashMap便会进行扩容resize。

　　我们先说下hash冲突：

　　当利用HashMap存数据的时候，先根据key的hashcode值来计算key的hash值(利用hash函数)，再根据hash值来计算该key在数组table中的位置index（hash & (length-1)）,比如我们要存两个键值对key1-value1和key2-value2,

如果key1、key2分别通过hash函数计算的hash值hash1、hash值hash2 相等，那key1和key2一定会落在数组table的同一个位置上，这就产生了冲突，这个冲突是由不同的key值但是却相同的hash值引起的，称之为hash冲突。HashMap解决hash冲突的方式就是链表，虽然key1-value1和key2-value2这两个键值对落在了数组table的同一个位置上，但是它们是链表的方式连接在一起，当HashMap查找key1时，就需要遍历这个链表了。

当负载因子越大的时候，出现hash冲突的可能性越大，这意味着数组table中某个具体的桶bucket上不止有一个元素（此时就构成了链表了）可能性增大，在检索数据的时候需要遍历链表的可能性增大，因此检索的效率就比较低（耗时长），但是空间的利用率越高。

当负载因子越小的时候，出现hash冲突的可能性越小，这意味着数组table中某个具体的桶bucket上不止有一个元素（此时就构成了链表了）可能性减小了，在检索数据的数据需要遍历链表的可能性减小，因此检索的效率就比较高，但是空间利用率越低。

　　上面的源码解析了提到了HashMap的容量一定得是2的整数此幂(2^n),这又是问什么呢？

　　通过上面的源码我们知道：根据hash值求该hash值在数组中的位置的实现是： hash & (length-1)，当数组table的长度length为2的整数次幂的时候，那（length-1）二进制表示形式从低位开始一定都是1，直到为0，如果length依次为2,4,8,16,32，64，则(length-1)一次为1,3,7,15,31,63，那(length-1)的二进制形式依次为1,11,111,1111,11111，我们知道二进制的与运算&，当一方位数全是1的时候，进行&运算的结果完全取决于另外一方。

比如从0开始到15,依次和15进行&运算，看看结果的平均分布情况：

通过位与&操作后，发现0-15完全平均的落在了数组的各个索引位置

 下面通过一个小例子予以验证：

public class HashDemo {  private final int[] table;  public HashDemo(int size) {    this.table = new int[size];    for (int i = 0; i < size; i++) {      table[i] = i;    }  }  //求key所对应的在数组中的位置  public int index(int key){    //求hash值    int hash = hash(key);    //返回key所对应的在数组中的位置    return hash & (table.length-1);  }  //HashMap中hash函数的实现,求hash值  public int hash(int h){    h ^= (h >>> 20) ^ (h >>> 12);    return h ^ (h >>> 7) ^ (h >>> 4);  }  public static void main(String[] args) {    Map<String,Integer> keyToNumber = new HashMap<String, Integer>();    int size = 16;    HashDemo hashDemo = new HashDemo(size);    int testSize = 1000;    for (int i = 0; i < testSize; i++) {      int index = hashDemo.index(i);      Integer number = keyToNumber.get("key" + index);      if (number == null) {        keyToNumber.put("key"+index,1);      }else {        keyToNumber.put("key"+index,keyToNumber.get("key"+index)+1);      }    }    Iterator<Map.Entry<String, Integer>> it = keyToNumber.entrySet().iterator();    while (it.hasNext()) {      Map.Entry<String, Integer> entry = it.next();      System.out.println(entry.getKey() + "  == "+entry.getValue());    }  }}

当我们将size设置为16 （2的4次幂）时，控制台输出：

key4   == 62
key3   == 62
key6   == 62
key5   == 62
key0   == 62
key2   == 62
key1   == 62
key10   == 63
key11   == 63
key8   == 63
key7   == 62
key9   == 63
key15   == 63
key14   == 63
key13   == 63
key12   == 63

 由上面的输出可见，数据非常平均的分配在了数组的16个索引位置，

当size设置为非2的整数次幂的时候，比如50，这时控制台输出：

key0   == 120
key17   == 124
key16   == 124
key1   == 120
key49   == 128
key48   == 128
key32   == 128
key33   == 128

由此可见1000个数据只分配在了8个索引位置上。

使用HashMap的注意事项：

　　1.HashMap采用数组+链表的形式存储数据，当预先知道要存储在HashMap中数据量的大小时，可以使用new HashMap(int size)来指定其容量大小，避免HashMap数组扩容导致的元素复制和rehash操作带来的性能损耗。

　　2.HashMap是基于Hash表、实现了Map接口的，查找元素的时候，先根据key计算器hash值，进而求得key在数组中的位置，但是要尽量避免hash冲突造成的要遍历链表操作，因此在我们手动指定HashMap容量的时候，容量capacity一定得是2的整数次幂，这样可以让数据平均的分配在数组中，减小hash冲突，提高性能。

 　 3.HashMap是非线程安全的，在多线程条件下不要使用HashMap，可以使用ConcurrentHashMap代替。

原标题：HashMap 源码解析

关键词：