以下面试题从看准，牛客，以及大量大厂面经中收集而来，面向真实面试。
一、面试题总览
面试题整理后分为三大模块，分别是数据结构，扩容以及线程安全，同样梳理HashMap的时候也可以从这三个角度展开。下面这些问题相信大家在面试过程中也会被经常问到，也很容易的回答出来。就我本身而言，每次面试的时候都会重新看一遍源代码，有时候还回去再找一些相应的题目，这其实浪费了很多时间，所以我想把这些都整理出来，供大家和自己复习，以后面试过程中使用。如果其中有什么问题，欢迎指正，留言交流，非常感谢。
1.数据结构
HashMap面试题
1.hashmap的数组长度为什么要保证是2的幂？(Hash表设计文章中已解答)
性能及空间利用率两点来回答。
位运算性能较取模运算快，其实可以不一定是2的幂，但这样会导致利用率较低。比如15，最后一位永远是0，任意hash值与其做与运算得到的索引永远是偶数，这样就会导致只有一半的利用率。所以为2的幂才是最合适的。
2.hashmap如何解决hash冲突？ 以及如果冲突了，怎么在hash表中找到目标值
链地址法以及红黑树。扩容
如果并没有达到树化条件，则直接扩容
判断是否产生冲突
判断是否为树
插入到链表尾部后，判断是否要进行树化。
首先计算hash值，定位桶位，判断桶中元素类型是Node还是TreeNode，如果是Node表明是链表，如果是TreeNode为红黑树结构，链表直接遍历，红黑树直接查找。
3.怎么尽量避免哈希冲突，自己说了充分利用对象的属性+良好的哈希算法，但是面试官还继续追问，自己好像也没有找到答案，扩容？？
4遇到哈希冲突的时候，除了数组+链表，还有什么处理方式
5.hashMap底层？为什么jdk1.8要用红黑树实现？什么时候会出现线程不安全？怎么解决线程不安全？默认初始容量是16，如果我改成7，容量会变成7么？为什么？
6.为什么hashmap中的链表需要转成红黑树？
7.jdk1.8之前并发操作hashmap时为什么会有死循环的问题？
由于前面确定了负载因子为0.75，在loadfactor为0.75时根据泊松分布，
8.HashMap 转成红黑树，8这个数字是怎么来的 泊松分布；退化为链表的6这个数字呢？
9.loadFactor为什么是0.75？
10.上来问项目，然后问hashmap每一步都问，印象最深的是为什么计算hash值要右移16位不是17位。还有设计原则。当时没背。凉凉
11.往HashMap插入删除数据，时间复杂度是多少
12.红黑树和链表那个增加快
13.怎么实现HashMap，定义需要的方法和API，时间复杂度不能为O(n)
14.HashMap 1.7为什么会导致死循环？
15.有1000个数据存在hashmap中，实际的数量是多少，考虑负载因子和扩容
16.Hashmap为什么不用平衡树？为什么用红黑树而不是B树，B+树，AVL树
17.HashMap HashTable区别 HashMap的优化
18.你都知道哪些Map，都在什么场景下使用？为什么？
19.hashmap为什么要重写hashcode和equls方法
20.说一说jdk1.8中，对hashMap的优化
21.红黑树和AVL树有什么区别？HashMap为什么不采用AVL树？
22.如何能提示HashMap的性能
预设hashmap的长度，避免resize，这也是问当确定了数据总量为1000，数组总长度应该是多少的原因
23.HashMap key可以为null,为什么ConcurrentHashMap key 不可以为null ?
ConcurrentHashMap不能为null原因,无法去判断到底是key不存在还是value为null
24.hashmap初始大小 1>4 = 16;最大 1>30 即2的30次方；超过最大值如何处理？
25.resize是否要重新计算hash值？
26.java hashMap和redis map的rehash有什么区别？
27.HashMap 如何保证容量一直是2的N次方，如果构造函数传的不是2的n次方呢？
28.JAVA8 的 HashMap 中 TREEIFY_THRESHOLD 常量为什么是 8 ?https://www.v2ex.com/t/651978
29.HashMap节点是有序的吗？了解哪些有序的Map？
HashSet面试题
1.HashSet的value是什么
2.HashSet为什么不存null？
hashMap的put方法，返回null表示新添加，返回oldValue表示覆盖。
2.扩容
1.hashmap什么时候会触发扩容？
2.hashmap扩容时每个entry需要再计算一次hash吗？
3.说一下hashmap的扩容机制吧
3.线程安全问题
1.java hashMap和redis map的rehash有什么区别？
2.如何才能得到一个线程安全的HashMap？
下面从源码的角度来分析和解答以上问题。
二、HashMap源码分析
版本JDK1.8，后面会分析JDK1.7中HashMap源码
1.默认数据
//默认初始容量16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //最大容量2^30static final int MAXIMUM_CAPACITY = 1 << 30;//默认负载因子 0.75static final float DEFAULT_LOAD_FACTOR = 0.75f;//需要树化的链表长度阈值static final int TREEIFY_THRESHOLD = 8;//需要树化的时候，数组元素最小个数static final int MIN_TREEIFY_CAPACITY = 64;//树退化为链表的树节点数量static final int UNTREEIFY_THRESHOLD = 6;//存储数据数组transient Node[] table;//entry 集合transient Set> entrySet;//实际存储元素个数transient int size;//结构性修改计数transient int modCount;//扩容阈值int threshold;//负载因子final float loadFactor;如果是链表结构，则桶中数据类型为Node
static class Node<K,V> implements Map.Entry<K,V> { //存储hash值，避免多次运算 final int hash; final K key; V value; //下一个元素的引用 Node next; Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry,?> e = (Map.Entry,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; }}如果已经转变为红黑树，则桶中元素类型为TreeNode
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { //父结点 TreeNode parent; // red-black tree links //左子节点 TreeNode left; //右子节点 TreeNode right; TreeNode prev; // needed to unlink next upon deletion //是否为红色 boolean red; TreeNode(int hash, K key, V val, Node next) { super(hash, key, val, next); }}2.构造函数
(1)默认无参构造
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}这种实例化方式是最常见的，默认指定了初始容量为16，负载因子为0.75
(2)指定初始容量及负载因子
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); //这里仅仅是设置了threshold，并没有设置capacity属性 this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity);}如果指定了初始容量，由于HashMap的capacity都是2的幂，所以需要找到大于等于给定初始容量的最小的2的幂，若给定的初始容量就是2的幂，则该方法返回的就是该值。
/** * Returns a power of two size for the given target capacity. */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;}这段代码的逻辑就是将给定容量中第一个出现1 的后面所有位都置为1，如图所示：
注意，得到的这个capacity却被赋值给了threshold。
this.threshold = tableSizeFor(initialCapacity);而不是这样：
this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;这样才符合threshold的意思(当HashMap的size到达threshold这个阈值时会扩容)。但是，请注意，在构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算。
3.增加元素方法
public V put(K key, V value) { //根据key计算hash值 return putVal(hash(key), key, value, false, true);}static final int hash(Object key) { int h; //高低位做异或运算，保留高低位的特征;前面的文章也已经提到过,这里不再过多赘述 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}1.真正的插入数据的方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) //1.如果数组为null或者数组长度为0，resize方法做初始化的工作,并返回数组新的长度 n = (tab = resize()).length; //2.通过hash值与table.length-1 计算索引，获取索引位上的元素。 //如果该索引位置元素不存在,则插入元素,反之走else逻辑; //(注意点1：key为null的值存储在桶中也是用Node进行包装的，所以key为null的节点并不为null)， //(注意点2：newNode方法中hash属性保存了key的hash值，该hash值是经过扰动函数计算后的，防止后面重复计算hash值) if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; //3.如果该索引位置的元素已存在即发生冲突，且key的hash与该索引位置的元素key的hash相等， //并且该key与桶中元素的key相等或key符合equal，则将桶中旧元素赋值给e，最后面做value的替换 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) //4.如果已经树化，则走红黑树节点的添加逻辑;红黑树会单独讲解 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { //5.否则走链表添加逻辑 for (int binCount = 0; ; ++binCount) { //遍历链表直到到链表尾部，将新元素插入到链表尾部 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //如果桶中元素的链表长度大于等于 7,并且数组中元素总量大于等于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; } } //6.第三步中e保存的是该位置桶中元素，做value的覆盖,返回旧值 if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } //增加结构修改计数 ++modCount; //如果当前数组存储元素超过扩容阈值，则进行扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null;总结：添加元素的逻辑
通过key的hash算法以及寻址算法定位到索引，通过索引找到桶中元素；
若该元素不存在
-
直接实例化一个Node并放入该位置；
若该元素存在
-
判断桶中元素key与当前key是否一致，若一致则替换value；
-
如果桶中元素类型是TreeNode，表明已经树化，则走红黑树添加操作。
-
其他情况则为链表结构，从头到尾遍历链表。如果在链表中找到某个key与当前key相同，则覆盖value；否则将新Node添加到链表尾部。如果链表长度大于等于树化阈值8，且数值中元素数量大于等于64则将链表转换为红黑树。
最后如果数值中size超过扩容阈值，则进行扩容及数据迁移。
2.对数据进行初始化以及扩容方法
基于高低位链表,当前节点数组下标元素rehash不变或+旧的容量,存在线程安全问题和fail-fast.
final Node[] resize() { Node[] oldTab = table; //1.如果数组没有被初始化，则旧数组容量为0，反之为真实容量 int oldCap = (oldTab == null) ? 0 : oldTab.length; //2.旧数组的扩容阈值 int oldThr = threshold; //3.新数组的容量及扩容阈值 int newCap, newThr = 0; //4.如果旧数组容量大于0，表明该旧数组已被初始化 if (oldCap > 0) { //如果旧数组容量超过数组最大容量，则扩容阈值为int最大值，后面也不会再扩容 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //反之将旧数组容量*2作为新的数组容量， //如果该值小于数组最大值且旧数组容量大于等于16， //新数组的阈值同样为旧数组扩容阈值*2 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } //5.能进入下面这段分支表示数组尚未被初始化；将threshold作为capacity else if (oldThr > 0) newCap = oldThr; else { //6.到这里表明capacity以及threshold都未被设置；走默认值 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //7.如果新数组扩容阈值为0 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; //8.使用新容量初始化一个新数组,开始数据的迁移 Node[] newTab = (Node[])new Node[newCap]; table = newTab; if (oldTab != null) { //对旧数组的每一个有元素的索引位进行迁移； for (int j = 0; j < oldCap; ++j) { Node e; if ((e = oldTab[j]) != null) { oldTab[j] = null; //如果该位置没有链表结构，则将该元素与新数组length-1 进行与运算获取索引，并将其放到该索引位置 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; //如果该元素是树形节点，涉及到红黑树的操作会单独写一篇文章 else if (e instanceof TreeNode) ((TreeNode)e).split(this, newTab, j, oldCap); else { //9.重点关注这里基于高低链表对旧链表数据的迁移过程。 Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; do { next = e.next; if ((e.hash & oldCap) == 0) { 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;}初始化及扩容的逻辑比较简单，重点关注数据迁移的过程。
关键词：高低链表
假设原数组长度为16，做与运算实际有效位只有16位，对应二进制为：0000 0000 0000 0000 1111 1111 1111 1111扩容后数组长度变为32，做与运算实际有效位只有17位，对应二进制为：0000 0000 0000 0001 1111 1111 1111 1111观察16和32的二进制发现仅仅只有一位不同。这里模拟key1与key2 hash冲突，放在同一个链表上。假设key1的hash值为(旧元素的Node节点中hash存储的是已经经过扰动函数计算的)1010 0010 1110 0111 0000 0000 0000 0000与16的二进制做与运算，结果：0000 0000 0000 0000 0000 0000 0000 0000key2的hash值为：1011 0010 1110 0110 0000 0000 0000 0000与16的二进制做与运算，结果：0000 0000 0000 0000 0000 0000 0000 0000可见key1和key2的寻址算法的结果相同，所以它们被放在同一个链表上。这时候数据迁移后，数组长度为32，key1与32的二进制做与运算结果：0000 0000 0000 0001 0000 0000 0000 0000key2与32的二进制做与运算结果：0000 0000 0000 0000 0000 0000 0000 0000可见新的索引只会有一位不同，所以key的hash值的第16位为1，新的索引就是旧索引*2；如果第16位为0，新索引就等于旧索引。思路就是新建两个链表，通过遍历旧链表中元素，将不同元素挂到高低链表上，假设元素的hash值的第16位为1，就将其追加到高链表；如果第16位为0，则追加到低链表上。高链表直接挂到[老索引值*2]的位置，低链表挂到新数组索引位[老索引值]的位置(e.hash & oldCap)=0：这行关键代码就是用来判断第16位的值是0还是1因为oldCap是2的n次幂的整数,其二进制表达为1个1后面跟n个0：1000…0，若想要e.hash&oldCap的结果为0，则e.hash的二进制形式中与对应oldCap的二进制的1的位置一定为0，其他位置的可以随意，这样即可保证结果为0；假设：oldCap= 2 ^ 3 =8 = 1000则e.hash可以是 01014.JDK8的优化
1.8还有三点主要的优化：
(1) 结构增加了红黑树；
(2) 链表的插入方式从头插法改成了尾插法
(3) 1.7数据迁移需要重新hash和寻址；1.8扩容后索引要么是原索引要么是原索引+旧容量大小。
(4) 在插入时，1.7先判断是否需要扩容，再插入，1.8先进行插入，插入完成再判断是否需要扩容；
(1)为什么要引入红黑树？
原因：JDK7中的hashmap 假设极端情况下hash碰撞非常严重，某个桶位的链表非常长，查找效率为O(n)，效率较低。
而红黑树插入为O(logn),查询为O(logn)，链表插入为O(1)，查询为O(n)。个数少时，插入删除成本高，用链表；个数多时，查询成本高，用红黑树。需要定一个值，比这个值大就转红黑树，比这个值小就转链表，而且要避免频繁的转换。根据泊松分布，在负载因子0.75(HashMap默认)的情况下，单个hash槽内元素个数为8的概率小于百万分之一，将7作为一个分水岭，等于7时不做转换，大于等于8才转红黑树，小于等于6才转链表。
(2)为什么不采用AVL树或B树，B+树？
(3)为什么树化阈值是8？为什么树退化为链表的阈值是6？
当loadfactor为0.75时，根据泊松分布可以如下数据，表示的是链表不同长度所对应的概率。
* 0: 0.60653066* 1: 0.30326533* 2: 0.07581633* 3: 0.01263606* 4: 0.00157952* 5: 0.00015795* 6: 0.00001316* 7: 0.00000094* 8: 0.00000006* more: less than 1 in ten million可以看到当链表长度为8时候的概率为千万分之6，概率极低。所以取该值作为树化阈值。
为什么取6不取7呢？
至于为什么转回来是6，因为如果hash碰撞次数在8附近徘徊，会一直发生链表和红黑树的转化，为了预防这种情况的发生。
(1)假设当前某个桶位有8个元素，此时已经是红黑树结构，假设这时候删除一个元素，就立马转换为链表，然后该桶位发生冲突后又添加一个元素，又转变为红黑树，有很大的性能消耗。
(2)6和8 概率差距较大，且都不易达到。
(4)为什么JDK8 中链表采用尾插法而不是头插法？
因为1.7头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环；
A线程在插入节点B，B线程也在插入，遇到容量不够开始扩容，重新hash，放置元素，采用头插法，后遍历到的B节点放入了头部，这样形成了环.
三、HashMap线程安全问题
不是，在多线程环境下，1.7 会产生死循环、数据丢失、数据覆盖的问题，1.8 中会有数据覆盖的问题，以1.8为例，当A线程判断index位置为空后正好挂起，B线程开始往index位置的写入节点数据，这时A线程恢复现场，执行赋值操作，就把A线程的数据给覆盖了；还有++size这个地方也会造成多线程同时扩容等问题。
线程安全的Map：
HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以实现线程安全的Map。
HashTable是直接在操作方法上加synchronized关键字，锁住整个数组，粒度比较大，Collections.synchronizedMap是使用Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现；ConcurrentHashMap使用分段锁，降低了锁粒度，让并发度大大提高。
下一篇会介绍LinkedHashMap以及LRU算法的实现.