【HashMap专题】15、hashmap 连环炮，看看你能接住多少招

共以下 9 个回答

• 中国用户 永久会员 2024年3月9日 下午1:04

  1、HashMap 了解吗？平时在什么地方使用过它呢？（说明：发现没有，我喜欢问使用场景，希望大家也是能够思考使用场景的，因为掌握了这个，你说话更加有说服力）
  哈希map是以key-value的方式存储数据（HashMap$Node类型），key不能重复，但值可以重复，允许使用null值。hashmap没有实现同步，线程不安全。
  2、HashMap 底层数据结构说一下？（指导：直接说最新的即可，不需要去对比以前的版本，因为面试官也听烦了，另外在说的时候，为了你语言的严谨，一定要强调下是哪个JDK版本的哈）
  在java8中，hashmap底层是elementData数组结构，当添加一个元素时，会先得到hash值转换成索引值，判断table中该位置是否有元素，没有就直接加入，有就调用equal方法比较，不同则放在该节点后面，当链表的元素达到8个并且数组的大小达到64就会进行树化。
  3、为什么用红黑树呢？用平衡二叉树不可以吗？或者你讲一讲他们各自的优缺点吗？
  黑树不追求”完全平衡”，从维护开销方面比AVL好，读取就没有AVL好。
  4、为什么选择 8 之后转为红黑树呢？另外链表转为红黑树之后，还会继续转为链表吗？
  会，如果元素的哈希值足够随机，链表的长度对应的概率符合泊松分布，达到 8 的概率小于千万分之一。当红黑树的节点小于 6 时，红黑树又会转回链表。
  5、简单描述下 put 的流程？可以说一下JDK位了效率更快，在 put 的时候，做了哪些优化不？
  先初始化加载因子0.75，当添加一个元素时，会先得到hash值转换成索引值，判断table中该位置是否有元素，没有就直接加入，有就调用equal方法比较，不同则放在该节点后面，当链表的元素达到8个并且数组的大小达到64就会进行树化。优化，索引key的优化，hashcode和自身右位运算16
  6、多线程情况下，put 是线程安全的吗？可以简单举个例子，说一下哪里不安全吗？
  不安全，java8 采用的是尾插法，保证了元素在扩容前后的顺序一致，避免了死循环问题，但还会造成数据覆盖。
  7、如果我想要让 hashmap 变成线程安全的，你觉得可以怎么做？（有时候会扯到 concurrentHashMap，不过咱们这里先不追击这个）
  可以使用 ConcurrentHashMap，分段锁
  8、头插法会导致死循环，那你觉得在以前的版本中，为啥会使用头插法呢？
  很快被拿到
  9、那我们再说一说 HashMap 的扩容吧，什么时候会扩容呢？你觉得为啥负载因子为啥选择 0.75 呢？
  当表中的元素大于threshold 也就是capacity * loadfactor的时候就会进行扩容，“哈希冲突” 和 “空间利用率“
  10、频繁扩容会导致效率比较低下，那你觉得在平时，在实际的开发场景中，可以怎么优化来避免频繁扩容呢？
  先估计容量大小
  11、一个场景题：只存60个键值对，需要设置初始化容量吗？设置的话设置多少初始化容量比较好呢？
  初始化是16，12时扩容到32,24时扩容到64，48的时候扩容到128，应该最小初始化65.

  0 赞同 0 条回复

  登录以回复
• Everglow 永久会员 2023年11月17日 上午1:00

  1、HashMap 了解吗？平时在什么地方使用过它呢？（说明：发现没有，我喜欢问使用场景，希望大家也是能够思考使用场景的，因为掌握了这个，你说话更加有说服力）

  HashMap是一种存储键值对的数据结构，简单的原理就是通过计算键的哈希值定位存储到数组中的位置。在存储一些有关联的数据的场景中可以使用，例如想要通过id获取到一个User对象，就可以使用HashMap存储，就可以以近似O（1）的时间复杂度获取到数据。

  2、HashMap 底层数据结构说一下？（指导：直接说最新的即可，不需要去对比以前的版本，因为面试官也听烦了，另外在说的时候，为了你语言的严谨，一定要强调下是哪个JDK版本的哈）

  HashMap底层是通过数组存储数据的，通过把键值对封装在HashMap的内部类Node中进行存储，如果发生了哈希冲突，HashMap通过拉链法，也就是拉出一条链表来存储哈希值相同的元素。在JAVA8后进行了优化，新增了红黑树这一数据结构，当一条链上的元素大于等于8，并且数组长度大于等于64时会将这条链表转变为一颗红黑树，从而提高数据的检索效率 从O(n)提升到O(logn)。

  3、为什么用红黑树呢？用平衡二叉树不可以吗？或者你讲一讲他们各自的优缺点吗？

  红黑树和平衡二叉树都是平衡树，区别就在于红黑树是保证的黑节点平衡，而平衡二叉树要求严格的平衡，也就是左右子树高度不能大于1，所以在插入元素的时候，二叉树可能会进行多次的旋转来保持绝对的平衡，如果使用平衡二叉树插入数据的效率可能会很低，使用红黑树虽然插入效率变高，但每个节点要维护该节点的颜色属性，空间上占用的会更多。

  4、为什么选择 8 之后转为红黑树呢？另外链表转为红黑树之后，还会继续转为链表吗？

  因为在哈希函数完全随机的情况下，负载因子在0.75的情况下，一条链上的长度是服从柏松分布的，当长度为8时 概率小于千万分之一，也就代表着不会轻易的树化，因为树化的过程耗费时间很多，但是如果哈希函数选择不好的情况下，链表长度过长，就需要转为红黑树提高检索效率。

  5、简单描述下 put 的流程？可以说一下JDK位了效率更快，在 put 的时候，做了哪些优化不？

  首先调用key的hashcode方法获取到哈希值，并且将key的哈希值的低16位与高16位按位异或来增加哈希函数的随机性，因为在通过key确定索引位置的时候是通过与数组长度取模确定的，转变为二进制就是取二进制的后几位作为索引位置，这样哈希值的高位可能就永远用不到，所以为了增加随机性，通过这样一个扰动函数来优化。之后调用putVal方法首先判断当前数组是否初始化，因为hashmap采用懒加载的策略，只有put值的时候才会开辟数组空间，初始化后通过用哈希值对数组长度取模确定存储在数组中的索引位置，如果当前索引处为空，就直接把node放入该槽中，如果不为空，则通过 或 equals方法来判断key是否相同 如果相同就替换node也就是value的值，如果不想等就依次遍历该槽中拉出链表的节点，如果key都不想等，就在链表尾部插入该数据，插入前还要判断是否需要树化如果需要还要转变为红黑树，在最后还要判断当前哈希表中的元素是否大于capacity * loacfactor如果大于阈值就需要resize()将数组长度增加到原来的二倍，并对哈希表中的元素rehash

  并且在哈希值与数组长度取模的过程，没有使用%来直接运算，而是通过数组长度-1与哈希值按位与，通过位运算的方式来取模，具体原理就是 因为HashMap要求数组长度都是2的幂次，我以16举例16的二进制是01000 -1 之后就变成 00111 与hashcode按位与就是取hashcode的后三位，也就是计算hashcode 模 16的值。

  6、多线程情况下，put 是线程安全的吗？可以简单举个例子，说一下哪里不安全吗？

  不是线程安全的，假如有两个线程先后往同一个空槽中插入相同的key但是不同的数据，线程1首先判断当前槽中元素为空，此时发生了上下文切换，线程2将数据插入了该槽中，此时cpu再次切换到线程1，就会对线程2插入的数据造成覆盖

  7、如果我想要让 hashmap 变成线程安全的，你觉得可以怎么做？（有时候会扯到 concurrentHashMap，不过咱们这里先不追击这个）

  可以使用Collections类中的synchronizedMap方法，也就是把HashMap中的所有方法包装成synchronized方法。

  或者使用HashTable 原理和它一样，缺点就是在对表做修改时会锁住整个表 并发效率太低。

  使用ConcurrentHashMap

  8、头插法会导致死循环，那你觉得在以前的版本中，为啥会使用头插法呢？

  主要是用到时间局部性原理吧，就是说我新插入的元素，在后面大概率就会先用到，保证查找的时间复杂度为O（1）

  9、那我们再说一说 HashMap 的扩容吧，什么时候会扩容呢？你觉得为啥负载因子为啥选择 0.75 呢？

  当表中的元素大于threshold 也就是capacity * loadfactor的时候就会进行扩容。选择0.75是对时间和空间的平衡，负载因子我们可以理解成哈希表中元素装满的程度，如果负载因子过小，就会导致刚插入几个元素就会resize，虽然发生哈希冲突概率很小，但是空间利用率太低，如果负载因子过大，就会导致哈希表中装的很满，也就是哈希冲突的概率很大，这样检索效率就会很低，所以选择0.75对时间效率和空间上的一个平衡

  10、频繁扩容会导致效率比较低下，那你觉得在平时，在实际的开发场景中，可以怎么优化来避免频繁扩容呢？

  可以先预估这个哈希表要装多少元素，预先通过构造函数开辟出合适大小的数组，避免resize（），

  还可以根据需求自定义loadfactor

  11、一个场景题：只存60个键值对，需要设置初始化容量吗？设置的话设置多少初始化容量比较好呢？

  需要，因为HashMap初始容量是16，如果最终要存60个键值对，就要经历好几次resize，为了减少resize的次数，可以设置为128，这样就保证在put的时候永远不会resize

  0 赞同 0 条回复

  登录以回复
• Silence 永久会员 2023年10月27日 下午9:08

  1 嗯，hashmap了解，他是一个Kv键值队形的集合，它的key具有无序性和不允许重复的特性。嗯，通常来看的话，哈西map它在实际的应用场景中用缓存的场景比较多，就比如说spring它为了解决循环依赖，它有三级缓存，都是用的hashmap来进行实现的。

  2 在JDK 1.8这个版本当中，它hashmap的底层实现是使用了数组加链表加红黑树的数据结构。它解决哈希冲突的方法就是通过链子存储来解决的哈希冲突，所以说用到了链表,但是如果说链表过长了的话会增加他的查询时间复杂度提高他的耗时,所以说链表过长的时候，它就会自动转换成红黑树.

  3 嗯，首先来对比一下这个红黑树和平衡二叉。从查找的效率上来说，他们都是o（logn）。但是红黑树他并不要求他完全平衡，然后平衡二叉树它有强制要求，就是它的左右高度相差不能超过1。但是红黑树只需要保证它的左右子树的高度相差不超过两倍。所以说平衡二叉树维持平衡的代价要比红黑树高一些，他需要使用更多的旋转来保持平衡，而红黑树则不用。所以说从删除插入节点方面来说，红黑树的效率要高于平衡二叉树，所以选择了红黑树

  4 链表转换成红黑色的条件是嗯，当这个链表的长度超过八，并且这个焊系统的宽度超过64之后就会树化。之所以选择八作为这个临界值，其实是经过了大量的统计规律之后，发现在正常情况下一个链表他要超过八的情况其实概率非常非常低，到达了几百万分之一。所以说没有必要设置的更长，而设置更短了之后呢，它又可能会频繁的树化，嗯，把链表转换成红黑树，它也是需要消耗性能的，所以说频繁的书画的话也会给性能带来影响。综合来看的话，选择8在效率上是最好的。

  5 嗯，他的整个葡萄流程就是说我们在铺的一个元素的时候，首先会去看一看这个整个表他是否是空，如果说是空的话，那就说明他是第一次破台元素，他会去初始化这个表。默认的初始容量的话，它就是指定的16。然后初始化好了之后，他会根据插入的key 的Hash code的高位和低位进行预货之后，对于这个焊系统的宽度进行取模得到他需要put的元素的哈希统的下标，然后他会判断一下这个哈系统是否为空，如果为空的话，那么就可以直接铺进去进行返回，嗯，如果不为空的话，他就会去判断一下他的这个code跟这个桶的头结点的code是否相同，如果不相同则判断下一个，如果说相同，那么就调用进一步判断究竟是否是同一个对象。如果说是的话，那么就覆盖掉外露，然后直接返回。如果说不是的话，那么他就会便利整个链表进行一直下一个下一个的这么判断，判断的顺序都是先判断哈西扣的是否相等，如果不等着直接判断下一个，如果相等，那么就会调用eos来进行判断。如果到的链表尾部都没有发现有这个元素出现的话，那么就直接会插入到这个链表的尾部。这里面有一个优化的点，就是说他在进行判断的时候是利用的high code来加速了一个判断，因为用的判断只需要判断两个值是否相等就可以了，而用的话它会走更复杂的逻辑。之所以可以用哈西cod来加速判断，就是有一个要求，要求我们在重写了equals方法的同时，必须要重写哈西code的这个方法，重写哈西cod的目的就是为了保证我们调用eos返回处的时候他们之间的hash code一定相等，这样才能确保哈西code不等的时候，eos一定不相等。然后还有一个优化的地方，就是它在计算桶的下标的时候并不是用的真正的取模运算，而是用了一个按位与的操作来加速取模运算。需要实现这个逻辑也有一定的前置要求，要求就是我们这个哈希统的宽度必须是2的整数次幂。说哈希map在我们指定某一个初始容量之后也会自动的把它真实的哈系统的宽度调整为嗯，对应的大于等于这个宽度的最小的2的整数次幂。

  6 多线程下map它的过程并不是安全的，因为他没有做任何的并发控制，可能会导致一些错误出现。就比如说两个线程同时到一个链表的尾部的时候，他们遍历都是遍历到了同一个尾部，就有可能导致后面的线程覆盖掉前面线程的添加操作。

  7 如果说要让哈西map变成现场安全的话，那么就需要对他做并发控制，这个时候并法控制的所的力度就显得尤为重要了，如果说锁的范围太大了的话，那肯定会极大的降低这个Map的性能，所以说我们加锁的时候要尽可能吸力度的加锁，然后来尽可能的提高他的并发度的同时保证他的县城安全。Concurrent hash map在1.7版本的时候使用的是分段所来保证的线程安全，到了1.8版本之后，就使用的是更为细力度的锁，锁住的是每一个链表的表头。

  8 嗯，我认为DK 1.7版本它使用头插法的原因主要是因为程序的局部性原理吧，局部性原理，他的意思就是说我们现在执行的指令或者说是访问的数据非常有可能在接下来的时间内立马又被访问到，所以说操作系统它所用的页面置换算法大多都是用lru来实现的，DK 1.7版本的头插法，我感觉也有这么点意思，就是说我们插入了一个数据之后，很有可能立马就访问到，所以说把它放在头部的话就可以提升查询的效率。但是头插法其实它并不能提高插入元素的效率，因为哈西迈普的唯一性规定了他的key不能要重复，即使最后是插在头部，他也需要把整个链表遍历完，确保没有重复的元素之后才能插入。

  9 hashmap的扩容，是吧？当一个哈希迈普的元素中越来越多了之后，那么它发生哈希冲突的可能性就会越来越高，就有可能会导致一条链表上的元素堆积的越来越多，导致查询的效率降低。所以这个时候我们就需要对哈希表进行一个扩容，减少哈希碰撞，提高查询的效率。阿西麦普他在进行扩容的时候有一个扩容因子，当map中的元素达到了这个桶的宽度乘以这个扩容因子之后，它就会提前进行扩容。通常来讲的话，这个扩容因子它默认是0.75，之所以选0.75是根据概率统计来得出的结论，在泊松分布中有一个够表达碰撞的概率跟扩容因子的关系。我说这个扩容因此设置太小之后呢，它就有可能会频繁的扩容，浪费我们的内存空间，如果说他设置太大了就会导致频繁的哈希碰撞，降低我们的查询效率，所以在综合考虑之后，通常就是这个扩容，因此选定为0.7~0.8最为合适，hashmap就在里面选择了0.75这个值。

  10 我们尽量避免扩容的方式可以指定初始容量，在创建一个map之前，大概的估计一下他未来会承载的容量将是多少并且指定一下这个容量，指定了初始容量之后，Put元素的时候长一段时间都不用再动态的进行扩容。不用重新分配内存空间和拷贝元素，极大的提高了我们put的效率，减少了不必要的性能消耗，但是这样做也有可能会导致我们高估了元素的个数导致空间的浪费。

  11 如果已经确定了要put60个元素的话，那么就可以为他指定初始容量，动态扩容就是为了避免内存不够用才他帮我们动态的申请内存，既然我们自己知道了，就不必要浪费这个动态扩容的性能了。它的初始容量我认为设置成128比较合适，你可能会想设置成64不是更加接近他原本需要的容量，这样能够节省内存。但是还是迈普他有一个扩容因子，扩容因子是0.75，它会导致即使我们设置成64，它的元素达到48个的时候也会帮我们扩容到128，所以说我们直接指定128就又减少了他扩容的消耗。

  0 赞同 0 条回复

  登录以回复
• LilyBoy 永久会员 2023年9月10日 上午12:35

  打卡

  0 赞同 0 条回复

  登录以回复
• Gary 永久会员 2023年7月8日 下午3:26

  1.hashMap是一个用来存放key-value键值对的集合类型，key和value的类型都可以自定义，一般key会用String或者Integer类型，因为这两个类型的对象的值不会发生变化，它们对应的哈希值会比较固定，在获取的时候不用每次都重新计算一遍。在controller返回Json结果的时候，可以用hashMap作为一个结果的返回类型，比如里面放状态码、信息、数据，code然后跟一个状态码，message然后跟具体发返回的信息，data然后跟具体返回的数据；

  2.在jdk1.8，hashMap用的是数组+链表+红黑树的数据结构。没有发生哈希冲突的时候，元素都放在数组里面；发生了冲突之后，数组的同一个位置需要放多个元素，此时数组的位置放的就是一个链表或者一个红黑树，这个位置的元素小于8并且hashMap的元素数量小于64的时候，用的是链表，这样可以防止过于频繁的树化和反树化；当元素多的时候，就把链表变成红黑树；

  3.用红黑树代替链表，是因为元素多了之后，链表的查询效率会很低；不用平衡二叉树是因为虽然平衡二叉树和红黑树都可以使得树的高度不至于太高，但是它们两个维持高度的开销不一样，红黑树是通过颜色和平衡操作来维持树的高度，而平衡二叉树需要维护一个额外的平衡因子

  4.元素少的时候，链表在空间和效率上，都比红黑树要好。至于为什么是8，因为这个时候，链表的长度符合泊松概率的分布，长度大于8的概率是小于百万分之一，也就是说，一般情况下，很难发生链表转换成红黑树这种情况，发明这个机制更多是为了防止在特殊情况下，hashMap依然可以有一个比较好的性能

  5.put的时候，先计算出key的哈希值，再计算出在数组上的对应位置，如果这个位置没元素，就直接放在数组的这个位置，数组没初始化长度的话，要先创建一个默认长度为16的数组。如果这个位置有元素，就看看这个位置上的所有key的值，有没有跟put进来的这个key一样的，如果有，就把原来的value替换成put进来的value；如果没有，就放在数组对应位置的链表或者红黑树上，如果放链表，要判断一下是否要转换成红黑树，最后判断一下需不需要扩容
  两个方面的优化，为了提高计算效率，用位运算代替取模运算；为了减少哈希冲突，用多个与运算符对哈希值的高位和低位进行搅动运算，尽量做到，就算两个key只有一个位不一样，都会对最后的哈希值造成影响

  6.不安全。jdk1.8使用尾插法的方式，解决了链表死循环的问题，但是，同一时间多个线程同时put，如果碰巧判断到同一个槽位是空的，那么后面插入的数据，会把前面的覆盖掉

  7.直接在每个方法前面都加个synchronized，hashTable就是这样实现线程安全的，但是效率很低，相当于只能单线程操作。可以使用concurrentHashMap，它使用CAS和分段锁的方式，可以在保证线程安全的同时，提高并发的效率

  8.因为通常情况下，认为新插入的数据，会有更大的概率被用到，放前面的话查询效率会更高，不用遍历链表，直接在第一个就能拿到

  9.hashMap默认的负载因子是0.75,这是在空间利用率和哈希冲突概率，两者之间的一个权衡，是测试人员做了大量实验之后，得出的一个效果比较好的结果。链表转换为红黑树之后，如果红黑树的结点数变成6，那么这个红黑树会退化成链表

  10.可以根据业务需要，计算出hashMap会放多少个元素在里面，然后指定一个初始化长度，或者可以修改一下默认的负载因子

  11.默认的第一次插入元素的时候，长度是16，每次扩容都是两倍的扩，16-32-64-128，所以可以指定初始化长度为128，避免扩容带来的开销

  0 赞同 0 条回复

  登录以回复
• 。 永久会员 2023年6月23日 下午5:40

  1.HashMap是一种键值对的数据结构，能够在O(1)时间复杂度查找key，在一些需要传递多种类型参数的方法会使用一个hashMap作为参数传递，比如在使用mybatis需要传递一些分页参数，直接传递会导致代码过长，这时候可以使用Map来传递；
  2.在jdk8下使用数组+链表+红黑树；
  3.红黑树和平衡二叉树都能够在logn时间复杂度查找到元素，但是平衡二叉树在插入和删除时需要进行rl，rr，ll，lr旋转来保持高度平衡，红黑树放松限制，通过节点变色和左右旋转来维护接近平衡；
  4. 链表长度到8是小概率事件，通常是对象的hashCode有问题，到达8后转为红黑树可以把查找复杂度从O(n)降到O(olgn)，在数据量小的情况下O(n)和O(olgn)没有区别。红黑树会在元素少于6的情况下转换为链表，如果在小于8的情况下链表转换为红黑树，可能会有频繁的转换发生；
  5.先获取key对象的hashCode，算出对象应该在数组存放的位置，如果那个位置没有数据，直接存放，如果有数据，遍历链表，有相同hashcode就直接退出，如果链表长度小于7，直接接入链表，如果链表长度大于等于8，转换为红黑树，如果该位置是红黑树，直接插入。插入后如果键值对数量大于数组长度与负载因子(默认0.75)的乘积时，会触发扩容；
  6.多线程环境下不安全，在jdk7链表用头插法插入，多线程下会出现循环链表，jdk8的链表使用尾插法，多个数据插入同一位置，会出现覆盖的情况，如果已经是红黑树在多线程下会出现树的平衡被破坏；
  7.使用Collections.synchronizedMap(Map map)方法，也可以使用reentrantReadWriteLock来保障线程安全;
  8.后加入的数据被访问的概论较大；
  9.在数组为空时，键值对数量大于数组长度与负载因子乘积时。0.75即四分之一，对于长度为2的幂的数字来说可以得到精确的数字，如果因子太大会导致数据过多，hash冲突变多，效率下降，如果因子太小，导致频繁的扩容，会造成空间的浪费和效率下降；
  10.改变初始容量，这样数组长度会更大，扩容次数会减少，也可以修改负载因子大小。重写key对象的hashCode方法，确保随机性；
  11.如果未设置初始容量，那么会在插入到12个，24个，48个时进行扩容，最后数组长度为128，如果设置初始容量为64，那么会在插入到48个时进行扩容，可以直接设置为128，这样就不用扩容；

  1 赞同 0 条回复

  登录以回复
• 秊 永久会员 2023年6月21日 下午5:50

  1、HashMap 了解吗？平时在什么地方使用过它呢？（说明：发现没有，我喜欢问使用场景，希望大家也是能够思考使用场景的，因为掌握了这个，你说话更加有说服力）

  HashMap 也就是哈希表，底层利用数组支持下标随机访问数据的特性，快速的对键值对进行增删改查操作。（项目中好像没有直接用到过，用到了来补充）

  2、HashMap 底层数据结构说一下？（指导：直接说最新的即可，不需要去对比以前的版本，因为面试官也听烦了，另外在说的时候，为了你语言的严谨，一定要强调下是哪个JDK版本的哈）

  在最新的 JDK 1.8 中，HashMap 的底层数据结构为 “哈希表 + 链表 + 红黑树”。当哈希表中出现哈希冲突时，HashMap 采用 “链地址法” 来解决，也就是哈希表中的每个槽位，都会对应一个链表，所有哈希值相同的元素都会被放到同一个槽位对应的链表中。但随着链表长度的增加，元素的读取效率会下降，直到达到某个阈值时，HashMap 会将链表转化为红黑树，进一步提升性能。

  3、为什么用红黑树呢？用平衡二叉树不可以吗？或者你讲一讲他们各自的优缺点吗？

  红黑树是弱平衡二叉树，整棵树可以有局部的不平衡。AVL 树是强平衡二叉树，它严格要求整棵树的平衡性。也就是说，虽然两者的插入，删除复杂度都为 $O(logn)$，实际中 AVL 树需要执行更多的旋转操作来保证强平衡性，效率要低于红黑树。但红黑树也有缺点，它需要额外的字段来记录每个节点的颜色，因此会占用更多的存储空间。

  4、为什么选择 8 之后转为红黑树呢？另外链表转为红黑树之后，还会继续转为链表吗？

  这个在源码的注释中有解释，大致意思为：如果元素的哈希值足够随机，理想情况下链表的长度对应的概率符合泊松分布，达到 8 的概率小于千万分之一。也就是说，一般情况下并不会发生链表到红黑树的转化，更多是一种防止自己选取的哈希算法不好的保底策略，在极端情况下仍会有较好的效率。

  但是，当红黑树的节点小于 6 时，红黑树又会转回链表，原因是数据量很小的情况下，空间和时间上链表都要比红黑树优秀。至于为什么要把这个阈值定为 6，而不同样定为 8，主要是而为了防止元素数量在 8 附近导致两种数据结构的频繁转换。

  5、简单描述下 put 的流程？可以说一下JDK为了效率更快，在 put 的时候，做了哪些优化不？

  首先 put( ) 会计算出要插入 key 的哈希值，通过哈希值计算出其在数组中的索引位置，如果该位置上没有元素则直接插入，有元素则需要遍历这个位置上的所有元素。如果能找到与当前键相等的键值对，则将其更新为当前值并返回旧值，如果找不到与当前键相等的键值对，则需要执行真正的插入操作，将其插入到链表或者红黑树中，最后判断插入后是否需要扩容。

  put( ) 的优化我印象深的是计算 key 哈希值的 hash( )，主要有两个优化的点：使用位运算代替取模运算和对 hashCode 进行搅动计算。具体来说，可以用 $x % 2^n = x & (2^n – 1)$ 这个公式将取模转变为位运算来提升性能，但是同时也需要底层数组的长度是 2 的倍数，这个在 HashMap 的初始化和扩容方法中做了保证。

  除此之外，为了进一步降低哈希冲突的概率，hash( ) 又通过多个与运算将哈希值的高位和低位进行搅动，尽可能的做到在不同 key 中哪怕有一个位的不同，都会对最终产生的哈希值造成影响。

  6、多线程情况下，put 是线程安全的吗？可以简单举个例子，说一下哪里不安全吗？

  不是，在 JDK 1.7 中多线程同时进行 put( ) 会出现数据覆盖问题，在需要扩容时也可能会出现链死循环问题。JDK 1.8 修复了链死循环，但数据覆盖问题依然存在。

  JDK 1.7 的 HashMap 底层为数组 + 链表，扩容的 transfer( ) 会遍历原链表中的每个节点，采用头插法将其转移到新哈希表槽位的链表中，这个过程在多线程下会导致新链表中出现环路，并造成某些元素丢失。

  JDK 1.8 采用的是尾插法，保证了元素在扩容前后的顺序一致，避免了死循环问题，但还会造成数据覆盖。比如两个线程同时执行 put( )，且两个线程都同时判断槽位为空，则后插入的数据会覆盖先插入的数据。

  7、如果我想要让 hashmap 变成线程安全的，你觉得可以怎么做？（有时候会扯到 concurrentHashMap，不过咱们这里先不追击这个）

  想要解决 HashMap 的线程不安全问题，首先我们不能修改源码，那就要么使用一些 “辅助” 操作，让它变得安全，要么就寻找替代品。首先说的 “辅助” 操作是指，使用 Collections 类的 synchronizedMap 方法包装一下，它返回由指定映射支持的同步映射，是线程安全的。换替代品的话，可以考虑 HashTable，HashTable 通过将整个表上锁来实现线程安全，某些情况下效率很低。还可以使用 ConcurrentHashMap，它使用分段锁或者 CAS 操作来保证线程安全。

  8、头插法会导致死循环，那你觉得在以前的版本中，为啥会使用头插法呢？

  采用头插法的话，最新插入的数据就会在链表的最前边，根据程序的局部性原理，最近被访问的数据很可能不久之后会再次访问，那么此时可以在 $O(1)$ 时间返回。

  9、那我们再说一说 HashMap 的扩容吧，什么时候会扩容呢？你觉得为啥负载因子为啥选择 0.75 呢？

  HashMap 需要扩容时，可以分为几种情况来考虑。

  首先是在无参的构造函数中。在第一次进行 put 操作之前，HashMap 内部数组为 null，第一次 put 后才会开始第一次初始化扩容，默认为 16 。

  其次是指定了初始容量的构造参数，也是在第一次 put 操作之后才开始初始化扩容，但此时的容量是第一个不小于指定容量的 2 的幂数，阈值为计算后容量乘负载因子。

  其它情况就是，非首次 put，导致容量大于阈值，需要扩容。容量和阈值都变为原来的 2 倍，负载因子不变。

  负载因子为 0,75 的原因，简单来说是 “哈希冲突” 和 “空间利用率“ 矛盾的一个折中。原因是，扩容因子是用来计算阈值的，阈值为底层 table 长度乘负载因子，当 HashMap 容量大于阈值时会触发扩容。所以如果负载因子过小，table 中还没填几个元素就要扩容，虽然哈希冲突概率很小，但空间浪费太多。相反，如果负载因子过大，空间利用率是高，但哈希冲突的概率也大大增加。那就取个折中吧，为 0.75。

  10、频繁扩容会导致效率比较低下，那你觉得在平时，在实际的开发场景中，可以怎么优化来避免频繁扩容呢？

  容易想到的就是，提前预估业务的存储量，设置一个较大的初始容量。这时不用考虑它是否是 2 的次幂，HashMap 自己会计算出第一个大于等于给定容量的 2 次幂来作为初始容量。除此之外，可以自定义负载因子的大小，对哈希函数优化等等。

  11、一个场景题：只存60个键值对，需要设置初始化容量吗？设置的话设置多少初始化容量比较好呢？

  HashMap 默认的初始容量大小为 16。如果不设置初始容量的话，根据规则 size > threshold 时会触发扩容，且 threshold = loadFactor *capacitry，最终 capacity 会经历 16 – 32 – 64 – 128 三次扩容操作。考虑到HashMap 自己会计算出第一个大于等于给定容量的 2 次幂来作为初始容量，所以随机选一个 65 – 128 之间的数作为初始容量即可。

  2 赞同 0 条回复

  登录以回复
• upward ᯤ⁶⁰ᴳ 永久会员 2023年6月13日 上午10:24

  1 hashmap是java的集合框架的一个实现类，实现了collection接口，在我的支付项目上用到过，用于接收redis中购物车的数据结构
  2 HashMap 底层数据结构在1.8中是hash散列表+链表+红黑树。散列表装的是Entry键值对，发生冲突时，会用equals或者地址比较方式比较是否是同一个键，如果不是就加入链表，如果链表的个数大于8，就会看散列表长度是否大于64，不是就进行扩容，扩容时采用高低链表的方式，并且先组装链表然后再放入到新的Entry数组。 大于64会把链表变成红黑树。
  3 红黑树和AVL树的搜索都是O（logn），AVL稍微快一点。但是AVL树的插入时进行调整的频率比红黑树高一些，导致插入效率不太高。红黑树允许一定的不平衡，也就是说红黑树是一种不大严格的AVL树。也可以说是一个折中方案。AVL要求最多一层的不平衡，而红黑树最多可以是两倍。
  4 （这个答得不太多，看了一下源码自己总结一下）速度上将链表的O（n）转成了红黑树的O（logn），防止出现长链表的查询。红黑树的个数被删为6，或者当前节点为null的时候会回退回链表。
  红黑树put时先将如果key没有实现comparable接口，则会调用tieBreakOrder函数System.identityHashCode方法排序比较
  5 put流程主要是调用putval函数，hash寻址后如果位置为空就创建节点直接放入，如果不是空并且当前位是链表，就一个个和链表的对比插到链表后面，对比方式就是equals和，
  如果对比超过了8次，就要进行树化判断。然后resize判断
  6 put不是线程安全的，可能会导致同一个hash表扩容时，如果有一个节点put进hash，因为是尾插入法，可能导致导致刚刚异步插入的新节点被覆盖掉。
  7 加同步锁或者自旋锁。相当于hashtable的实现了
  8 据说是考虑到热点数据的原因,即最近插入的元素也很可能最近会被使用到。所以为了缩短链表查找元素的时间,所以每次都会将新插入的元素放到表头。
  9 扩容的三个条件table为null的时候扩容、数组中的元素个数达到阈值扩容、数组中的链表个数达到8以上，并且数组的大小小于64
  扩容阈值为0.75是通过泊松分布计算得到的理论最优。扩容阈值越大，插入发生hash冲突概率增大，反着减小但是浪费空间，需要折中方案。
  10 如果能确定大小或者范围的话直接构造时取这个输入大小参数；复写hash方法减小冲突；合理设置负载因子；
  11 （这个参考上面大佬的，学到了）128。 n-1就是高位是0，低位都是1，这样&完之后，结果各个位置的取值取决于hash，如果构造时传入60的话，hash表大小会初始化为64，插入到48个时会出现扩容，所以选择128也有这个原因。

  1 赞同 0 条回复

  登录以回复
• 西西弗斯的石头 永久会员 2023年6月12日 下午3:51

  1、HashMap 了解吗？平时在什么地方使用过它呢？（说明：发现没有，我喜欢问使用场景，希望大家也是能够思考使用场景的，因为掌握了这个，你说话更加有说服力）

  了解，比如通过名称指定配置信息，建立对象与对象的映射关系，设置缓存从而可以避免频繁查询数据库和文件系统，提高效率，使用hashmap存储请求路由规则，根据路由规则以及请求参数查找对应的服务器列表。

  2、HashMap 底层数据结构说一下？（指导：直接说最新的即可，不需要去对比以前的版本，因为面试官也听烦了，另外在说的时候，为了你语言的严谨，一定要强调下是哪个JDK版本的哈）

  JDK >= 1.8的时候是数组+链表+红黑树，Hash值产生碰撞时，链表长度>8会由链表转换成红黑树（将链表转换成红黑树前判断，如果当前数组长度小于64，那么选择先数组扩容，而不是转换成红黑树），当红黑树节点被删为6的时候，会由红黑树转换成链表，就是二者的性能临界点。

  HashMap的默认初始化大小为16（注意：当HashMap对象被创建时，并不直接创建内部数组，而是第一次添加元素时再创建内部数组，这种懒加载方式可以减少不必要的内存占用），之后每次扩充容量变为原来的2倍，并且HashMap总是使用2的幂作为哈希表的大小。

  3、为什么用红黑树呢？用平衡二叉树不可以吗？或者你讲一讲他们各自的优缺点吗？

  HashMap底层使用红黑树的主要原因是为了在桶中存在大量键值对时提高查找效率。当桶中的链表长度较长时，查找效率可能会变得比较低，这时可以将链表转换为红黑树，以便在O(log n)的时间复杂度内查找键值对。

  平衡二叉树的初衷是解决普通二叉树在频繁的插入，删除等动态更新的情况下出现的时间复杂度退化的问题。

  红黑树与avl树对比：

  红黑树是近似平衡的。相比于avl树，检索时效率差不多，都是通过平衡来二分查找，但是对于插入删除等操作提高很多。红黑树不像avl树一样追求绝对平衡，它允许局部很少的不完全平衡，这样对于效率影响不大，但省去了很多没有必要的调平衡操作，avl树调平衡有时候代价很大，所以效率不如红黑树。

  红黑树高度只比高度平衡的AVL树的高度（log2 n）仅仅大一倍，性能上却好很多。

  AVL树是一种高度平衡的二叉树，所以查找的非常高，但是有利就有弊，为了维持这种高度平衡，要付出更多代价，每次插入删除都要调整，比较复杂耗时。对于有频繁的插入和删除操作的数据集合，使用AVL树的代价就有点高了。红黑树的插入，删除，查找各种操作性能都比较稳定。

  4、为什么选择 8 之后转为红黑树呢？另外链表转为红黑树之后，还会继续转为链表吗？

  防止链表过长，从而导致查询效率过低，红黑树有自平衡的特点，可以防止不平衡的情况发生，时间复杂度由n变为lgn。

  更多还是为了防止用户自己实现了不好的哈希算法时导致链表过长，从而导致查询效率低，转化为红黑树更多是一种保底政策。

  红黑树的个数被删为6的时候会回退回链表。

  5、简单描述下 put 的流程？可以说一下JDK为了效率更快，在 put 的时候，做了哪些优化不？

  HashMap提供了put方法添加元素，putval方法只是给put方法调用的一个方法，如果数组为空或者长度为0就扩容，不为空的话，如果定位到的数组位置有元素就和要插入的key比较，如果key相同就直接覆盖，如果key不同就判断p是否是一个树节点是否是一个树节点,如果是就调用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);将元素添加进去，如果不是就遍历链表插入（插入链表的尾部），当链表长度大于阈值并且数组长度大于等于64就会执行链表转红黑树的操作，否则就只是对数组扩容。

  jdk8在扩容时计算数组元素下标时做了优化：

  jdk1.7:

  重新计算每个元素的哈希值

      static int indexFor(int h, int length) {
          // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
          return h & (length-1);
      }
  

  jdk1.8:

  在扩容时没有像JDK1.7那样，而是通过高位运算e.hash & oldCap，来确定元素是否需要移动。

  do {
      next = e.next;
      // resize前后，桶的位置未变化
      // 尾插法插入链表
      if ((e.hash & oldCap) == 0) {
          if (loTail == null)
              loHead = e;
          else
              loTail.next = e;
          loTail = e;
      }
      // resize后新产生的桶
      // 尾插法插入链表
      else {
          if (hiTail == null)
              hiHead = e;
          else
              hiTail.next = e;
          hiTail = e;
      }
  } while ((e = next) != null);
  

  //不同移动
  key1.hash = 10 0000 1010
  oldCap = 16 0001 0000
  

  //需要移动
  key2.hash = 10 0001 0001
  oldCap = 16 0001 0000
  

  

  6、多线程情况下，put 是线程安全的吗？可以简单举个例子，说一下哪里不安全吗？

  不安全，如果两个线程同时对一个HashMap操作，一个线程在其中添加或删除元素，另一个正在遍历该HashMap，这种情况可能导致一个线程看到不一致的状态。

  import java.util.HashMap;
  
  public class SynchronizedHashMapExample {
  
      public static void main(String[] args) throws InterruptedException {
  
          HashMap map = new HashMap<>();
  
          // 添加元素
          map.put("A", 1);
          map.put("B", 2);
          map.put("C", 3);
  
          // 创建锁对象
          Object lock = new Object();
  
          // 第一个线程遍历HashMap
          Thread thread1 = new Thread(() -> {
              synchronized (lock) {
                  for (String key : map.keySet()) {
                      System.out.println(key + ": " + map.get(key));
                  }
              }
          });
  
          // 第二个线程在遍历过程中删除一个元素
          Thread thread2 = new Thread(() -> {
              synchronized (lock) {
                  map.remove("B");
              }
          });
  
          thread1.start();
          thread2.start();
  
          thread1.join();
          thread2.join();
      }
  }
  

  7、如果我想要让 hashmap 变成线程安全的，你觉得可以怎么做？（有时候会扯到 concurrentHashMap，不过咱们这里先不追击这个）

  jdk7死循环例子：

  5张图讲明白JDK1.7下的HashMap死循环（原理+实战) – 知乎 (zhihu.com)

  关键点：线程2先扩容完毕，此时布局是这样的，但是线程1却还在按照只有两个桶的时候的布局来进行扩容，读取数据的时候却又是按照T2已经扩容完毕的数据来进行。

  可以使用同步机制：可以使用Java中的synchronized关键字来保证多个线程对HashMap的同步访问。在使用synchronized关键字时，需要确保所有对HashMap的访问都在同步代码块中完成，以保证线程安全。

  8、头插法会导致死循环，那你觉得在以前的版本中，为啥会使用头插法呢？

  考虑到热点数据的原因，即最近插入的元素也很可能最近会被使用到，所以为了缩短链表查找元素的事件，所以每次都插入到表头，并且头插法插入速度最快，找到数组位置就直接找到插入位置，但是可能会造成多线程同时扩容出现死循环。

  9、那我们再说一说 HashMap 的扩容吧，什么时候会扩容呢？你觉得负载因子为啥选择 0.75 呢？

  • table为null的时候扩容
  • 数组中的元素个数达到阈值扩容
  • 数组中的链表个数达到8以上，并且数组的大小小于64

  0.75是为了触发扩容，减少冲突发生的概率，加载因子很大，扩容条件就会苛刻，hash碰撞概率变高，每个链表长度都很长，查询速度变慢，太小又会导致扩容频率变高，，内存消耗变大。

  10、频繁扩容会导致效率比较低下，那你觉得在平时，在实际的开发场景中，可以怎么优化来避免频繁扩容呢？

  • 根据业务，给hashmap初始大小一个合理的值减少扩容次数。
  • 选择合适的负载因此控制hashmap的扩容频率
  • 避免hashmap中使用复杂对象作为键，这会增加哈希算法的复杂度，如果使用确保其类覆盖hashcode方法和equals方法。

  11、一个场景题：只存60个键值对，需要设置初始化容量吗？设置的话设置多少初始化容量比较好呢？

  需要，否则就需要多次扩容，取2的幂次方，也就是128即可，因为2的幂次高位是1其余位置是0，当进行hash运算时，(n-1)&hash，n-1就是高位是0，低位都是1，这样&完之后，结果各个位置的取值取决于hash，如果不是2的整数次幂必然会有0位，0与任何&肯定为0，会造成更多的哈希冲突。

  1 赞同 1 条回复

  登录以回复
  • upward ᯤ⁶⁰ᴳ 永久会员 @ 西西弗斯的石头 2023年6月13日 上午10:10

    大佬的回答中为什么用头插法好像有点问题，1.7 1.8都是要遍历链表的，因为要选出高低链表

    登录以回复