仅hashmap一道面试题我就搞定了面试官成功入职面试官：我裂开了

预计阅读需要19分钟

HashMap应该算是Java后端工程师面试的必问题，因为其中的知识点太多，很适合用来考察面试者的Java基础。

开场

面试官: 你先自我介绍一下吧！

安琪拉: 我是安琪拉，草丛三婊之一，最强中单（钟馗不服）！哦，不对，串场了，我是**，目前在--公司做--系统开发。

面试官: 看你简历上写熟悉Java集合，HashMap用过的吧？

安琪拉: 用过的。(还是熟悉的味道)

面试官: 那你跟我讲讲HashMap的内部数据结构？

安琪拉: 目前我用的是JDK1.8版本的，内部使用数组 + 链表红黑树；

安琪拉: 方便我给您画个数据结构图吧：

仅hashmap一道面试题我就搞定了面试官成功入职面试官：我裂开了

面试官: 那你清楚HashMap的数据插入原理吗？

安琪拉m 1 p 2 ,: 呃[做沉思状]。我觉得还是应该画个图比较清楚，如下：

仅hashmap一道面试题我就搞定了面试官成功入职面试官：我裂开了

  1. 判断数组是否为空，为空进行初始化;
  2. 不为空，计算 k 的 hash 值，通过(n - 1) & hash计算应当存放在数组中的下标 index;
  3. 查看 table[index] 是否` ; ( 2 . 7 } K $存在数据，没有数据就构造一个Node节点存放在 tabD 3 Q a , Cle[index] 中；
  4. 存在数! 4 ` r据，说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等，相等M Q o Z & j o o，C F D , y用新的value替换原数据(onlyIfAb* I Ssent为fa[ ; , ? U _ Zlse)；
  5. 如果不相等，判断当前节点类型是不是树型节点，g ] j } 4 T如果是树型节点，[ ! a创造树型节点插入红黑树中；
  6. 如果不是树型节点，创建普通Node加入链表中；判l : r A m X断链表长度是否大于 8， 大于的话链表转换为红黑树；
  7. 插入完成之后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的二倍。

面试官:; s J 刚才你提到HashMap的初始化，那HashMap怎么设定初始容量大小的吗？

安琪拉: [这也算问题？?] 一般如果new HashMap() 不传值，默认大小是16，负W Z k载因子是0.75， 如果自己传入初始大小k，初始化大小为 大于k的 2的整数次方，例如如果传10，大小为16。（补充说明:实现代码如下）

static fi] F N U E ~nal int tableSizeFor(int cap) {
  int n = cap - 1;
  n |= n >&gg 6 S E e ; Q 4t;> 1;
  n |= n >>> 2;
  n |= n >>> 4;
  n |= n >>&C v a 0 m k e jgt; 8;
  n |= n >>> 16;
  return (n < 0) ? 1 : (n >9 e 7 ; S %= MAXIW ; v 6 @ KMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

补充说明：下图是详细过程，算法就是让初始二进制右移1，2，4，8，16位，分别与自己异或，把高位第一个为1的数通过不断右移，把高位为1的后面全变为1，111111 + 1 = 18 f & b000000 = （符合大于50并且是2的整数次幂 ）

面试官: 你提3 V 1 b ^ p |到hash函数，你知道HashMap的哈希函数V b ~怎么设计的V E `吗？

安琪拉: [问的还挺细] hash函数是先拿到通过key 的hashcode7 6 & U ~ l，是32位的int值，然! ] I后让hashcode的高16位和低16位进行异或操作。

仅hashmap一道面试题我就搞定了面试官成功入职面试官：我裂开了

面试官: 那你知道为什么这么设计吗？

安琪拉: [这也@ q % U要问]，这个也叫扰动Q [ J 7 d B p l函数，这么设计有二点原因：

  1. 一定要尽可能降低hash碰撞，D I 1 G 0 1 4 B U越分散越好；
  2. 算法一定要尽可能高效，因为; = i n r I这是高频操作, 因此采用位运算；

面试官: 为什么采用1 C . P ` l F [ ohashcode的高16位和低16位异或能降低hash碰撞？hash函数能不能直b D # s =接用key的hashcode？

[这问题有点刁钻], 安琪拉差点原地了，恨不得出biubiubiu 二一三连招。

安琪拉: 因为key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值。int值范围为**-2147483648~2147483647**，前后加起来大概z ^ p 1 1 U *40亿的映射空间。只要哈希g - /函数映射{ 2 d f得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的V B p ( o。你想，如果HashMap数组的初始大小才C V 8 A16，用之前需要对数组的长度取模运算，得到的余数才能用来n j | U #访问数组下标。(来自知乎-胖君)

源码中模运算就是把散列值和数组长度-1做一个\"与\V : f ` Y W"操作，位运算比%运算Q n $ C i ~ _要快。

bucketIndex = indexFor(hash, table.length);

static int i8  C endexFor(int h, int length) {
     return h & (lengte x ^ K T : F 7 h-1);
}

顺便说一下，这也正好解释了为什么HashMaK K - 9 I wp的数组长度要取2的整数幂。因为; Q 6 m 7 { r G这样（数组长度-1）正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。

  10100101 110001v = j p00 00100101
& 00000000 00000000 00001111
-----------------------------x Y ]-----
  00000000 00000000 00000101    //高位全部归零，只保留末四位

但这时候问题就来了，这样就算我的散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。更要命的是如果散列本身做得不好，分布上成等差数列的漏洞，如果正好让最后几个低位呈现规律性重复，就无比蛋疼。x ) z Y

时候“扰动函数”的价值就2 9 . U l i C 9 +体现出来了，说到这里大家应该q % k ? R h ^ 3 n猜出来了。看下面这个图，

仅hashmap一道面试题我就搞定了面试官成功入职面试官：我裂开了

右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

最后我们来看一个实验：随机选取了352个字符串，在他们散! * !列@ f G R ( D z : 8值完全没有冲突的前提下，对它们做低位掩码，取数组下标。

仅hashmap一道面试题我就搞定了面试官成功入职面试官：我裂开了

结果显示，当Hash^ # B h 6 7Map数组长度为512的时候（2的九次方），也就是用掩码取低9位的时候，~ o G r在没有扰动函数的情况下，发生了103次碰撞，接近30%。而在使用了扰动函数之后只有92次碰撞。碰撞减少了将近10%。看来扰动函数确实还是有功效的。

另外Jaj = {va1.8相J 5 / ( v比1.7做了调整，3 z o g1.7做了四次移位和四次异或，但明显Java 8觉得扰动做一次就够了，做4次的话，多了可能边际效用也不大，所谓为了效率考虑就改成一次了。

下面是1.7Z @ = , L $ s O的hash代码：

statica * W 2 Q k I I int hash(int h) {
    h ^= (h >>> 20) ^ (h2 F [ - ) >>> 12);
    reQ L , KtuO / 7rn h ^ (h >>>j 2 $ N 7) ^ (h >>> 4);
}

面试官: 看来做过功课，有点料啊！是v R ^不是偷偷看了安琪拉的博客, 你刚刚说到1.8对hash函数做了优化，1.8还有别的优化吗？

安琪拉: 1.8还有三点主要的优化：( Q [ k * 8 j | z

  1. 数组+链表改成了数组+链表或红黑树；
  2. 链表的插入方式从头插法改成了尾插法，简单说就是插入时，如果W l x X v g数组位置上已经有元素，1.7将新元素放到数组中，原始节点作为u N 3新节点的后继节点，L & * m 9 m W | i1.8遍历链表，将U - !元素放置X i P $到链表的最后；
  3. 扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；
  4. 在插入时，1.7先判断是否需要扩容，再插入，1v p v $ w r m.8先进行插入，插入完成再判断是否需要扩容；

面试官: 你分别跟我讲讲为什么要做这几点优化；

安琪拉: 【咳咳，果然是连环炮】

  1. 防止发生hash冲突，链表长度过长，将时间复杂度由O(n)降为O(logn);
  2. 因为1.7头插法扩容时，头插法会使链表发生P e k R J R B e J反转，多线程环境下会产生环； A线程在插入节点B，B线程Z 0 A % 1 _也在插入，I % = / . 1 t 5遇到容量不够开始扩容，重新hash，放置元素，采用头插法，后遍历到的B节点放入了头部，这样形成了环，如m N K $ M ? |下图所示： 1.7的扩容调用tranT x f E l _ Hsfer代码，如下所示： void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : ta, ^ U G ; u / % @ble) { while(null != e) { Entry<K,V> next = e.next; if (rehaS R ; S 4 msh) { e.hash =z , f - null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; //AW o ; u / * % A h线程如果执行到这一行挂起，B线程开始进行扩容 newTable[i] = eP / 1 o q; e = next; } } } 复制代码
  3. 扩容的时候为什么1.8 不用重新hash就可以直接定位[ @ ) A 3 1 e g {原节点在新数据的位置呢? 这是由于扩容是扩大为原数组大小的2倍，用于计算数组位置的掩码仅仅只是高位多了一个1，怎么理解呢？ 扩容前长度为16，用于计算(n-1) & hash 的二进制n-1为0000 1111，扩容为32后的二进制就高位多了1，为0001 1111。 因为是&a R F X v ! Gmp; 运算，1和任何数 & 都是它本身，那就分二种情况，如下图：原数据hashcode高位第4位为0和高位为1的情况； 第四位高位为0，重新hash数值不变，第四位为1，重新hash数值比原来大16（旧数组] a :的容量）

面试官: 那HashMap是线程安全的吗？

安琪= 5 B ~ m i 7拉: 不是，在多线程环境下l / J B，1.7 会产生死循环、8 e { L * f [ z .数据丢失、数据覆盖的问题，1.8 中会有数据覆盖的问题，以1.8为例] & I 6 V，当A线/ u & w程判断index位置为空后正好挂起，B线程开始G v Y ] $ V g ~ P往index位置的写入节点数据，这时A线程恢复现场，执行赋值操作，就把A线程的E n R ] t * # N r数据给覆盖了；还有++size这个地方也会造成多线程F | 7 w ! a同时扩容等问题。

final V putVal(int has! 6 kh, K key, V value, boolean onlyIfAb: m s 0 [  ] ; 1sent,
               boolean evict) {
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = rl * 7 } 1 desize()).length;
  if ((p = tab[i = (n - 1) &a[ 2 `mp; hash]) == null)  //多线程执行到这里
    tab[i] = newNode(hash, key, value, null);
  e@ E { V ? N t J *lse {
    Node<K,V> e; K k;
    if (p.hash == hash &&
        ((k = p.kek h y 0y) == key || (ku % f u 9ey != null && keW w ! W 3 n c G yy.equals(k))))
      e = p;
    else if (p ig e 3 i anstanceof TreeNode)
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, valj x M 8  7 0 O ^ue);
    else {
      for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
          p.next = newNode(hash, key, value, null);
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab,O 2 : hash);
          break;
        }
        if (e.hash == hash &&
            ((kA } _ z = 9 ^ ? E = e.key) ==S P O key || (key != null && key.equals(k))))
          break;
        p = e;
      }
    }
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      if (!on5 X O V E s OlyIfAbsent || oldValt B Aue == null)
        e.value = value;
      afterNodeAccess(e);
      return oldValue;
    }
  }
  ++modCount;
  if (++size > thresN 9 8 `hold` E x R s T G r) // 多个线程走到这，可能重复resize()
    resl w A l T r ] T Size();
  afterNodeInsertion(evicto l D 1 q y);
  return null;
}

面试官: 那) i ^你平常怎么解决这个线程不安全B ^ , q o +的问题？

安琪拉: Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以实现线程安全的Map。

HashTable是直接在操作方法上加synchrW y ( = Xonized关键字，锁住整个数组，粒度比较大，Collections.synchronizedMap是使用CollF w D I 4 nections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现；ConcurrentHashMap使用分段锁，降低了锁粒度，让并发度大大提高。

面试官: 那你知道f 0 b 2 6 3ConcurrentHashMap的分段锁的实现原理吗？

安琪拉: 【天啦撸! 俄罗斯套娃，一个套一个】ConcurrentHashMap成员变量使用volatile 修饰，免除了指令重排序，同时保证内U 6 , r x L 6 5存可见性，另外使用CAS操作和synchronized结合实现赋值m } % B e S e操作，多线程操作只会锁住当前操作索引的节点。

如下图，线程A锁住A节点所在链表，线程B锁住B节点所在链表，操作互不干涉。

仅hashmap一道面试题我就搞定了面试官成功入职面试官：我裂开了

面试官: 你前面提到链表转红黑树是链表长度达到阈值，这个阈值是多少？

安琪拉: 阈值是8，红黑树转链表阈值为6

面试官: 为什么是8，不是16，32甚至是7 ？又为什么红黑树转链表的阈值是6，不是8了呢？

安琪拉: 【你去问作者& m 9 m啊！天啦撸，biubiubiu 真想213连招】因为作者就这+ 8 ? , X么设计的，哦，不对，因为经过计算，在hash函数设计O 8 D j j P e h p合理的情况下，发生hash碰撞8次的几率为百万分之6，概率说话。。因w J + v N X x为8够用了，至于为什么转回来是6，因为如果hash碰撞次数在8附近徘徊，会一直发生链表和红黑树的转w } _ .化，为了预防这种情况的发生。

面试官: HashMap内部节点是有序的吗？

安琪拉: 是无序的，根据hash值随机插入

面试官: 那有没有有序的Map？

安a ; 4 t琪拉: LinkedHashMap 和 TreeMap

面试官: 跟我讲讲LinkedHashMap怎么实现有序的？

安琪拉:1 [ Z O $ @ LinkedHy x & {asV 9 whMap内部维护了一个单链表，有头尾节点，同时L% 7 | linkedHashMap节点Entry内部除了继承HashMap的Node属性，还有before 和 after用于标识前置节点和后置节点。可以实现按插入的顺序或访问顺序排序。

/**
 * The head (eldes4 t |t) of] j S the doubly linked list.
*/
tran) [ & @sient LinkedHashMap.Entry<K,V> head;

/**
  * The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K4 K Q  ; e,V> tail;
//链接h t ! } Y K新加入的p节点到链表后端
private void linkNodeLast(LinkedHashX 3 T w EMap.Entry<K,V> p) {
  LinkedHashMap.Entry<* d C o o b rK,V> last = tail;
  tail = p;
  if (last == null)
    head = p;
  else {
    p.before = last;
    l% F k 8ast.after = p;
  }
}
//LinkedHashMap的节点类
static class Entry<K,V> extends HashM[ M R F r 7 = ] Oap.Node<K,V> {
  Entry<K,V> before, after;
  Entry(int hash, K key, V value, N& # & n dode<K$ N , 9 O,V> next) {
    super(hash, key, value, next);
  }
}

示例代码：

public static void main(String[] args) {
  Map<String, String> map = new LinkedHashMap<String, SD X Y k 0tring>();
  map.put(\"1\", \"安琪拉\");
  map.put(\"2\", \"的\");
  map.put(\"3\", ] B U c\"博客\) L  4 T");

  for(Map.Entry<String,String> item: map.entrySet()){
    System.out.println(item.getKeyK 6 a = () + \":\" + item.getValue());
  }
}
//console输出
1
2
3

面试官: 跟我讲讲TreeMap怎么实现有序的？

安琪拉：Tree ) ! 0 6 Q 0 veMap是按照Key的自然顺序或者Comprator的顺序进行排序，内部是通过红黑树来实现。所以r | p j要么key所属的类实现Comparable接口，或者自定, ) a 5 J [ _义一个实现了Comparator接口的比较器，传给TreeMap用户key的比较。

面试官: 前面提到通过CAS 和 sy R S G k gnchronized结合实现锁粒度的降低，你能给我讲讲CAS 的实现以及synchronized的实现原理吗？

安琪拉: 下一期咋们再c * r o V ^约时间，OK？

面试官: 好吧，回去等通知吧！

整理了一些Java方面的架构、面试资料（微服务、Z i o | Z ) K j集群、分布式、中间件等），有需要的b l , E -小伙伴可以关注私信【555】，无套路自行领取

本文系本站编辑转载，文章版权归原作者所有，内容为作者个人观点，转载目的在于传递更多信息，并不代表本站赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请与本站联系，本站将在第一时间删除内容！
上一篇

解密四维空间的超立方体

下一篇

中通为成都市民配送30万单蔬菜，生态圈协同展现同城配送能力

你也可能喜欢

  • 暂无相关文章!

发表评论

您的电子邮件地址不会被公开。 必填项已用 * 标注

提示：点击验证后方可评论！

插入图片
返回顶部