HashMap常见面试问题

1、HashMap的底层数据结构？

HashMap是由数组和链表组合构成的数据结构。大概如下，数组里面每个地方都存了key- value这样的实例，在Java7叫Entry，在Java8中叫Node。

2、HashMap的存取原理？

因为HashMap本身所有的位置都是null，在put插入的时候会根据key的hash去计算一个index值。就比如说put（“帅丙”，520），我插入了为“帅丙”的元素，这个时候我们会通过哈希函数计算出插入的位置，计算处理index是2。

hash（“帅丙”） = 2

HashMap之所以会需要链表，是因为数组的长度是有限的，在有限的长度里面我们使用哈希，但是哈希本身就存在概率性，就是说“帅并”和“并帅”两个词我们都去进行哈希计算得到hash有一定的概率会是一样的，那这样“并帅”的极端情况也会hash到一个值上，那就形成了链表。

并且每个节点都会保存自身的hash、key、value、以及下一个节点，下面是Node的源码。

3、在Java7和Java8的区别？

在Java8之前Entry节点在插入的时候是头插法，意思是说新来的值会取代原有的值，原有的值就顺推到链表中去，就像上面的例子一样，因为写这个代码的作者认为后来的值被查找的可能性更大一点，提升查找的效率。但是在Java8之后，都是改用尾部插入了。

Java8之后链表有红黑树部分，代码里面有许多的if else的逻辑判断了，红黑树的引入巧妙的将原本O(n)的时间复杂度降低到了O(logn)。

使用头插法改变链表上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题。

Java7在多线程操作HashMap时可能会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系。

4、为啥会线程不安全？

因为通过源码看到put/get方法都没有加同步锁，多线程情况最容易出现的就是：无法保证上一秒put的值，下一秒get的时候还是原值，所以线程安全是无法得到保证。

5、有什么线程安全的类代替吗？

处理HashMap在线程安全的场景，一般都会使用HashTable或者ConcurrentHashMap，但是因为 前者的并发度的原因基本上没啥使用场景了，所以存在线程不安全的场景我们都使用ConcurrentHashMap。

HashTable的源码很简单粗暴，直接在方法上锁，并发度很低，最多同时允许一个线程访问，ConcurrentHashMap就好很多了，它比前者的并发度好太多了。

6、默认初始化大小是多少？为啥是这么多？为啥大小都是2的幂？

之所以会是2的幂，是因为为了位运算的方便，位与运算比算数计算的效率高了很多，之所选择16是为了服务将key映射到index的算法中。用16是因为在使用不是2的幂的数字的时候，length-1的值是所有二进制位全为1，这种情况下，index的结果等同与HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀。这是为了实现均匀分布。

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

因为数组的容量是有限的，数据多次插入之后，到达一定的数量就会进行扩容，也就是resize。那么什么时候resize呢？

有两个因素：

• Capacity：HashMap当前的长度
• LoadFactor：负载因子，默认值是0.75f

解释一下，就比如当前的容量大小为100，当你存进第76个的时候，判断发现需要进行resize了（因为超过了负载因子0.75f），那么就进行扩容。那么是如何扩容的呢？

分为两部：

• 扩容：创建一个新的Entry空数组，长度是原数组的2倍
• ReHash：遍历原Entry数组，把所有的Entry重写Hash到新数组

那么为什么要重新Hash呢，为什么不直接复制？

因为长度扩大以后，Hash的规则也随之改变。

Hash的公式---> index = HashCode（Key） & （Length - 1）

扩容前：

扩容后：

8、HashMap的主要参数都有哪些？

在重写equals方法的时候需要重写hashCode。

首先，在java中，所有对象都是继承于Object类。Object类中有两个方法equals、hashCode，这两个算法都是用来比较两个对象是否相等的。

在未重写equals方法我们是继承了object的equals方法，那里的equals是比较两个对象的内存地址，显然我们new了2个对象内存地址肯定不一样。对于值对象，==比较的是两个对象的值。对于引用对象，比较的是两个对象的地址。

上面那个例子“帅并”和“并帅”的index都可能是2，在一个链表上的。我们去get的时候，它是根据key去hash然后计算出index，找到了2，那么如何具体的找到“帅并”还是“并帅”呢？

equlas，所以如果我们对equals方法进行了重写，建议一定要对hashCode方法重写，以保证相同的对象返回相同的hash值，不同的对象返回不同的hash值。

9、HashMap是怎么处理hash碰撞的？

使用链表O(n)+红黑树O(logn)。正常一个位置放一对key- value，冲突后存放两对或多堆key- value。

这种挂链表的方式假设链表很长，会导致遍历链表性能较差，达到时间复杂度O(n)。做个优化：如果链表长度达到一定长度后，链表会转化成红黑树。使用红黑树的好处是，当遍历红黑树的时候，时间复杂度变成O(logn)，性能较高。

要回答出两点：

• 出现hash冲突的时候，会在这个位置上挂一个链表，在遍历时，时间复杂度时O(n)
• 当链表长度到达一定长度后，会将链表转化为红黑树，时间复杂度O(logn)。性能更高。

1. 链表在多长的时候会转红黑树，为啥在这个长度转红黑树？当链表长度超过8，并且经过扩容后当前数组长度大于64，会将链表转化为红黑树。而当HashMap的红黑树的元素小于等于6时候重新转化为链表结构。
2. 为什么JDK1.8 HashMap选择红黑树而不是其他的树？是因为红黑树的特性让它拥有较高的查询性能的同时，避免维持平衡带来的很大的开销。
3. 就是无论是链表还是红黑树，其在数组里面的位置就是一个，get的时候我怎么知道哪个值是我想要的？先通过寻址算法找到数组对应的index下标；然后获取当前下标的node节点，在get key的过程中是遍历链表或者遍历红黑树来查找对应的key的值value；遍历链表O(n)，遍历红黑树O(logn)