本文从HashMap的原理出发引出面试问题，一共介绍六个大问题，里面包含连环追问的几个小问题。

0.哈希表

根据设定的哈希函数及处理冲突的方法将查找表中各数据元素存储在一段有限的连续空间中，即得哈希表。

哈希表又称为散列表，它通过将关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。

哈希函数（Hash Function）

哈希表能快速添加和查找元素的核心原因就是哈希函数，哈希函数能快速将一个数值转换成哈希值（整数）。所以哈希表必须保持哈希值的计算一致，如果两个哈希值是不相同的，那么这两个哈希值的原始输入也是不相同的。

哈希函数是人为构造的，构造的哈希函数应尽可能理想，尽可能一一对应。存储位置 = f(关键字)

常见的构造哈希函数的方法有直接定址法、数字分析法、平方取中法等。

如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？

当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀，但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。

那么哈希冲突如何解决呢？

哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式。

1.HashMap的数据结构

jdk1.7以前的存储结构是数组+链表，到了jdk1.8变成了数组+链表+红黑树。

//HashMap的主干数组，可以看到就是一个Entry数组，初始值为空数组{}，主干数组的长度一定是2的次幂。
//至于为什么这么做，后面会有详细分析。
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

假如一个数组槽位上链上数据过多（即拉链过长的情况）导致性能下降该怎么办？

JDK1.8在JDK1.7的基础上针对增加了红黑树来进行优化。即当链表长度超过8，数组长度超过64时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。查找效率会从链表的o(n)降低为o(logn)。

问题一：HashMap是怎么处理哈希冲突的？

HashMap由数组+链表组成的。Entry数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，当插入一个键值对时，如果定位到的数组位置不含链表（当前entry的next指向null），那么直接插入；如果定位到的数组包含链表，首先遍历链表，存在即覆盖，否则新增。

问题二：什么是红黑树呢？

红黑树是一个自平衡的二叉查找树，也就是说红黑树的查找效率是非常的高，查找效率会从链表的o(n)降低为o(logn)。

问题三：为什么不一下子把整个链表变为红黑树呢？

（1）构造红黑树要比构造链表复杂，在链表的节点不多的时候，从整体的性能看来， 数组+链表+红黑树的结构可能不一定比数组+链表的结构性能高。就好比杀鸡焉用牛刀的意思。

（2）HashMap频繁的扩容，会造成底部红黑树不断的进行拆分和重组，这是非常耗时的。因此，也就是链表长度比较长的时候转变成红黑树才会显著提高效率。

2.HashMap的put方法

• 调用put方法传入键值对
• 使用Hash函数计算hash值
• 根据hash值计算存放的位置(n - 1) & hash，判断是否和其他键值对位置发生了冲突
• 若没有发生冲突，直接存放在数组中即可
• 如果出现碰撞冲突了，则需要处理冲突：
• a.如果此时数据结构是红黑树，则调用红黑树的方法插入数据；
• b.否则采用传统的链式方法插入。如果链表的长度达到临界值，则把链表转变为红黑树；
• 如果已经存在重复的键，则为该键替换新值value；
• 插入完成后如果size大于阈值，则进行扩容；

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

首先计算出key的hashCode赋值给h,然后与h无符号右移16位后的二进制进行按位异或得到最后的hash值。

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

（1）hashCode()返回对象的内存地址：

public static void main(String[] args) {
    Map<String, Integer> mapp = new HashMap<>();
    String a="aaa";
    String b="bbb";
    System.out.println("a的hashCode值："+a.hashCode());
    System.out.println("b的hashCode值："+b.hashCode());
}

（2）h即为hashCode值，然后对它右移16位

右移16位的操作相当于前面补16个0

去掉后面的多余的即可。

然后对它们作异或操作

计算出hash值之后如何确定存放的位置？

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

hash值与（数组长度-1）做按位与操作。

最终位置为索引5。

整个流程如下图：

问题一：HashMap默认的初始化大小是多少？

如果new HashMap() 不传值，默认大小是16，负载因子是0.75， 如果自己传入初始大小k，初始化大小为大于k的 2的整数次方，例如如果传10，大小为16。

问题二：集合的初始化容量为什么必须是2的n次幂？

当向HashMap中添加一个元素的时候，需要根据key计算hash值，去确定其在数组中的具***置。 HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同。

因为HashMap通过hash & (length -1)来得到该对象的保存位，HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当 length 总是2的n次方时，hash & (length-1)运算等价于对length取模，也就是hash%length，但是&比%具有更高的效率。比如 n % 32 = n & (32 -1)。

问题三：为什么要这样操作呢？

如果当n即数组长度很小，假设是16的话，那么n-1即为 --->1111 ，这样的值和hashCode()直接做按位与操作，实际上只使用了哈希值的后4位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题。

问题四：插入的方式是什么？

java8之前是头插法，新来的值会取代原有的值，原有的值就顺推到链表中去，因为写这个代码的作者认为后来的值被查找的可能性更大一点，提升查找的效率。java8之后是尾插法。

因为1.7头插法扩容时，头插***使链表发生反转，多线程环境下会产生环；

比如A线程在插入节点B，B线程也在插入，遇到容量不够开始扩容，重新hash，放置元素，采用头插法，后遍历到的B节点放入了头部，这样形成了环，如下图所示：

3.HashMap的扩容方式？负载因子是多少？为什么是这么多？

loadFactor指的是负载因子，指能够承受住自身负载（大小或容量）的因子，默认值为 0.75，数组大小为 16，那么当HashMap中元素个数超过 16*0.75=12 的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，

当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。进行扩容，会伴随着一次重新hash分配，并且会遍历hash表中所有的元素。

HashMap在进行扩容时，使用的rehash方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 (length-1)&hash的结果相比，只是多了一个bit位，所以节点要么就在原来的位置，要么就被分配到"原位置+旧容量"这个位置。

因此，我们在扩容时，不需要重新计算hash值，只需要看看原来的hash值新增的那个bit是1还是0就可以了，是0的话索引没变，是1的话索引变成“原索引+oldCap(原位置+旧容量)”。可以看看下图为16扩充为32的resize示意图：

假设初始容量是16：

16扩容到32后：

正是因为这样巧妙的rehash方式，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，在resize的过程中保证了rehash之后每个桶上的节点数一定小于等于原来桶上的节点数，保证了rehash之后不会出现更严重的hash冲突，均匀的把之前的冲突的节点分散到新的桶中了。

4.HashMap的get()方法？

查找方法，通过元素的Key找到Value。

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

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //如果哈希表不为空并且key对应的桶上不为空
    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) {
            // 判断是否是红黑树，是的话调用红黑树中的getTreeNode方法获取节点
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // 不是红黑树的话，那就是链表结构了，通过循环的方法判断链表中是否存在该key
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

小结：

1.get方法实现的步骤：

• 1）通过hash值获取该key映射到的桶
• 2）桶上的key就是要查找的key,则直接找到并返回
• 3）桶上的key不是要找的key,则查看后续的节点：
• a:如果后续节点是红黑树节点，通过调用红黑树的方法根据key获取value
• b:如果后续节点是链表节点，则通过循环遍历链表根据key获取value

final TreeNode<K,V> getTreeNode(int h, Object k) {
            return ((parent != null) ? root() : this).find(h, k, null);
 }
 final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
            TreeNode<K,V> p = this;
            do {
                int ph, dir; K pk;
                TreeNode<K,V> pl = p.left, pr = p.right, q;
                if ((ph = p.hash) > h)
                    p = pl;
                else if (ph < h)
                    p = pr;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;//找到之后直接返回
                else if (pl == null)
                    p = pr;
                else if (pr == null)
                    p = pl;
                else if ((kc != null ||
                          (kc = comparableClassFor(k)) != null) &&
                         (dir = compareComparables(kc, k, pk)) != 0)
                    p = (dir < 0) ? pl : pr;
                //递归查找
                else if ((q = pr.find(h, k, kc)) != null)
                    return q;
                else
                    p = pl;
            } while (p != null);
            return null;
        }

3.查找红黑树，由于之前添加时已经保证这个树是有序的了，因此查找时基本就是折半查找，效率更高。

4.和插入一样，如果对比节点的哈希值和要查找的哈希值相等，就会判断key是否相等，相等就直接返回。不相等就从子树中递归查找。

5.若为树，则在树中通过key.equals(k)查找，O(logn) ；若为链表，则在链表中通过key.equals(k)查找，O(n)。

5.HashMap在jdk1.8做了哪些优化？

• 数组+链表改成了数组+链表或红黑树；
• 链表的插入方式从头插法改成了尾插法，简单说就是插入时，如果数组位置上已经有元素，1.7将新元素放到数组中，原始节点作为新节点的后继节点，1.8遍历链表，将元素放置到链表的最后；
• 扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；
• 在插入时，1.7先判断是否需要扩容，再插入，1.8先进行插入，插入完成再判断是否需要扩容；

6.HashMap线程安全吗？为什么？

HashMap不是线程安全的，在多线程环境下，jdk1.7 会产生死循环、数据丢失、数据覆盖的问题，jdk1.8 中会有数据覆盖的问题，以jdk1.8为例，当A线程判断index位置为空后正好挂起，B线程开始往index位置的写入节点数据，这时A线程恢复现场，执行赋值操作，就把A线程的数据给覆盖了；还有++size这个地方也会造成多线程同时扩容等问题。

线程安全的Map有HashTable、Collections.synchronizedMap、ConcurrentHashMap。

HashTable是直接在操作方法上加synchronized关键字，锁住整个数组，粒度比较大。

Collections.synchronizedMap是使用Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现。

ConcurrentHashMap使用分段锁，降低了锁粒度，让并发度大大提高。