今天我们就面试会问到关于 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, 增加元素的方法是怎么实现的?
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
- boolean evict
- ) {
- Node<K,V>[] tab; Node<K,V> p; int n, i;
- // 如果说桶 (也就是数组, 以下都用 "桶" 代替) 为空, 或者桶大小为 0 则进行初始化
- // 这里要区桶大小 和 桶内元素的大小 桶大小是指桶装东西的能力
- // 桶内元素大小 是指桶装了多少东西
- if ((tab = table) == null || (n = tab.length) == 0)
- n = (tab = resize()).length;
- // 这里是帮助元素查找元素在桶中的定位 如果定位的位置没有元素 那么
- // 直接将元素放入桶的该位置就行
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null);
- else {
- // 运行到这说明定位的位置已经有元素了
- Node<K,V> e; K k;
- // 既然有人霸占元素的位置, 那么就要与该元素进行对比, 看看自己的 Hash 值和
- // key 值是不是和该位置的元素一直, 如果都一直就记录下该元素以下为 e
- // 说明有一个和我插入元素的 key 一样的元素 后续可能要用新值替换旧值
- if (p.hash == hash &&
- ((k = p.key) == key || (key != null && key.equals(k))))
- e = p;
- // 如果只是 Hash 值相等而 key 不等, 这里就是 Hash 碰撞啦, 要解决 hash 碰撞
- // hashMap 采用的是链地址法 就是碰撞的元素连成一个链表 这里由于链表
- // 如果太长就会树化成红黑树, 以下是判断 p 也就是桶里放的是不是红黑树
- else if (p instanceof TreeNode)
- // 是红黑树 我们就把节点放入红黑树 注意: 这里也不是一定插入到树中,
- // 因为如果我们要插入的元素和红黑树中某个节点的 key 相同的话, 也会考虑
- // 新值换旧值的问题
- e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
- else {
- // 跳到这 说明 p 不是树, 而是链表 binCount 用来记录链表中元素的个数, 那么
- // 为啥要记录链表中元素的个数呢? 主要判断链表是否需要树化成红黑树
- for (int binCount = 0; ; ++binCount) {
- // e 的后一个节点为空 那么直接挂上我们要插入的元素
- if ((e = p.next) == null) {
- p.next = newNode(hash, key, value, null);
- // TREEIFY_THRESHOLD 是树化的阈值且其值为 8
- // 这里要注意: 我们要插入的节点 p 是还没有加到 binCount 中的
- // 也就是说这里虽然 binCount>=7 就可以树化, 其实真正的树化
- // 条件是链表中元素个数大于等于 8
- if (binCount>= TREEIFY_THRESHOLD - 1) // -1 for 1st
- treeifyBin(tab, hash);
- break;
- }
- // 待插入的 key 在链表中找到了, 记录下来然后退出
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- break;
- p = e;
- }
- }
- // 说明找到了 key 相同的元素
- if (e != null) { // existing mapping for key
- V oldValue = e.value;
- // 判断是否需要旧值换新值, 默认情况下是允许更换的
- if (!onlyIfAbsent || oldValue == null)
- e.value = value;
- // 这个方法点进去就是个空方法, 主要是为了给继承 HashMap 的
- // LinkedHashMap 服务的
- afterNodeAccess(e);
- return oldValue;
- }
- }
- // 修改次数 + 1
- ++modCount;
- // 看下达到扩容的阀值没
- if (++size> threshold)
- // 扩容 , 在本方法的前面需要初始化的时候也出现过
- resize();
- // 这个方法同样也是为 LinkedHashMap 服务的
- afterNodeInsertion(evict);
- // 没找到元素 就返回空
- return null;
- }
6, 获取元素的方法时怎么实现的?
使用 hash 值去找桶的位置:
- final Node<K,V> getNode(int hash, Object key) {
- Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
- // 桶不为空 并且桶的元素大于 0 同时定位的位置元素还不为空 那就顺藤摸瓜
- if ((tab = table) != null && (n = tab.length)> 0 &&
- (first = tab[(n - 1) & hash]) != null) {
- // 第一个元素是不是我们要找的啊? 判断一下, 是就返回
- if (first.hash == hash && // always check first node
- ((k = first.key) == key || (key != null && key.equals(k))))
- return first;
- if ((e = first.next) != null) {
- // 第一个元素不是我们要找的, 而且后面还接着元素 判断一下是不是树
- if (first instanceof TreeNode)
- // 是树 按照树的获取节点方法去获取
- return ((TreeNode<K,V>)first).getTreeNode(hash, key);
- // 到这说明是链表了 那就按照链表的方式去循环
- do {
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- return e;
- } while ((e = e.next) != null);
- }
- }
- return null;
- }
7, 最后插播一下 HashMap 中的属性
- // 初始容量 1 向左移动 4 位为 16
- static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
- // 最大容量 1 向左移 30 位
- static final int MAXIMUM_CAPACITY = 1 << 30;
- // 加载因子 也就是桶大小使用要是超过 0.75 那么就要考虑扩容了
- static final float DEFAULT_LOAD_FACTOR = 0.75f;
- // 链表太长 要变树的阀值
- static final int TREEIFY_THRESHOLD = 8;
- // 树变成链表的阀值
- static final int UNTREEIFY_THRESHOLD = 6;
- // TREEIFY_THRESHOLD 达到 8 也不一定树化, 还要容量达到 64
- static final int MIN_TREEIFY_CAPACITY = 64;
下一期我们对今天讲的 put,get 方法内涉及到的重要的方法进行讲解. 拜了个拜!
来源: https://www.cnblogs.com/DoubleP/p/11367435.html