HashMap面试问题整理

拉链法

创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

头插

尾插

在 transfer() 方法中，因为新的 Table 顺序和旧的不同，所以在多线程同时扩容情况下，会导致第二个扩容的线程next混乱，本来是 A -> B ，但t1线程已经 B -> A 了，所以就 成环 了。

18扔掉了 transfer() 方法，用 resize() 扩容：

使用 do while 循环一次将一个链表上的所有元素加到链表上，然后再放到新的 Table 上对应的索引位置。

JDK17的时候使用的是数组+ 单链表的数据结构。但是在JDK18及之后时，使用的是数组+链表+红黑树的数据结构（当链表的深度达到8的时候，也就是默认阈值，就会自动扩容把链表转成红黑树的数据结构来把时间复杂度从O（n）变成O（logN）提高了效率）

18的索引 只用了一次移位，一次位运算就确定了索引，计算过程优化。

二者的 hash 扰动函数也不同，17有4次移位和5次位运算，18只有一次移位和一次位运算

初始容量和加载因子会影响 HashMap 的性能：

常说的capacity指的是 DEFAULT_INITIAL_CAPACITY （初始容量），值是 1<<4 ，即16；

capacity() 是个方法，返回数组的长度。

在hashMap构造函数中，赋值为 DEFAULT_LOAD_FACTOR（075f）

加载因子可设为>1，即永不会扩容，(牺牲性能节省内存)

Map中现在有的键值对数量，每 put 一个entry， ++size

数组扩容阈值。

即：HashMap数组总容量 加载因子（16 075 = 12）。当前 size 大于或等于该值时会执行扩容 resize() 。扩容的容量为当前 HashMap 总容量的两倍。比如，当前 HashMap 的总容量为 16 ，那么扩容之后为 32

获取哈希码， object 的 hashCode() 方法是个本地方法，是由C实现的。

理论上hashCode是一个int值，这个int值范围在-2147483648和2147483648之间，如果直接拿这个hashCode作为HashMap中数组的下标来访问的话，正常情况下是不会出现hash碰撞的。

但是这样的话会导致这个HashMap的数组长度比较长，长度大概为40亿，内存肯定是放不下的，所以这个时候需要把这个hashCode对数组长度取余，用得到的余数来访问数组下标。

高低位异或，避免高位不同，低位相同的两个 hashCode 值 产生碰撞。

为什么 重写 equals 时必须重写 hashCode 方法？

equals()既然已能对比的功能了，为什么还要hashCode()呢？ 因为重写的equals()里一般比较的比较全面比较复杂，这样效率就比较低，而利用hashCode()进行对比，则只要生成一个hash值进行比较就可以了，效率很高。

hashCode()既然效率这么高为什么还要equals()呢？ 因为hashCode()并不是完全可靠，有时候不同的对象他们生成的hashcode也会一样（生成hash值得公式可能存在的问题），所以hashCode()只能说是大部分时候可靠，并不是绝对可靠，

A：两个时候

Node[] table，即哈希桶数组，哈希桶数组table的长度length大小必须为2的n次方

075 2^n 得到的都是整数。

把bucket扩充为2倍，之后重新计算index，把节点再放到新的bucket中

hashCode是很长的一串数字，<font color = orange>(换成二进制，此元素的位置就是后四位组成的 ( 数组的长度为16，即4位 ))</font>

eg

<font color = gray>1111 1111 1111 1111 0000 1111 0001</font> 1111 (原索引是后面四个，索引是15)

扩容后：

<font color = gray>1111 1111 1111 1111 0000 1111 000</font> 1 1111 (新的索引多了一位)（多出来这个，或1或0 随机，完全看hash）

因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于 新增的1bit是0还是1可以认为是随机的 （hashCode里被作为索引的数往前走了一个，走的这个可能是0，也可能是1），因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。

用Iterator有两种方式，分别把迭代器放到entry和keyset上，第一种更推荐，因为不需要再 get(key)

可减少哈希碰撞

可以，null的索引被设置为0，也就是Table[0]位置

在JDK7中，调用了 putForNullKey() 方法，处理空值

JDK8中，则修改了hash函数，在hash函数中直接把 key==null 的元素hash值设为0，

再通过计算索引的步骤

得到索引为0；

对key的hashCode()做hash运算，计算index; 如果在bucket里的第一个节点里直接命中，则直接返回； 如果有冲突，则通过keyequals(k)去查找对应的Entry;

调用 putValue :

是以31为权，每一位为字符的ASCII值进行运算，用int的自然溢出来等效取模。

假设String是ABC，

可以使用ConcurrentHashmap，Hashtable等线程安全等集合类。

Divenier总结：

要看作为key的元素的类如何实现的，如果修改的部分导致其 hashcode 变化，则修改后不能 get() 到；

如修改部分对 hashcode 无影响，则可以修改。

开放定址法、链地址法(拉链法)、再Hash法

部分

参考资料：

>

HashMap是基于哈希表的 Map 接口的实现。此实现提供所有可选的映射 *** 作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

扩展资料：

因为HashMap的长度是有限的，当插入的Entry越来越多时，再完美的Hash函数也难免会出现index冲突的情况。

HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可。

参考资料来源：

百度百科-Hashmap

此实现假定哈希函数将元素适当地分布在各桶之间，可为基本 *** 作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。容量 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash *** 作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。

HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法；

这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算，源码中做了优化hash&(length-1)，

hash%length==hash&(length-1)的前提是length是2的n次方；

我们可以看到在hashmap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过hashmap的数据结构是数组和链表的结合，所以我们当然希望这个hashmap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表。

所以我们首先想到的就是把hashcode对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，能不能找一种更快速，消耗更小的方式那？java中时这样做的，

所以，在存储大容量数据的时候，最好预先指定hashmap的size为2的整数次幂次方。就算不指定的话，也会以大于且最接近指定值大小的2次幂来初始化的。

2、key的hashcode与equals方法改写

Hashmap的key可以是任何类型的对象，例如User这种对象，为了保证两个具有相同属性的user的hashcode相同，我们就需要改写hashcode方法，比方把hashcode值的计算与User对象的id关联起来，那么只要user对象拥有相同id，那么他们的hashcode也能保持一致了，这样就可以找到在hashmap数组中的位置了。如果这个位置上有多个元素，还需要用key的equals方法在对应位置的链表中找到需要的元素，所以只改写了hashcode方法是不够的，equals方法也是需要改写滴~当然啦，按正常思维逻辑，equals方法一般都会根据实际的业务内容来定义，例如根据user对象的id来判断两个user是否相等。

在改写equals方法的时候，需要满足以下三点：

(1) 自反性：就是说aequals(a)必须为true。

(2) 对称性：就是说aequals(b)=true的话，bequals(a)也必须为true。

(3) 传递性：就是说aequals(b)=true，并且bequals(c)=true的话，aequals(c)也必须为true。

通过改写key对象的equals和hashcode方法，我们可以将任意的业务对象作为map的key(前提是你确实有这样的需要)。

HashMap在JDK18及以后的版本中引入了红黑树结构，若桶中链表元素个数大于等于8时，链表转换成树结构；若桶中链表元素个数小于等于6时，树结构还原成链表。因为红黑树的平均查找长度是log(n)，长度为8的时候，平均查找长度为3，如果继续使用链表，平均查找长度为8/2=4，这才有转换为树的必要。链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。

还有选择6和8，中间有个差值7可以有效防止链表和树频繁转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员，其中 HashMap 是 Map 接口的常用实现类，HashSet 是 Set 接口的常用实现类。虽然 HashMap 和 HashSet 实现的接口规范不同，但它们底层的 Hash 存储机制完全一样，甚至 HashSet 本身就采用 HashMap 来实现的。

通过 HashMap、HashSet 的源代码分析其 Hash 存储机制

实际上，HashSet 和 HashMap 之间有很多相似之处，对于 HashSet 而言，系统采用 Hash 算法决定集合元素的存储位置，这样可以保证能快速存、取集合元素；对于 HashMap 而言，系统 key-value 当成一个整体进行处理，系统总是根据 Hash 算法来计算 key-value 的存储位置，这样可以保证能快速存、取 Map 的 key-value 对。

在介绍集合存储之前需要指出一点：虽然集合号称存储的是 Java 对象，但实际上并不会真正将 Java 对象放入 Set 集合中，只是在 Set 集合中保留这些对象的引用而言。也就是说：Java 集合实际上是多个引用变量所组成的集合，这些引用变量指向实际的 Java 对象。

集合和引用

就像引用类型的数组一样，当我们把 Java 对象放入数组之时，并不是真正的把 Java 对象放入数组中，只是把对象的引用放入数组中，每个数组元素都是一个引用变量。

HashMap 的存储实现

当程序试图将多个 key-value 放入 HashMap 中时，以如下代码片段为例：

Java代码

HashMap<String , Double> map = new HashMap<String , Double>();

mapput("语文" , 800);

mapput("数学" , 890);

mapput("英语" , 782);

HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置。

当程序执行 mapput("语文" , 800); 时，系统将调用"语文"的 hashCode() 方法得到其 hashCode 值——每个 Java 对象都有 hashCode() 方法，都可通过该方法获得它的 hashCode 值。得到这个对象的 hashCode 值之后，系统会根据该 hashCode 值来决定该元素的存储位置。

我们可以看 HashMap 类的 put(K key , V value) 方法的源代码：

Java代码

public V put(K key, V value)

{

// 如果 key 为 null，调用 putForNullKey 方法进行处理

if (key == null)

return putForNullKey(value);

// 根据 key 的 keyCode 计算 Hash 值

int hash = hash(keyhashCode());

// 搜索指定 hash 值在对应 table 中的索引

int i = indexFor(hash, tablelength);

// 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素

for (Entry<K,V> e = table[i]; e != null; e = enext)

{

Object k;

// 找到指定 key 与需要放入的 key 相等（hash 值相同

// 通过 equals 比较放回 true）

if (ehash == hash && ((k = ekey) == key

|| keyequals(k)))

{

V oldValue = evalue;

evalue = value;

erecordAccess(this);

return oldValue;

}

}

// 如果 i 索引处的 Entry 为 null，表明此处还没有 Entry

modCount++;

// 将 key、value 添加到 i 索引处

addEntry(hash, key, value, i);

return null;

}

上面程序中用到了一个重要的内部接口：MapEntry，每个 MapEntry 其实就是一个 key-value 对。从上面程序中可以看出：当系统决定存储 HashMap 中的 key-value 对时，完全没有考虑 Entry 中的 value，仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。这也说明了前面的结论：我们完全可以把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的存储位置之后，value 随之保存在那里即可。

上面方法提供了一个根据 hashCode() 返回值来计算 Hash 码的方法：hash()，这个方法是一个纯粹的数学计算，其方法如下：

Java代码

static int hash(int h)

{

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

对于任意给定的对象，只要它的 hashCode() 返回值相同，那么程序调用 hash(int h) 方法所计算得到的 Hash 码值总是相同的。接下来程序会调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下：

Java代码

static int indexFor(int h, int length)

{

return h & (length-1);

}

这个方法非常巧妙，它总是通过 h &(tablelength -1) 来得到该对象的保存位置——而 HashMap 底层数组的长度总是 2 的 n 次方，这一点可参看后面关于 HashMap 构造器的介绍。

当 length 总是 2 的倍数时，h & (length-1) 将是一个非常巧妙的设计：假设 h=5,length=16, 那么 h & length - 1 将得到 5；如果 h=6,length=16, 那么 h & length - 1 将得到 6 ……如果 h=15,length=16, 那么 h & length - 1 将得到 15；但是当 h=16 时 , length=16 时，那么 h & length - 1 将得到 0 了；当 h=17 时 , length=16 时，那么 h & length - 1 将得到 1 了……这样保证计算得到的索引值总是位于 table 数组的索引之内。

根据上面 put 方法的源代码可以看出，当程序试图将一个 key-value 对放入 HashMap 中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但 key 不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。

当向 HashMap 中添加 key-value 对，由其 key 的 hashCode() 返回值决定该 key-value 对（就是 Entry 对象）的存储位置。当两个 Entry 对象的 key 的 hashCode() 返回值相同时，将由 key 通过 eqauls() 比较值决定是采用覆盖行为（返回 true），还是产生 Entry 链（返回 false）。

上面程序中还调用了 addEntry(hash, key, value, i); 代码，其中 addEntry 是 HashMap 提供的一个包访问权限的方法，该方法仅用于添加一个 key-value 对。下面是该方法的代码：

Java代码

void addEntry(int hash, K key, V value, int bucketIndex)

{

// 获取指定 bucketIndex 索引处的 Entry

Entry<K,V> e = table[bucketIndex]; // ①

// 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry

table[bucketIndex] = new Entry<K,V>(hash, key, value, e);

// 如果 Map 中的 key-value 对的数量超过了极限

if (size++ >= threshold)

// 把 table 对象的长度扩充到 2 倍。

resize(2 tablelength); // ②

}

上面方法的代码很简单，但其中包含了一个非常优雅的设计：系统总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处已经有了一个 Entry 对象，那新添加的 Entry 对象指向原有的 Entry 对象（产生一个 Entry 链），如果 bucketIndex 索引处没有 Entry 对象，也就是上面程序①号代码的 e 变量是 null，也就是新放入的 Entry 对象指向 null，也就是没有产生 Entry 链。

JDK 源码

在 JDK 安装目录下可以找到一个 srczip 压缩文件，该文件里包含了 Java 基础类库的所有源文件。只要读者有学习兴趣，随时可以打开这份压缩文件来阅读 Java 类库的源代码，这对提高读者的编程能力是非常有帮助的。需要指出的是：srczip 中包含的源代码并没有包含像上文中的中文注释，这些注释是笔者自己添加进去的。

Hash 算法的性能选项

根据上面代码可以看出，在同一个 bucket 存储 Entry 链的情况下，新放入的 Entry 总是位于 bucket 中，而最早放入该 bucket 中的 Entry 则位于这个 Entry 链的最末端。

上面程序中还有这样两个变量：

size：该变量保存了该 HashMap 中所包含的 key-value 对的数量。

threshold：该变量包含了 HashMap 能容纳的 key-value 对的极限，它的值等于 HashMap 的容量乘以负载因子（load factor）。

从上面程序中②号代码可以看出，当 size++ >= threshold 时，HashMap 会自动调用 resize 方法扩充 HashMap 的容量。每扩充一次，HashMap 的容量就增大一倍。

上面程序中使用的 table 其实就是一个普通数组，每个数组都有一个固定的长度，这个数组的长度就是 HashMap 的容量。HashMap 包含如下几个构造器：

HashMap()：构建一个初始容量为 16，负载因子为 075 的 HashMap。

HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 075 的 HashMap。

HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。

当创建一个 HashMap 时，系统会自动创建一个 table 数组来保存 HashMap 中的 Entry，下面是 HashMap 中一个构造器的代码：

Java代码

// 以指定初始化容量、负载因子创建 HashMap

public HashMap(int initialCapacity, float loadFactor)

{

// 初始容量不能为负数

if (initialCapacity < 0)

throw new IllegalArgumentException(

"Illegal initial capacity: " +

initialCapacity);

// 如果初始容量大于最大容量，让出示容量

if (initialCapacity > MAXIMUM_CAPACITY)

initialCapacity = MAXIMUM_CAPACITY;

// 负载因子必须大于 0 的数值

if (loadFactor <= 0 || FloatisNaN(loadFactor))

throw new IllegalArgumentException(

loadFactor);

// 计算出大于 initialCapacity 的最小的 2 的 n 次方值。

int capacity = 1;

while (capacity < initialCapacity)

capacity <<= 1;

thisloadFactor = loadFactor;

// 设置容量极限等于容量 负载因子

threshold = (int)(capacity loadFactor);

// 初始化 table 数组

table = new Entry[capacity]; // ①

init();

}

上面代码中粗体字代码包含了一个简洁的代码实现：找出大于 initialCapacity 的、最小的 2 的 n 次方值，并将其作为 HashMap 的实际容量（由 capacity 变量保存）。例如给定 initialCapacity 为 10，那么该 HashMap 的实际容量就是 16。

程序①号代码处可以看到：table 的实质就是一个数组，一个长度为 capacity 的数组。

对于 HashMap 及其子类而言，它们采用 Hash 算法来决定集合中元素的存储位置。当系统开始初始化 HashMap 时，系统会创建一个长度为 capacity 的 Entry 数组，这个数组里可以存储元素的位置被称为“桶（bucket）”，每个 bucket 都有其指定索引，系统可以根据其索引快速访问该 bucket 里存储的元素。

无论何时，HashMap 的每个“桶”只存储一个元素（也就是一个 Entry），由于 Entry 对象可以包含一个引用变量（就是 Entry 构造器的的最后一个参数）用于指向下一个 Entry，因此可能出现的情况是：HashMap 的 bucket 中只有一个 Entry，但这个 Entry 指向另一个 Entry ——这就形成了一个 Entry 链。如图 1 所示：

图 1 HashMap 的存储示意

HashMap 的读取实现

当 HashMap 的每个 bucket 里存储的 Entry 只是单个 Entry ——也就是没有通过指针产生 Entry 链时，此时的 HashMap 具有最好的性能：当程序通过 key 取出对应 value 时，系统只要先计算出该 key 的 hashCode() 返回值，在根据该 hashCode 返回值找出该 key 在 table 数组中的索引，然后取出该索引处的 Entry，最后返回该 key 对应的 value 即可。看 HashMap 类的 get(K key) 方法代码：

Java代码

public V get(Object key)

{

// 如果 key 是 null，调用 getForNullKey 取出对应的 value

if (key == null)

return getForNullKey();

// 根据该 key 的 hashCode 值计算它的 hash 码

int hash = hash(keyhashCode());

// 直接取出 table 数组中指定索引处的值，

for (Entry<K,V> e = table[indexFor(hash, tablelength)];

e != null;

// 搜索该 Entry 链的下一个 Entr

e = enext) // ①

{

Object k;

// 如果该 Entry 的 key 与被搜索 key 相同

if (ehash == hash && ((k = ekey) == key

|| keyequals(k)))

return evalue;

}

return null;

}

从上面代码中可以看出，如果 HashMap 的每个 bucket 里只有一个 Entry 时，HashMap 可以根据索引、快速地取出该 bucket 里的 Entry；在发生“Hash 冲突”的情况下，单个 bucket 里存储的不是一个 Entry，而是一个 Entry 链，系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），那系统必须循环到最后才能找到该元素。

归纳起来简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据 Hash 算法来决定其存储位置；当需要取出一个 Entry 时，也会根据 Hash 算法找到其存储位置，直接取出该 Entry。由此可见：HashMap 之所以能快速存、取它所包含的 Entry，完全类似于现实生活中母亲从小教我们的：不同的东西要放在不同的位置，需要时才能快速找到它。

当创建 HashMap 时，有一个默认的负载因子（load factor），其默认值为 075，这是时间和空间成本上一种折衷：增大负载因子可以减少 Hash 表（就是那个 Entry 数组）所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的的 *** 作（HashMap 的 get() 与 put() 方法都要用到查询）；减小负载因子会提高数据查询的性能，但会增加 Hash 表所占用的内存空间。

掌握了上面知识之后，我们可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值；如果程序比较关心空间开销、内存比较紧张，可以适当地增加负载因子；如果程序比较关心时间开销，内存比较宽裕则可以适当的减少负载因子。通常情况下，程序员无需改变负载因子的值。

如果开始就知道 HashMap 会保存多个 key-value 对，可以在创建时就使用较大的初始化容量，如果 HashMap 中 Entry 的数量一直不会超过极限容量（capacity load factor），HashMap 就无需调用 resize() 方法重新分配 table 数组，从而保证较好的性能。当然，开始就将初始容量设置太高可能会浪费空间（系统需要创建一个长度为 capacity 的 Entry 数组），因此创建 HashMap 时初始化容量设置也需要小心对待。

HashMap（jdk 18）

  使用哈希表存储键值对，底层是一个存储Node的table数组。其基本的运行逻辑是，table数组的每一个元素是一个槽，用于存储Node对象，向Hash表中插入键值对时，首先计算键的hash值，并对数组容量（即数组长度）取余，定位该键值对应放在哪个槽中，若槽中已经存在元素（即哈希冲突），将Node节点插入到冲突链表尾端，当该槽中结点超过一定数量（默认为8）并且哈希表容量超过一定值（默认为64）时，对该链表进行树化。低于一定数量（默认为6）后进行resize时，树形结构又会链表化。当哈希表的总节点数超过阈值时，对哈希表进行扩容，容量翻倍。

由于哈希表需要用到key的哈希函数，因此对于自定义类作为key使用哈希表时，需要重写哈希函数，保证相等的key哈希值相同。

由于扩容或树化过程Node节点的位置会发生改变，因此哈希表是无序的，不同时期遍历同一张哈希表，得到的节点顺序会不同。

成员变量

    Hash表的成员变量主要有存储键值对的table数组，size，装载因子loadFactory，阈值theshold，容量capacity。

table数组：

哈希表的实质就是table数组，它用来存储键值对。哈希表中内部定义了Node类来封装键值对。

 Node类实现了Map的Entry接口。包括key，value，下一个Node指针和key的hash值。

 容量Capacity：

HashMap中没有专门的属性存储容量，容量等于tablelenth，即数组的长度，默认初始化容量为16。初始化时，可以指定哈希表容量，但容量必须是2的整数次幂，在初始化过程中，会调用tableSizeFor函数，得到一个不小于指定容量的2的整数次幂，暂时存入到threshold中。

注意，若容量设置过大，那么遍历整个哈希表需要耗费更多的时间。

    阈值threshold：

指定当前hash表最多存储多少个键值对，当size超过阈值时，hash表进行扩容，扩容后容量翻倍。

   loadFactory：

threshold=capacityloadFactory。

装填因子的大小决定了哈希表存储键值对数量的能力，它直接影响哈希表的查找性能。初始化时可以指定loadFactory的值，默认为075。

 初始化过程

哈希表有3个构造函数，用户可以指定哈希表的初始容量和装填因子，但初始化过程只是简单填入这两个参数，table数组并没有初始化。注意，这里的initialCapacity会向上取2的整数次幂并暂时保存到threshold中。

table数组的初始化是在第一次插入键值对时触发，实际在resize函数中进行初始化。

hash过程与下标计算

哈希表是通过key的哈希值决定Node放入哪个槽中， 在java8中 ，hash表没有直接用key的哈希值，而是自定义了hash函数。

哈希表中的key可以为null，若为null，哈希值为0，否则哈希值（一共32位）的高16位不变，低16位与高16位进行异或 *** 作，得到新的哈希值。（h >>> 16，表示无符号右移16位，高位补0，任何数跟0异或都是其本身，因此key的hash值高16位不变。）

之所以这样处理，是与table的下标计算有关

因为，table的长度都是2的幂，因此index仅与hash值的低n位有关（n-1为0000011111的形式），hash值的高位都被与 *** 作置为0了，相当于hash值对n取余。

由于index仅与hash值的低n位有关，把哈希值的低16位与高16位进行异或处理，可以让Node节点能更随机均匀得放入哈希表中。

get函数：

V  get(Object key) 通过给定的key查找value

先计算key的哈希值，找到对应的槽，遍历该槽中所有结点，如果结点中的key与查找的key相同或相等，则返回value值，否则返回null。

注意，如果返回值是null，并不一定是没有这种KV映射，也有可能是该key映射的值value是null，即key-null的映射。也就是说，使用get方法并不能判断这个key是否存在，只能通过containsKey方法来实现。

put函数

V put(K key, V value) 存放键值对

计算key的哈希值，找到哈希表中对应的槽，遍历该链表，如果发现已经存在包含该key的Node，则把新的value放入该结点中，返回该结点的旧value值（旧value可能是null），如果没有找到，则创建新结点插入到 链表尾端 （java7使用的是头插法），返回null。插入结点后需要判断该链表是否需要树化，并且判断整个哈希表是否需要扩容。

由该算法可以看出，哈希表中不会有两个key相同的键值对。

resize函数

    resize函数用来初始化或扩容table数组。主要做了两件事。

1根据table数组是否为空判断初始化还是扩容，计算出相应的newCap和newThr，新建table数组并设置新的threshold。

2若是进行扩容，则需要将原数组中的Node移植到新的数组中。

由于数组扩容，原来键值对可能存储在新数组不同的槽中。但由于键值对位置是对数组容量取余（index=hash(key)&(Capacity-1)）,由于Capacity固定为2的整数次幂，并新的Capacity（newCap）是旧的两倍（oldCap）。因此，只需要判断每个Node中的hash值在oldCap二进制那一位上是否为0(hash&oldCap==0)，若为0，对newCap取余值与oldCap相同，Node在新数组中槽的位置不变，若为1，新的位置是就得位置加一个oldCap值。

因此hashMap的移植算法是，遍历旧的槽：

若槽为空，跳过。

若槽只有一个Node，计算该Node在新数组中的位置，放入新槽中。

若槽是一个链表，则遍历这个链表，分别用loHead，loTail,hiHead,hiTail两组指针建立两个链表，把hash值oldCap位为0的Node节点放入lo链表中，hash值oldCap位为1的节点放入hi链表中，之后将两个链表分别插入到新数组中，实现原键值对的移植。

lo链表放入新数组原来位置，hi链表放入新数组原来位置+oldCap中

树化过程 ：

当一个槽中结点过多时，哈希表会将链表转换为红黑树，此处挖个坑。

[总结] java8中hashMap的实现原理与7之间的区别：

1hash值的计算方法不同 2链表采用尾插法，之前是头插法 3加入了红黑树结构

key-value：HashMap是key-value形式存储的数据结构，key、value都可以为null，但是key只可以有一个null，因为Map的key是不允许重复的。

默认容量：如果在new HashMap的时候没有设置默认值，那么默认容量就是16，如果设置了默认值，那么默认容量就是传入值的向上最接近2的幂等的值。

例如：HashMap map = new HashMap(3); 默认容量就是4；

hash冲突：hashMap是通过链地址法解决hash冲突，多次hash降低hash冲突。

线程安全：hashMap在并发的时候会有数据丢失，因为多线程去运行，put的时候值会被覆盖，扩容的时候也是不安全的，并发的时候链表会形成死循环。所以hashMap是线程不安全的。

数据结构：hashMap底层数据结构是数组+链表或者数组+红黑树。链表长度大于等于8并且数组长度大于等于64时，链表会转换为红黑树，链表长度小于6时，红黑树会转换为链表。链表长度限制为小于6，也是为了避免链表和红黑树之间频繁转换。

自动扩容：hashMap的扩容因子是075，当HashMap中的元素个数超过数组大小的075倍时，就会调用resize()方法进行数组扩容，每次扩容的容量都是之前容量的2倍。

首次put时会触发扩容(算是初始化)，然后存入数据，然后判断是否需要扩容。

不是首次put，则不再初始化，直接存入数据，然后判断是否需要扩容。

Collections中提供了一个方法synchronizedMap()

为了避免HashMap的线程安全问题引出了ConcurrentHashMap。

ConcurrentHashMap是由数组、单向链表、红黑树组成的，默认长度是16。key-value都不支持null。

当数组长度大于64并且链表长度大于等于8时，单向链表会转为红黑树，链表长度小于6，红黑树会退化成单向链表。

hach冲突：ConcurrentHashMap是通过链地址法来解决hash冲突的。

并发安全的主要实现是通过对指定的Node节点加锁，来保证数据更新的安全性。

ConcurrentHashMap在性能优化方面主要体现在两点

CAS全称为Compare and swap 比较替换。

假设有三个 *** 作数，内存值V，旧的预期值A，要修改的值B，当且仅当预期值A和内存值V相同时，才会将内存值A修改为B并返回true，否则什么都不做。当然cas要与volatile变量配合使用，这样才能保证每次拿到的变量是主内存中最新的那个值，否则旧的预期值A对某条线程来说，用于是一个不会变的值A，只要某次CAS *** 作失败，永远都不可能成功。

17采用数组+单链表，扩容采用头插法，并发情况下链表闭环，采用分段锁，采用的锁是Reentrantlock。

18采用数组+红黑树，扩容采用尾插法，采用Node节点，采用的锁是Synchronized+node。

fail-fast：是多线程并发 *** 作集合时的一种失败处理机制，就是最快的实际能把错误抛出而不是让程序执行。

人人都有一个进大厂的梦，希望以上的内容能够对你我这样的人有所帮助。

以上就是关于HashMap面试问题整理全部的内容，包括:HashMap面试问题整理、HashMap是什么东西、HashMap的内部实现机制，Hash是怎样实现的，什么时候ReHash等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！