HashMap源码分析之面试必备-LMLPHP

    今天我们就面试会问到关于HashMap的问题进行一个汇总,以及对这些问题进行解答。

    1、HashMap的数据结构是什么?

    2、为啥是线程不安全的?

    3、Hash算法是怎样实现的?

    4、HashMap是如何处理Hash碰撞的?

    5、增加元素的方法是怎么实现的?

    6、获取元素的方法时怎么实现的?

  

    以上这些问题在面试中出现的频率往往比较高,在对HashMap不太了解的情况下,往往很难将这些问题答全,笔者就带领对这块不熟悉的小伙伴们一起,一步一步解析以上的问题。

1、HashMap的数据结构是什么?

    对于这个问题,笔者建议回答的时候对JAVA版本进行区分,因为不同版本下,HashMap的结构是有些差异的。

    回答:在JDK1.8之前HashMap是数组+链表的形式,JDK1.8包括之后是数组+链表+红黑树。本文讲的HashMap是基于JDK1.8。

2、为啥是线程不安全的?

    多个线程某个时刻同时操作HashMap并执行put操作,且Hash值相同,这个时候需要解决冲突。很多方法如put() 、addEntry() 、resize() 等都不是同步的。

3、Hash算法是如何实现的?

HashMap源码分析之面试必备-LMLPHP

    "^"为异或符号其计算机符号为xor,相同为0,相异为1,如0^0=0 、0^1=1.">>>"为右移动符号,左侧补零。图中h>>>16就是将h的高16位换到h的低16位,而之前的高16位全补零。

HashMap源码分析之面试必备-LMLPHP

    这里有童鞋可能就会问了,为什么要进行这个向右移16位且异或的操作?

HashMap源码分析之面试必备-LMLPHP

4、HashMap是如何处理Hash碰撞的?

HashMap采用的是链表法,将hash值相同的元素放在一个链表下。

 5、增加元素的方法是怎么实现的?

HashMap源码分析之面试必备-LMLPHP

 1 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
 2                    boolean evict
 3 ) {
 4         Node<K,V>[] tab; Node<K,V> p; int n, i;
 5         // 如果说桶(也就是数组,以下都用"桶"代替)为空,或者桶大小为0 则进行初始化
 6         // 这里要区桶大小 和 桶内元素的大小 桶大小是指桶装东西的能力
 7         // 桶内元素大小 是指桶装了多少东西 
 8         if ((tab = table) == null || (n = tab.length) == 0)
 9             n = (tab = resize()).length;
10         // 这里是帮助元素查找元素在桶中的定位 如果定位的位置没有元素 那么
11         // 直接将元素放入桶的该位置就行    
12         if ((p = tab[i = (n - 1) & hash]) == null)
13             tab[i] = newNode(hash, key, value, null);
14         else {
15         // 运行到这说明定位的位置已经有元素了
16             Node<K,V> e; K k;
17         // 既然有人霸占元素的位置,那么就要与该元素进行对比,看看自己的Hash值和
18         // key值是不是和该位置的元素一直,如果都一直就记录下该元素以下为e
19         // 说明有一个和我插入元素的key一样的元素 后续可能要用新值替换旧值
20             if (p.hash == hash &&
21                 ((k = p.key) == key || (key != null && key.equals(k))))
22                 e = p;
23         // 如果只是Hash值相等而key不等,这里就是Hash碰撞啦,要解决hash碰撞
24         // hashMap采用的是链地址法 就是碰撞的元素连成一个链表 这里由于链表
25         // 如果太长就会树化成红黑树,以下是判断p也就是桶里放的是不是红黑树
26             else if (p instanceof TreeNode)
27         // 是红黑树 我们就把节点放入红黑树 注意:这里也不是一定插入到树中,
28         // 因为如果我们要插入的元素和红黑树中某个节点的key相同的话,也会考虑
29                 // 新值换旧值的问题
30                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
31             else {
32         // 跳到这 说明p不是树,而是链表 binCount用来记录链表中元素的个数,那么
33         // 为啥要记录链表中元素的个数呢?主要判断链表是否需要树化成红黑树
34                 for (int binCount = 0; ; ++binCount) {
35                     // e的后一个节点为空 那么直接挂上我们要插入的元素
36                     if ((e = p.next) == null) {
37                         p.next = newNode(hash, key, value, null);
38                         // TREEIFY_THRESHOLD 是树化的阈值且其值为8
39                         // 这里要注意:我们要插入的节点p是还没有加到binCount中的
40                         // 也就是说这里虽然binCount>=7就可以树化,其实真正的树化
41                         // 条件是链表中元素个数大于等于8
42                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
43                             treeifyBin(tab, hash);
44                         break;
45                     }
46                     // 待插入的key在链表中找到了,记录下来然后退出
47                     if (e.hash == hash &&
48                         ((k = e.key) == key || (key != null && key.equals(k))))
49                         break;
50                     p = e;
51                 }
52             }
53             // 说明找到了key相同的元素
54             if (e != null) { // existing mapping for key
55                 V oldValue = e.value;
56                 // 判断是否需要旧值换新值,默认情况下是允许更换的
57                 if (!onlyIfAbsent || oldValue == null)
58                     e.value = value;
59                 // 这个方法点进去就是个空方法,主要是为了给继承HashMap的
60                 // LinkedHashMap服务的
61                 afterNodeAccess(e);
62                 return oldValue;
63             }
64         }
65         // 修改次数+1
66         ++modCount;
67         // 看下达到扩容的阀值没
68         if (++size > threshold)
69         // 扩容 ,在本方法的前面需要初始化的时候也出现过
70             resize();
71          // 这个方法同样也是为LinkedHashMap服务的
72         afterNodeInsertion(evict);
73         // 没找到元素 就返回空
74         return null;
75     }
 

 6、获取元素的方法时怎么实现的?

    使用hash值去找桶的位置:

HashMap源码分析之面试必备-LMLPHP

 1    final Node<K,V> getNode(int hash, Object key) {
 2         Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
 3         // 桶不为空 并且桶的元素大于0 同时定位的位置元素还不为空 那就顺藤摸瓜
 4         if ((tab = table) != null && (n = tab.length) > 0 &&
 5             (first = tab[(n - 1) & hash]) != null) {
 6             // 第一个元素是不是我们要找的啊?判断一下,是就返回
 7             if (first.hash == hash && // always check first node
 8                 ((k = first.key) == key || (key != null && key.equals(k))))
 9                 return first;
10             if ((e = first.next) != null) {
11             // 第一个元素不是我们要找的,而且后面还接着元素 判断一下是不是树
12                 if (first instanceof TreeNode)
13                     // 是树 按照树的获取节点方法去获取
14                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);
15                 // 到这说明是链表了 那就按照链表的方式去循环
16                 do {
17                     if (e.hash == hash &&
18                         ((k = e.key) == key || (key != null && key.equals(k))))
19                         return e;
20                 } while ((e = e.next) != null);
21             }
22         }
23         return null;
24     }

7、最后插播一下HashMap中的属性

 1 // 初始容量1向左移动4位为16
 2  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 3  // 最大容量1向左移30位
 4  static final int MAXIMUM_CAPACITY = 1 << 30;
 5  // 加载因子 也就是桶大小使用要是超过0.75 那么就要考虑扩容了
 6  static final float DEFAULT_LOAD_FACTOR = 0.75f;
 7  //  链表太长 要变树的阀值
 8  static final int TREEIFY_THRESHOLD = 8;
 9  // 树变成链表的阀值
10  static final int UNTREEIFY_THRESHOLD = 6;
11   // TREEIFY_THRESHOLD达到8也不一定树化,还要容量达到64
12  static final int MIN_TREEIFY_CAPACITY = 64;

 下一期我们对今天讲的put、get方法内涉及到的重要的方法进行讲解。拜了个拜!

大量面试经验以及学习资料书籍请关注微信公众号:AVAJ
回复"offer"进行获取
365篇大厂java面经 你想要的我这里都有

08-17 16:38