今天我们就面试会问到关于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算法是如何实现的？
"^"为异或符号其计算机符号为xor，相同为0，相异为1，如0^0=0 、0^1=1.">>>"为右移动符号，左侧补零。图中h>>>16就是将h的高16位换到h的低16位，而之前的高16位全补零。
这里有童鞋可能就会问了，为什么要进行这个向右移16位且异或的操作？
4、HashMap是如何处理Hash碰撞的？
HashMap采用的是链表法，将hash值相同的元素放在一个链表下。
5、增加元素的方法是怎么实现的？
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值去找桶的位置：
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面经 你想要的我这里都有