结构

HashMap内部是通过数组+链表的方式实现哈希表的结构，如图。

image.png

HashMap会将key和value包装在Entry实体中，put数据时计算key的hash值，然后将hash和数组长度-1按位与计算出当前Entry对应的下标index，如果index处没有数据，则直接该Entry放入数组中指定位置，否则便发生了哈希碰撞，则该Entry插入到链表的头部。

哈希碰撞
求对象的哈希值，计算出来有一些对象的哈希值相同时，这种现象就叫做哈希碰撞。

源码分析

成员变量

//初始化数组容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//数组容量最大值
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载因子：
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//空数组
static final Entry<?,?>[] EMPTY_TABLE = {};
//HashMap的table数组，其长度必须是2的幂次
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//HashMap键值对个数
transient int size;
//扩容阈值
int threshold;
//加载因子
final float loadFactor;

put插入数据

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);
    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;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

当数组table为空时，创建数组
```
private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}
```
- 由于初始化HashMap时可以指定数组容量，如果传入的数值不是2的幂次，这里就找到一个比它大的2的幂次。
- 计算出阈值，阈值 = 容量 * 加载因子，即到达这个阈值时数组就要扩容。
- 最后初始化table数组。
HashMap允许key为空，当key为空时，对应数组的index = 0。
计算key的hash，并计算对应的数组下标index。
遍历该下标index下的链表，如果key已经存在，则覆盖原来的value值。

如果该key不存在，则新建一个Entry对象。

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

如果容量大于阈值了，此时需要扩容，扩容大小为原来数组长度的2倍，扩容后将旧数组中的数据转移到新数组中。

计算当前元素的hash以及数组的index，采用头插法插入到对应index下的链表上。

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

get获取数据

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

根据传入的key获取Entry对象

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

首先计算传入key的hash值。
遍历对应hash的index下面的链表，找到对应的Entry对象返回。
获取value值并返回。

jdk1.7HashMap存在的问题以及1.8的改进

1.7HashMap的问题

本身是线程不安全的，多线程下可能会出现死锁。

容易产生hash碰撞，退化成链表。

1.8HashMap的改进

基于数组+链表+红黑树实现的。

如果数组长度小于MIN_TREEIFY_CAPACITY = 64，会先扩容数组；当数组长度大于64时，如果链表上的结点数量到了树化阈值8，此时才会进行树化，链表化阈值为6。

面试题

为什么HashMap的容量是2的幂次？

hash & length - 1 计算得到index
```
hash :           0101 0101
length - 1(15) : 0000 1111 

hash & length - 1 = 0000 0101
```
我们发现2的幂次的长度-1的二进制低位都1，而高位都是0，这样在与hash值进行按位与时能够保证index的取值范围为 0 ~ length -1，刚好符合我们的要求。
HashMap默认容量是多少，加载因子是多少？

默认容量是1<<4 = 16，加载因子是0.75。
计算哈希值时为什么要对hashCode进行右移以及异或操作？

因为hashCode方法是可以重写的，如果我们重写的hash算法不好，会造成更多的哈希碰撞，右移以及异或可以让hashCode高位参与计算数组下标index的与运算中，这样可以让计算出的index分散更均匀，减少哈希碰撞。
遍历链表对比时，为什么先判断hash？

因为hash值不相等，那么两个对象肯定不相等，hash值相等，对象不一定相等，所以先判断hash值再equals效率更高。