解析HashMap（一）

一、什么是HashMap

​ oracle文档中的解释：

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

​ 我们可以得到几个重要的性质：

​ １．基于哈希表的Map接口的实现。

​ ２．它的key和value允许出现null。

​ ３．非同步。

​ ４．不保证映射顺序（插入顺序），也不保证该顺序不随时间的改变。

二、哈希表（散列表）

１．什么是哈希表？

​ 散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，也就是我们常说的哈希函数，使得每个关键字key都有一个对应的存储位置f(key)。而使用散列技术将记录存储在一块连续的存储在一块连续的存储空间中，这快连续的空间就是散列表/哈希表。

２．哈希函数的构造方法：

有两个原则：

a)方便计算；

b)散列地址分布均匀。

​ 常见的方法：2.1 直接定地址法、2.2 数字分析法、2.3 平方取中法、2.4 折叠法、2.5 除留余数法、2.6 随机数法。

３．哈希冲突

​ 哈希冲突是指，当key1 ≠ key2时，出现了f(key1) ≠ f(key2)。

​ 常见的解决办法有：开放定地址法、再散列函数法、链地址法（这也是HasnMap用来解决哈希冲突的办法）、公共溢出区法。

三、基于JDK 1.7源码解析

１．数据结构

​ 在JDK 7中HashMap是由数组＋链表实现数据存储的，综合两者的特性（数组寻址容易，插入删除困难；链表插入删除容易，寻址困难）实现了寻址容易，插入删除也容易。

​ 我们可以把数组看成一排桶连接起来，所有hash到同一个桶中的key，他们对应的结点是通过链表连接起来。

２．重要属性：

//内部数组的默认初始容量，作为hashmap的初始容量，是2的4次方(16)
   static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
   //默认的最大容量，2的30次方
   static final int MAXIMUM_CAPACITY = 1 << 30;
   //默认负载因子，当容器使用率达到这个75%的时候就扩容
   static final float DEFAULT_LOAD_FACTOR = 0.75f;
   //当数组表还没扩容的时候，一个共享的空表对象
   static final Entry<?,?>[] EMPTY_TABLE = {};
   //内部数组表，用来装entry，大小只能是2的n次方
   transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
   //存储的键值对的个数
   transient int size;
   /**
    * 扩容的临界点，如果当前容量达到该值，则需要扩容了
    * 如果当前数组容量为0时（空数组），则该值作为初始化内部数组的初始容量
    */
   int threshold;
   //由构造函数传入的指定负载因子,用来表示哈希表在其容量自动增加之前可以达到多满的一种尺度。
   final float loadFactor;
   //Hash的修改次数，用来快速失败
   transient int modCount;
   //threshold的最大值
   static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
   //计算hash值时候用，初始是0
   transient int hashSeed = 0;

​ 其中我们要着重讨论一下size、capacity、loadFactor、threshold这几个变量。

​ capacity就是当前可以容纳的最大数量，size表示当前实际“KV对”数量。需要注意的是，capacity的大小为2的幂，当我们使用HashMap(int initialCapacity)来初始化容量的时候，jdk会默认帮我们计算一个相对合理的值（第一个比他大的2的幂）当做初始容量。

​ HashMap有扩容机制，就是当达到扩容条件时会进行扩容，从16扩容到32、64、128…

​ 那么，这个扩容条件指的是什么呢？

​ HashMap的扩容条件就是当HashMap中的元素个数size超过临界值threshold时就会自动扩容。

​ 公式为：threshold = loadFactor * capacity。

内部类Entry:

//hashmap中每一个键值对都是存在Entry对象中，entry还存储了自己的hash值等信息
static class Entry<K,V> implements Map.Entry<K,V> {
       //键
       final K key;
       //值
       V value;
       //数组中每一项可能存储多个entry，而这些entry就是已链表的形式被存储，此next指向下一个entry
       Entry<K,V> next;
       //本entry的hash值
       int hash;    
   //...省略...
}

３．构造方法

​ 我们在这里只介绍传入容量和负载因子的构造方法。

public HashMap(int initialCapacity, float loadFactor) {
       //初始容量不能小于0
       if (initialCapacity < 0)
           throw new IllegalArgumentException("Illegal initial capacity: " +
                   initialCapacity);
       //初始容量不能大于默认的最大容量
       if (initialCapacity > MAXIMUM_CAPACITY)
           initialCapacity = MAXIMUM_CAPACITY;

       //负载因子不能小于0，且不能为“NaN”（NaN（“不是一个数字（Not a Number）”的缩写））
       if (loadFactor <= 0 || Float.isNaN(loadFactor))
           throw new IllegalArgumentException("Illegal load factor: " +
                   loadFactor);
       //将传入的负载因子赋值给属性
       this.loadFactor = loadFactor;
       /**
        * 此时并不会创建容器，因为没有传具体值。
        * 当下次传具体值的时候，才会“根据这次的初始容量”，创建一个内部数组。
        * 所以此次的初始容量只是作为下一次扩容（新建）的容量。
        */
       threshold = initialCapacity;
       
       //该方法只在LinkedHashMap中有实现，主要在构造函数初始化和clone、readObject中有调用。
       init();
   }

​ 我们需要注意，HashMap在new后并不会立即分配数组,而是第一次put时初始化,类似ArrayList在第一次add时分配空间。

４．put()方法

/**
   * 存入一个键值对，如果key重复，则更新value
   * @param key 键
   * @param value 值
   * @return 如果存的是新key则返回null，如果覆盖了旧键值对，则返回旧value
   */
  public V put(K key, V value) {
      //如果数组为空，则新建数组，这时同时初始化容量
      if (table == EMPTY_TABLE) {
          inflateTable(threshold);
      }

      //如果key为null，则把value放在table[0]中
      if (key == null)
          //如果有则覆盖了旧value，则返回value，否则返回null
          return putForNullKey(value);

      //生成key所对应的hash值
      int hash = hash(key);

      //根据hash值和数组的长度找到：该key所属entry在table中的位置i
      int i = indexFor(hash, table.length);

      /**
       * 数组中每一项存的都是一个链表，
       * 先找到i位置，然后循环该位置上的每一个entry，
       * 如果发现存在key与传入key相等，则替换其value。然后结束侧方法。
       * 如果没有找到相同的key，则继续执行下一条指令，将此键值对存入链表头
       */
      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;
          }
      }

      //map操作次数加一
      modCount++;

      //查看是否需要扩容，并将该键值对存入指定下标的链表头中
      addEntry(hash, key, value, i);

      //如果是新存入的键值对，则返回null
      return null;
  }

inflateTable(threshold)方法：

​ 该方法是新建一个空的内部数组。

/**
  * 新建一个空的内部数组
  * @param toSize 新数组容量
  */
 private void inflateTable(int toSize) {
     //内部数组的大小必须是2的n次方，所以要找到“大于”toSize的“最小的2的幂”
     int capacity = roundUpToPowerOf2(toSize);

     //下次扩容临界值
     threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
     
     table = new Entry[capacity];
     //capacity根据初始化hashseed
     initHashSeedAsNeeded(capacity);
 }

roundUpToPowerOf2(int number)方法：

​ 找到number的最小的２的幂。

private static int roundUpToPowerOf2(int number) {
	/*
	当 1 < number < MAXIMUM_CAPACITY 时；
	进行highestOneBit((number - 1)处理，得到大于number的最下２的幂
	*/    
	return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ?　 Integer.highestOneBit((number - 1) << 1) : 1;
}

Integer.highestOneBit(int i)方法：

​ 用来获取最左边的bit（其余位为０）所代表的值。

/*
此方法使用　移位　和　或运算　来实现的
首先我们需要知道
1 | X = 1, 0 | X = X
我们假设一个整数n的二进制为：１XXX XXXX (X表示可１可０)
step 1 : i = 1XXX XXXX | 01XX XXXX = 11XX XXXX
step 2 : i = 11XX XXXX | 0011 XXXX = 1111 XXXX
step 3 : i = 1111 XXXX | 0000 1111 = 1111 1111
step 4 : i = 1111 1111 | 0000 0000 = 1111 1111
step 5 : i = 1111 1111 | 0000 0000 = 1111 1111
step 6 : 1111 1111 - 0111 1111 = 1000 0000
我们知道前五步是将n从最高位开始全部置为１
第６步是将n变成只有最高位为１
*/
	public static int highestOneBit(int i) {
        //step 1
        i |= i >> 1;
        //step 2
        i |= i >> 2;
        //step 3
        i |= i >> 4;
        //step 4
        i |= i >> 8;
        //step 5
        i |= i >> 16;
        return i - (i >>> 1);
    }

hash(Object key)方法

​ 在HashMap中元素找到存储位置需要经过：Key->hashCode->hash->index。hash值是通过key自己的hashcode来得到的。

​ 我们知道一般hashcode的位数比数组的长度要大，进行&操作时，往往只能低位进行运算，这样就会增加哈希冲突，所以在hash()中通过移位和异或操作加入高位计算。

final int hash(Object k) {
       //相当于一个开关，hashSeed = 0时为关
    	int h = hashSeed;

       //如果key是字符串类型，就使用stringHash32来生成hash值
       if (0 != h && k instanceof String) {
           return sun.misc.Hashing.stringHash32((String) k);
       }
	/*
	这也是我们平常说的扰动算法。
	*/
       //一次散列
       h ^= k.hashCode();

       //二次散列
       h ^= (h >>> 20) ^ (h >>> 12);
       return h ^ (h >>> 7) ^ (h >>> 4);
   }

indexFor(int h, int length)方法：

​ 返回hash值的索引，采用除模取余法，h & (length-1)操作等价于hash % length操作， 但&操作性能更优，不需要转成十进制。这时，就与容量要是２的幂有关系，之后会详细解答。

static int indexFor(int h, int length) {
    //除模取余,相当于hash % length，&速度更快
    return h & (length-1);
}

用位运算来代替取模运算，除了性能问题以外，还解决了负数问题。由于hashcode是int类型，有正有负，负数取模比较麻烦。使用二进制的位运算，不管hashcode是正还是负，length-1为正，则其二进制第一位为０，做按位＆运算，结果一定为正。

addEntry(int hash, K key, V value, int bucketIndex)

​ 查看是否需要扩容，然后插入新节点，注意新节点插入在链表头。

 /**
     * 查看是否需要扩容，然后添加新节点
     * @param hash key的hash值
     * @param key 结点内key
     * @param value 结点内value
     * @param bucketIndex 结点所在的table下标
     */
void addEntry(int hash, K key, V value, int bucketIndex) {
        //如果当前键值对数量达到了临界值，并且下标位置不为空，则扩容table
        if ((size >= threshold) && (null != table[bucketIndex])) {
            //容量扩容一倍
            resize(2 * table.length);
            //由于数组扩容了，重新计算hash值
            hash = (null != key) ? hash(key) : 0;
            //重新计算存储位置
            bucketIndex = indexFor(hash, table.length);
        }

        //将键值对与他的hash值作为一个entry，插入table的指定下标中的链表头中
        createEntry(hash, key, value, bucketIndex);
    }

​ 整个put的过程以及当中用到的几个重要的方法讲解结束，接下来我们顺着讲解扩容过程。

５．resize()

​ 我们上面学习了数组扩容的条件，数组扩容的大小，由于默认initHashSeedAsNeeded内开关都是关闭状态，所以一般情况下transfer不需要进行rehash，能减少一部分开销。

​ 我们现在详细看一下其源码的实现：

/**
    * 对数组扩容，即创建一个新数组，并将旧数组里的东西重新存入新数组
    * @param newCapacity 新数组容量
    */
   void resize(int newCapacity) {
       Entry[] oldTable = table;
       int oldCapacity = oldTable.length;

       //如果当前数组容量已经达到最大值了，则将扩容的临界值设置为Integer.MAX_VALUE(Integer.MAX_VALUE是容量的临界点)
       if (oldCapacity == MAXIMUM_CAPACITY) {
           threshold = Integer.MAX_VALUE;
           return;
       }

       //创建一个扩容后的新数组
       Entry[] newTable = new Entry[newCapacity];

       //将当前数组中的键值对存入新数组,initHashSeedAsNeeded根据内部数组长度初始化hashseed
       transfer(newTable, initHashSeedAsNeeded(newCapacity));

       //用新数组替换旧数组
       table = newTable;

       //计算下一个扩容临界点
       threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
   }

transfer(Entry[] newTable, boolean rehash)

​ 将现有数组中的内容重新通过hash计算存入新的数组。

​ 采用了单链表头插入方式，同一个位置上的新元素总会被放在链表的头部位置。

/**
 * 将现有数组中的内容重新通过hash计算存入新数组
 * @param newTable 新数组
 * @param rehash
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    //遍历现有数组中的每一个单链表的头entry
    for (Entry<K,V> e : table) {
        //查找链表里的每一个entry
        while(null != e) {
            Entry<K,V> next = e.next;
            //默认情况是不需要 rehash 的
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }

            //根据新的数组长度，重新计算此entry所在下标i
            int i = indexFor(e.hash, newCapacity);

            //将entry放入下标i处链表的头部（将新数组此处的原有链表存入entry的next指针）
            e.next = newTable[i];

            //将链表存回下标i
            newTable[i] = e;

            //查看下一个entry
            e = next;
        }
    }
}

四、总结：

​ 简单介绍了关于HashMap、哈希表相关知识，以及基于JDK1.7分析其源码，减少了其中几个主要的方法。

（JDK1.7）

1. HashMap在new后不会立即分配数组空间，而是在第一次put时，通过inflateTable方法，同时第一次初始化容量也是在这时。

2. HashMap的数组大小一定是２的幂，初始默认大小为１６，如果自己new的时候传入的容量大小不是２的幂，会通过roundUpToPowerOf2方法算出大于指定容量的最下２的幂。

3. 扩容条件是size >= capacity * loadFactor，扩容大小为原容量的２倍。

4. HashMap处理哈希碰撞使用链地址法，使用头插法。

   之后会带来《解析HashMap（二）——基于JDK1.8》。