一，HashMap的底层数据结构

Java8 中HashMap的底层数据结构是数组＋链表，当数组长度达到64或者链表长度达到8时，将会把链表转化为红黑树。

1.HashMap的存取原理

put方法

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 当前哈希表为空，则初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            // 直接调用resize方法，返回长度，默认16
            n = (tab = resize()).length;
        // index的计算方法 (n - 1) & hash n是tab的Leagth
        // 没有hash碰撞，则直接挂在tab[index]下
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            // 哈希值相等，key也equals相等，覆盖value
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 遍历链表插入
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 链表节点数量 >= 8 转化为红黑树
                        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;
                }
            }
            // e不是空，有需要覆盖的节点
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 空函数 Callbacks to allow LinkedHashMap post-actions
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 插入新节点完毕，修改modCount
        ++modCount;
        
        // 更新size 判断是否需要扩容
        if (++size > threshold)
            resize();
        // 空函数 Callbacks to allow LinkedHashMap post-actions
        afterNodeInsertion(evict);
        return null;
    }

get方法 

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

 // 传入扰动后的哈希值 和 key
 final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 链表头节点判断
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }

2.resize，扩容，以及重新hash(rehash)

什么时候resize？

HashMap的默认负载因子是0.75f，所以当HashMap数组的长度大于容量＊0.75的时候，会对HashMap进行resize处理。

扩容分为两步，

首先，创建一个新的Entry空数组，长度是原来数组的两倍。

然后，进行ReHash操作，遍历原Entry数组，把所有的Entry重新Hash到新数组。

resize后是一定需要进行rehash的，因为index的计算与数组的长度相关，长度扩大之后，hash计算出来的值自然就发生了变化，这个会在下面hash计算展开详细描述。

对应HashMap源码位于resize()方法707行，往新的数组放元素进行了rehash。

3.Java7的头插法与Java8的尾插法

为什么Java7采用头插法，而Java8却改成了尾插法？

头插法插入会改变链表的顺序，导致并发情况下可能出现环形链表的情况，而改为尾插法之后，由于新插入元素之后维持原来链表的顺序不变，不会有环形链表的情况出现，但是在并发的情况下，会出现值覆盖的情况。

二，HashMap的主要参数都有哪些？

/**
 * The default initial capacity - MUST be a power of two.
 * 初始化容量必须是2的次方
 */
// 默认初始化容量
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 int TREEIFY_THRESHOLD = 8;

// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;

// 树形化最小容量
static final int MIN_TREEIFY_CAPACITY = 64;

1.初始化容量为什么是16，为什么都要是2的次方？

为了实现数据的均匀分布。

首先了解index(HashMap底层是数组和链表)的计算规则，index = HashCode(Key) & (Length- 1) ,key的hash值与当前Node数组的长度做位运算。

奇数为什么不行？

由index的计算方法得知，Length为奇数，Length- 1为偶数，偶数二进制结尾都是0，经过＆运算后，index的末尾也都会时0，这样就会增加hash冲突。

2的倍数为什么不行？

2的幂数经过Length-1之后，二进制时二进制位全为1，这样计算的index等同于HashCode的后几位的值。

因为当Length为2的幂时，会满足(Length - 1) & hash = hash % Length，位运算的结果与取模的结果一直，index的计算效率更加高效。

2.默认负载因子为什是0.75？

负载因子:是哈希表在其容量自动扩容之前可以达到多满的一种度量。

首先看源码关于0.75有以下这样一段描述

关键内容是，分布良好的hash，树结构是很少用到的，理想情况下，节点服从泊松分布(Poisson distribution)，调整大小的参数平均是0.5，0.75与0.5差异很大，以为考虑调整粒度以及忽略方差。

总结来说，0.75作为默认的加载因子，是时间和空间成本上寻求的一种折衷选择。

0.5的话，虽然可以减少查询时间成本，但是空间的利用率过低，也就意味着会提高rehash操作的次数。

3.链表转红黑树的阈值为什么是8？

首先链表转红黑树是很消耗性能的，也就是说我们要尽可能减低树化的可能性。

还是上面的那张图，可以看到一个链表中达到8个元素的概率为 0.00000006，几乎是不可能事件，所以8应该是统计概率之后的最优选择。

三，HashMap中Hash的计算规则

1.HashMap是怎么处理hash碰撞的？

Hash碰撞或者Hash冲突，指的是计算hash之后所得的Index一致，即发生了hash碰撞，可以看下上面提到的头插法与尾插法，其实就是发生hash碰撞后如何添加数据的。

Java7中的解决办法是链表，Java8变成了链表+红黑树。

2.为什么重写equals方法时需要重写hashCode方法？

首先需要了解Object的hashCode和equals方法

通过源码我们可以很明显看出，hashCode方法返回的是一个整数，

而equals判断的是参数与当前对象thiis是否相等，这里的对象相等时比较对象的内存地址是否相同，如果内存地址相同，这两个对象相同。

所以，对象相等时，hashCode也一定相等，但是hashCode不同时，对象一定不相等，先比较hashCode可以减少equals比较次数，提高效率。

我们还知道，index的计算是index = HashCode(Key) & (Length- 1)，是与HashCode相关的，如果计算得出的index一致，那么就需要使用equals方法去确定同一个index位置的对象哪一个才是我们需要的那个对象。

总结来说，重写equals方法一定要重写hashCode方法是为了，保证不同的对象有不同的hashCode，相同的对象有同一个hashCode。

四，HashMap是否是线程安全

1.为啥会线程不安全？

Java7头插法并发情况下出现环形链表，transfer方法

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            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 = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

而Java8还是之前提到的putVal()方法，由于没有锁，当线程A和线程B同时执行put，

Thread A 下图625行判断了tab[index] 为null，可以插入，但是还没有插入时，没有时间片而暂时挂起，

此时线程B也同样进行插入操作，而且同一个tab[index]位置正常插入元素，

之后，Thread A 再次执行626行put操作，就会把Thread B插入的元素覆盖。

2.有什么线程安全的类可以替代？

a.Hashtable,对所有方法加锁（synchronized）,所有线程锁的都是当前对象，锁的粒度太大。

b.ConcurrentHashMap，get时没有锁，put时有锁，锁的粒度比较小。

c.Collection.SynchronizedMap，锁的是同一个对象，每次锁的都是当前整张表，锁的粒度太大。

五，HashMap的红黑树操作

还没整理，先送上一篇文章连接，https://zhuanlan.zhihu.com/p/80587365