网站建设与维护试题a卷,仿珠宝首饰网站开发,唐山建设信息网站,wordpress 轮播图代码今天我们就面试会问到关于HashMap的问题进行一个汇总#xff0c;以及对这些问题进行解答。1、HashMap的数据结构是什么#xff1f;2、为啥是线程不安全的#xff1f;3、Hash算法是怎样实现的#xff1f;4、HashMap是如何处理Hash碰撞的#xff1f;5、增加元素的方法是怎么…今天我们就面试会问到关于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^00 、0^11.为右移动符号左侧补零。图中h16就是将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) {NodeK,V[] tab; NodeK,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 {// 运行到这说明定位的位置已经有元素了NodeK,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 ((TreeNodeK,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中的// 也就是说这里虽然binCount7就可以树化其实真正的树化// 条件是链表中元素个数大于等于8if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(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 keyV oldValue e.value;// 判断是否需要旧值换新值默认情况下是允许更换的if (!onlyIfAbsent || oldValue null)e.value value;// 这个方法点进去就是个空方法主要是为了给继承HashMap的// LinkedHashMap服务的afterNodeAccess(e);return oldValue;}}// 修改次数1modCount;// 看下达到扩容的阀值没if (size threshold)// 扩容 在本方法的前面需要初始化的时候也出现过resize();// 这个方法同样也是为LinkedHashMap服务的afterNodeInsertion(evict);// 没找到元素 就返回空return null;}6、获取元素的方法时怎么实现的 使用hash值去找桶的位置 final NodeK,V getNode(int hash, Object key) {NodeK,V[] tab; NodeK,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 ((TreeNodeK,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位为16static 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也不一定树化还要容量达到64static final int MIN_TREEIFY_CAPACITY 64;下一期我们对今天讲的put、get方法内涉及到的重要的方法进行讲解。拜了个拜大量面试经验以及学习资料书籍请关注微信公众号AVAJ回复offer进行获取365篇大厂java面经 你想要的我这里都有
