本文共 2287 字，大约阅读时间需要 7 分钟。

1.HashMap的实现原理

HashMap概述：HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键，HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体

HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。Entry是HashMap的一个静态内部类 所以HashMap看起来像这样： HashMap基于Hash算法实现的：

1. 当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
2. 存储时，如果出现hash值相同的key（hash值相同的key值不一定相同），此时有两种情况：（1）如果key相同，则覆盖原始值（我们需要注意的时，在HashMap中key值是唯一的）（2）如果key值不同，则将当前的key/value放入链表中
3. 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值

2.HashMap在JDK1.7和JDK1.8中有哪些不同

在JDK1.8之前，采用的是拉链法：将链表和数组相结合，也就是说创建一个链表数组，数组中的一格就是一个链表，若遇到hash冲突，则将冲突的值加到链表中即可

在JDK1.8之后，引入和红黑树，当链表长度大于阈值（默认为8），但是数组长度小于64时首先进行扩容，当链表长度大于8，且数组长度大于64时，才会将链表转换为红黑树，以减少搜索时间

3.HashMap的put方法的具体流程

1. 首先计算key的hash值，这里调用了hash方法，hash方法实际上是让key.hashcode()与key.hashCode()>>>16进行异或操作,hash函数大概的作用就是：高16bit不变，低16bit和高16bit做一个异或操作
2. 判断table[i[是否为空（i就是通过hash函数计算出的hash值），如果为空，则直接新建节点添加，转向6
3. 判断table[i]的首元素是否和key一样，如果相同则直接覆盖value，退出
4. 如果table[i]的首元素和key不相同，那么判断table[i]是否为红黑树，如果是红黑树，则直接在树中插入键值对
5. 如果table[i]不是红黑树，则遍历table[i]，判断链表长度是否大于8，大于8的话将链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作
6. 插入成功后，判断实际存在的键值对数量是否超过hashMap的最大容量，如果超过，进行扩容操作
   

4.如何解决hash冲突

1. 使用链地址法来链接具有相同hash值得数据
2. 使用hash函数来降低哈希冲突的概率，使得数据分布更加均匀
3. 引入红黑树进一步降低遍历得时间复杂度，使遍历更加快

5.为什么HashMap中得String、Integer这样得包装适合作为K

1. 都是final类型，保证了Key的不更改性，不会存在同一对象获取hash值不同点额情况
2. 内部重写了equels()方法和hashCode()方法

6.HashMap为什么不直接使用hashCode()处理的hash值直接作为Table的下标

hashCode()方法返回的是int整数类型，范围在-（2³¹）~（2³¹-1),约有40亿个映射空间，而HashMap通常情况下是取不到最大值的，并且设备上也难以提供这么多空间，从而导致hashCode()计算出的hash值可能不在数组大小范围内，进而无法匹配存储位置

7.HashMap的长度为什么是2的幂次方

我们首先可能会想到采用%取余的操作来实现，如果我们采用&符号来代替%取余（因为按位运算会比%取余操作会更快），那么hash%lengthhash&（length-1）的前提就是length为2的n次方，所以这就解释了为什么HashMap的数组长度要为2的幂次方

简单来总结就是：**因为位运算会比%取余操作快很多，为了使取余符号与&操作等价，即为了使hash%lengthhash%（length-1）**

那为什么是两次扰动

为了是加大hash值低位的随机性，使得HashMap中的链表/红黑树长度差不多，从而提高对应数组存储下标位置的随机性&均匀性，最终减少hash冲突，两次扰动已经达到了高低位同时参与运算的目的

8.HashMap与HashTable有什么区别

1. 线程安全：hashMap是非线程安全的，HashTable是线程安全的：HashTable内部的方法基本都经过synchronized修饰
2. 效率：因为线程安全的问题，HashMap要比HashTable效率高一点。另外，Hashtable基本被淘汰，不要在代码中使用它
3. 对Null Key和Null value的支持：HashMap中，null可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为null。但是在HashTble中，put进的键值只要有一个null，就直接抛出异常
4. 初始容量大小和每次扩充容量大小的不同：创建时如果不指定容量初始值，HashTable默认的初始大小为11，之后每次扩充，容量变为原来的2n+1.HashMap默认的初始化大小为16.之后每次扩充，容量变为原来的2倍
5. 底层数据结构：JDK1.8以后的HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8），就会将链表转换为红黑树，以减少搜索时间，HashTable中没有这样的机制

转载地址：http://dmjmb.baihongyu.com/