基本属性

常量

// 默认初始容量，1左移4位，即16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量 2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
// 负载因子，用来与容量一起计算 扩容阈值
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 树化阈值
static final int TREEIFY_THRESHOLD = 8;
// 取消树化阈值，即 链表长度小于6后，树结构转化为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 树化时最小容量，即总容量超过64，且链表长度超过8，才开始树化
static final int MIN_TREEIFY_CAPACITY = 64;

成员变量

// hashmap 本质是一个数组，数组内的元素是Node，Node中包含 K，V
transient Node<K,V>[] table;
// map.entrySet() 返回的值，用于遍历
transient Set<Map.Entry<K,V>> entrySet;
// 元素的数量
transient int size;
// 当前哈希表结构修改次数，只计算添加元素，替换元素不算
transient int modCount;
// 扩容阈值  （capacity * loadFactor）
// 当hash表中元素超过阈值时，触发扩容
int threshold;
// 负载因子，用于计算扩容阈值
final float loadFactor;

在 HashMap 结构中，数据通过 Node<K, V>的结构进行存储

static class Node<K,V> implements Map.Entry<K,V> {
        // 经过扰动函数后 计算出的 hash值
        final int hash;
        // 存储的key
        final K key;
        // 存储的value
        V value;
        // 同一个位置 下一个节点
        Node<K,V> next;
        ...
    }

构造方法

// 默认构造方法，指定负载因子为0.75
// 没有初始化数组
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

// 指定容量，负载因子的构造方法
public HashMap(int initialCapacity, float loadFactor) {
    // 参数合法性校验
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    // 扩容阈值，这里虽然设置的是扩容阈值，但实际是设置的数组大小，后面resize会解释
    this.threshold = tableSizeFor(initialCapacity);
}

// 返回一个数值，满足 大于等于当前值，且是2的次方数
static final int tableSizeFor(int cap) {
      int n = cap - 1;
      n |= n >>> 1;
      n |= n >>> 2;
      n |= n >>> 4;
      n |= n >>> 8;
      n |= n >>> 16;
      return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  }

这里有个注意的点，根据传入的的初始大小，经过计算，得出大于当前值最小的2的次方数
这里将这个指赋值给了 threshold （扩容阈值），在后面初始化时，扩容阈值会当做目标数组大小

为什么要将hashmap数组的大小必须是2的n次方？

hashmap的路由算法 是 位运算，hash & (n-1)，当n为 2的次方数时，& 运算等价于 取模运算

put方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
// 扰动函数，计算hash值，目的是将当前key的hashcode 的高16位也参与计算
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

put 元素时，将key元素的hashCode 经过扰动函数处理，得到一个新的hash值

== 扰动函数是什么？为什么需要扰动函数？==

如果没有扰动函数，路由算法就变为了 key.hashCode & (n-1)
然而大多数情况下，n的值都很小，比如默认的16。
0100 1001 1001 1101 （key.hashCode）
& 0000 0000 0000 1111 （n-1）
————————————
0000 0000 0000 1101
可以看出 hashCode 只有后4位参与了运算

为了让数据更加分散，尽可能降低出现hash冲突的概率，hashmap设计了扰动函数
经过 让 hashCode 的高16位 和 低16位 进行异或，这样低16位就包含了高16位的特征
再经过 路由算法，就会得到更散列的数据。

hashmap 可以存储 null值吗？

经过扰动函数，如果key为 null ，返回的hash值为0，再经过 路由算法，0 &（n-1） 为 0
所以，hashMap可以存储null，并且存储 索引为0 的位置

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    //tab : 当前map中的散列表
    //p: 当前散列表的元素
    //n: 当前散列表数组的长度
    //i: 路由寻址的结果，即要存放桶的位置
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 懒加载，第一次put的时候 初始化table数组
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash  即路由算法。找到应该存放的位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 如果没有hash冲突，直接构建node对象放在这个桶里
        tab[i] = newNode(hash, key, value, null);
    else {
        // 如果有hash冲突
        // e: 与当前key冲突的node元素
        // k: 与当前key冲突的node元素的key
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 当前插入的key与桶中的key相等
            e = p;
        else if (p instanceof TreeNode)
            // 如果 不相等且是树
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 如果不相等 且不是树结构，那就是链表
            // 遍历链表，找与当前key相等的链表元素，进行替换
            for (int binCount = 0; ; ++binCount) {
                // 没找到相同的，说明要插入链表的末尾
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果链表长度超过 阈值，进行树化（不一定树化，元素小于64只会扩容）
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //需要替换
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 留下的模板方法，供用户 重写
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //如果不是替换数据，而是添加数据
    ++modCount;
    //如果元素数 大于 扩容阈值，触发扩容
    if (++size > threshold)
        resize();
    // 留下的模板方法，供用户 重写
    afterNodeInsertion(evict);
    return null;
}

put方法的执行流程

1. 获取K的hash值
2. 经过hash扰动函数，使hash值更散列： 让key的hashcode值的高16位也参与运算， 因为路由算法是根据数组长度进行路由的，前期数组长度很小，二进制高16位都是0，没有参与运算
3. 构造Node对象，{hash，key，value， next}
4. 经过路由算法，找出node所存放的位置 ((table.length-1） & node.hash）
5. 如果当前桶为null，说明没有hash冲突，直接存入当前位置
6. 如果当前桶有值，出现hash冲突，如果当前节点已经是树，直接插入红黑树
7. 如果不是树，找到与当前key相等的数据进行替换
8. 如果没有找到相等的数据，则判断是否达到树化阈值（总元素个数>64 & 链表长度>8）
9. 没有达到树化阈值，插入链表尾部。

== 如何解决的哈希冲突 ==

jdk1.7 使用 链表的方式 ，jdk1.8使用链表+红黑树方式，进一步优化查询效率

resize 方法（扩容）

目的： 解决哈希冲突导致的链化严重问题

final Node<K,V>[] resize() {
    // 扩容前的哈希表
    Node<K,V>[] oldTab = table;
    // 扩容前table数组长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 扩容前的阈值
    int oldThr = threshold;
    // 扩容后的数组长度，扩容只会的阈值
    int newCap, newThr = 0;

    
    if (oldCap > 0) {// 说明hash表已经初始化了
        //老数组长度已经到达最大值，不扩容，之后也不扩容了
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 构造方法保证了oldCap是2的整数次幂，所以后面只需要进行2倍变化
        //newCap 为oldCap的2倍,如果老容量大于 16 ，则扩容阈值也翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 还没初始化
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 有oldThr，说明创建hashMap对象时使用的是有参构造方法
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 使用默认无参构造创建的hashMap的初始化，默认容量为16，阈值为12
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //设置newThr
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;

    // 开始扩容
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 如果之前已经初始化了，oldTab中有数据，需要将oldTab中的数据存入newTab
    if (oldTab != null) {
        // 遍历数组
        for (int j = 0; j < oldCap; ++j) {
            // 当前节点
            Node<K,V> e;
            
            if ((e = oldTab[j]) != null) {// 如果当前桶位中有数据
                //方便jvm回收
                oldTab[j] = null;
                if (e.next == null)
                    //如果当前桶只有一个数据，即没有链化，直接计算新的位置进行复制
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 如果已经树化了，
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 如果已经链化
                    //低位链表
                    Node<K,V> loHead = null, loTail = null;
                    //高位链表
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        
                        if ((e.hash & oldCap) == 0) {
                            // 例如 oldCap =16 ，值为0 说明2进制第4位为0
                            // 之前是 & oldCap -1 已经知道了 后四位
                            // 现在只需要 & oldCap 确定第5位是不是1，如果是1 则在高位链表
                            // 放低位链表
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            // 放高位
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    //把链表放到对应的位置
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}