专题目录
一、HashMap jdk1.7和jdk1.8
二、HashMap线程安全问题
[三、HashMap和Hashtable、CurrentHashMap、HashSet]
[四、重写equals方法 --可引申到对象拷贝问题]
[五、红黑树 --可引申到B+树]
[六、总结对HashMap的感悟 ]
注：idea看源码必备快捷键：
ctrl+F12(查看类参数和方法)、ctrl+H(查看类的上下继承关系树)

1.7 HashMap

前言

在理解Hash和扩容流程之前，我们得先了解下HashMap的几个字段。从HashMap的默认构造函数源码可知，构造函数就是对下面几个字段进行初始化，源码如下：

 int threshold;             // 所能容纳的key-value对极限 
 final float loadFactor;    // 负载因子
 int modCount;  
 int size;

1.7之前还没Node节点只用了Entry

//hashmap的内部类
static class Entry<K,V> implements Map.Entry<K,V> 
        final K key;
        V value;
        Entry<K,V> next;//指向下一个节点
        int hash;

首先，Entry<K,V>[] table的初始化长度length(默认值是16)，loadFactor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。

结合负载因子的定义公式可知，threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。

size这个字段其实很好理解，就是HashMap中实际存在的键值对数量。注意和table的长度length、容纳最大键值对数量threshold的区别。而modCount字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。

HashMap底层是哈希桶数组加链表实现的：

image.png

问题1：如何确定哈希桶数组索引位置

根据hash（key）来找到数组的下标，确定数组位置：

//链表节点的结构，1.7使用的是Entry,1.8使用的是Node
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
...
//hash是key的hash值，table.length是数组的长度
int i = indexFor(hash, table.length);
...
static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
      //值得大家思考：为什么要逻辑与？--另外专题
        return h & (length-1);
    }

根据map.put源码可以看出，对key进行hash操作求出一个int值，就是需要存放在数组所在的位置；因为存在hash碰撞问题，不能保证一个数组位置只放一个值，可能有多个key的hash值一样，所以选择链表方式解决这种问题

问题2：put流程，如何扩容resize？

image.png

分析下put源码：

/**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        //遍历链表， table[i]：链表头节点
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
          //这里是判断key重复，这里判断有个细节问题，值得大家考量：为什么要先判断hash值？
          //结论：1、两个对象的hash值不相等，那么这两个对象一定不相等；
          //     2、hash值相等，这两个对象一定相等吗？ 不一定！！！

            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                //返回被覆盖的value
                return oldValue;
            }
        }

        modCount++;
        //跟着走
        addEntry(hash, key, value, i);
        return null;
    }

进入addEntry方法：

/**
     * Adds a new entry with the specified key, value and hash code to
     * the specified bucket.  It is the responsibility of this
     * method to resize the table if appropriate.
     *
     * Subclass overrides this to alter the behavior of put method.
     */

    void addEntry(int hash, K key, V value, int bucketIndex) {
// 满足扩容的条件：1、size节点数>=table数组长度 
//2、当前数组上链表头节点不为null
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
          //key==null 放在数组第一位上
            hash = (null != key) ? hash(key) : 0;
          //求扩容后新的数组位置index
            bucketIndex = indexFor(hash, table.length);
        }
       //跟着走
        createEntry(hash, key, value, bucketIndex);
    }

进入addEntry方法：

/**
   * Like addEntry except that this version is used when creating entries
   * as part of Map construction or "pseudo-construction" (cloning,
   * deserialization).  This version needn't worry about resizing the table.
   *
   * Subclass overrides this to alter the behavior of HashMap(Map),
   * clone, and readObject.
   */
// 这里可以看出是1.7使用的是头插法
void createEntry(int hash, K key, V value, int bucketIndex) {
      Entry<K,V> e = table[bucketIndex];
      table[bucketIndex] = new Entry<>(hash, key, value, e);
    //累计元素个数 , 联想到map.size()
      size++;
  }

回到上一步分析下resize:

void resize(int newCapacity) {
        HashMap.Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        HashMap.Entry[] newTable = new HashMap.Entry[newCapacity];
        //核心：将原数据迁移到新的数组上
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

void transfer(HashMap.Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (HashMap.Entry<K,V> e : table) {
            while(null != e) {
                //先保存next节点数据
                // （因为迁移后 第一次next=null,迁移后的节点会倒置，而jdk8不会倒置）
                HashMap.Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                //使用头插法（头节点成为e的next节点）
                e.next = newTable[i];
                //e成为头节点
                newTable[i] = e;
                //指向next，继续迁移
                e = next;
            }
        }
    }

以上代码分析得出以下结论：
1、满足扩容的条件：size节点数>=table数组长度 ；当前数组上链表头节点不为null
2、扩容倍数2倍
3、1.7是先扩容后插入值，插入方式是头插法（此时如果选择尾插法，需要遍历链表，反而增加了复杂度，较低了插入的效率）

有疑问或有问题的请留言，希望可以与大家一起探讨源码学习进步！每天晚上都会更新我的技术点，下期补充1.8的区别，还有mysql索引底层原理...