关于java:求求大厂给个OfferMap面试题

3次阅读

共计 3173 个字符，预计需要花费 8 分钟才能阅读完成。

微信搜【Java3y】关注这个有幻想的男人，点赞关注是对我最大的反对！

文本已收录至我的 GitHub：https://github.com/ZhongFuCheng3y/3y，有 300 多篇原创文章，最近在 连载面试 系列！

我，三歪，最近开始写面试系列。我给这个面试系列取了一个名字，叫做《求求大厂给个 Offer》

后面曾经写了两篇了，喜爱看的同学能够微信搜「Java3y」回复「面试」即可观看。

所以这篇文章叫做《求求大厂给个 Offer：Map 面试题》

接下来就开始吧。

三歪：“我叫三歪，目前保护一个公众号叫做 Java3y，这几年写了 300+ 原创技术文章，近 1000 页的原创电子书和多个知识点的思维导图。我的愿景是：只有关注我并三连的同学都能够拿到大厂 offer。我的 ….”

三歪：“Map 在 Java 里边是一个接口，常见的实现类有 HashMap、LinkedHashMap、TreeMap 和 ConcurrentHashMap”

三歪：“首先要明确的是：在 Java 里边，哈希表的构造是 数组 + 链表 的形式。HashMap 底层数据机构是 数组 + 链表 / 红黑树 、LinkedHashMap 底层数据结构是 数组 + 链表 + 双向链表 、TreeMap 底层数据结构是红黑树，而 ConcurrentHashMap 底层数据结构也是 数组 + 链表 / 红黑树”

面试官：“咱们先以 HashMap 开始吧，你能讲讲当你 new 一个 HashMap 的时候，会产生什么吗？”

三歪：“HashMap 有几个构造方法，但最次要的就是指定初始值大小和负载因子的大小。如果咱们不指定，默认 HashMap 的大小为16，负载因子的大小为0.75”

三歪：“HashMap 的大小只能是 2 次幂 的，假如你传一个 10 进去，实际上最终 HashMap 的大小是 16，你传一个 7 进去，HashMap 最终的大小是 8，具体的实现在 tableSizeFor 能够看到。咱们把元素放进 HashMap 的时候，须要算出这个元素所在的地位（hash）。在 HashMap 里用的是 位运算 来代替取模，可能更加高效地算出该元素所在的地位。为什么 HashMap 的大小只能是 2 次幂，因为只有大小为 2 次幂时，能力正当用位运算代替取模。”

三歪：“而负载因子的大小决定着哈希表的扩容和哈希抵触 。比方当初我默认的 HashMap 大小为 16，负载因子为 0.75，这意味着数组最多只能放 12 个元素，一旦超过 12 个元素，则哈希表须要扩容。怎么算出是 12 呢？很简略，就是16*0.75。每次put 元素进去的时候，都会查看 HashMap 的大小有没有超过这个阈值，如果有，则须要扩容。”

三歪：“鉴于下面的说法（HashMap 的大小只能是 2 次幂），所以扩容的时候时候默认是扩原来的 2 倍”

三歪：“显然扩容这个操作必定是耗时的，那我能不能把 负载因子调高 一点，比方我要调至为 1，那我的 HashMap 就等到 16 个元素的时候才扩容呢。显然是能够的，然而不举荐。负载因子调高了，这意味着 哈希抵触的概率 会增高，哈希抵触概率增高，同样会耗时（因为查找的速度变慢了）”

三歪：“实现就在 hash 办法上，能够发现的是，它是先算出失常的哈希值，而后与 高 16 位 做异或运算，产生最终的哈希值。这样做的益处能够 减少了随机性，缩小了碰撞抵触的可能性。”

三歪：”在 put 的时候，首先对 key 做 hash 运算，计算出该 key 所在的 index。如果没碰撞，间接放到数组中，如果碰撞了，须要判断目前数据结构是链表还是红黑树，依据不同的状况来进行插入。假如 key 是雷同的，则替换到原来的值。最初判断哈希表是否满了 (以后哈希表大小* 负载因子），如果满了，则扩容“

三歪：”在 get 的时候，还是对 key 做 hash 运算，计算出该 key 所在的 index，而后判断是否有 hash 抵触，假如没有间接返回，假如有则判断以后数据结构是链表还是红黑树，别离从不同的数据结构中取出。“

三歪：”首先会比拟 hash 值，随后会用 == 运算符和 equals() 来判断该元素是否雷同。说白了就是：如果只有 hash 值雷同，那阐明该元素哈希抵触了，如果 hash 值和equals() || == 都雷同，那阐明该元素是同一个。“

三歪：”当数组的大小大于 64 且链表的大小大于 8 的时候才会将链表改为红黑树，当红黑树大小为 6 时，会进化为链表。这里转红黑树进化为链表的操作次要出于 查问和插入时对性能的考量。链表查问工夫复杂度 O(N)，插入工夫复杂度 O(1)，红黑树查问和插入工夫复杂度 O(logN)“

三歪：“其实在日常开发中 LinkedHashMap 用得不多。在后面也提到了，LinkedHashMap 底层构造是 数组 + 链表 + 双向链表 ”，实际上它继承了 HashMap，在 HashMap 的根底上保护了一个 双向链表 。有了这个双向链表，咱们的插入能够是“有序”的，这里的有序不是指大小有序，而是 插入有序。

三歪：“LinkedHashMap 在遍历的时候理论用的是双向链表来遍历的，所以 LinkedHashMap 的大小不会影响到遍历的性能”

三歪：“TreeMap 在事实开发中用得也不多，TreeMap 的底层数据结构是红黑树，TreeMap 的 key 不能为 null（如果为 null，那还怎么排序呢），TreeMap 有序是通过 Comparator 来进行比拟的，如果 comparator 为 null，那么就应用天然程序”

三歪：“HashMap 不是线程平安的，在多线程环境下，HashMap 有可能会有数据失落和获取不了最新数据的问题，比如说：线程 A put进去了，线程 B get不进去。咱们想要线程平安，能够应用 ConcurrentHashMap”

三歪：“ConcurrentHashMap 是线程平安的 Map 实现类，它在 juc 包下的。线程平安的 Map 实现类除了 ConcurrentHashMap 还有一个叫做 Hashtable。当然了，也能够应用 Collections 来包装出一个线程平安的 Map。但无论是 Hashtable 还是 Collections 包装进去的都比拟低效（因为是间接在外层套 synchronize），所以咱们个别有线程平安问题考量的，都应用 ConcurrentHashMap”

三歪：“ConcurrentHashMap 的底层数据结构是 数组 + 链表 / 红黑树 ，它能反对高并发的拜访和更新，是线程平安的。ConcurrentHashMap 通过在 局部加锁 和利用 CAS 算法 来实现同步，在 get 的时候没有加锁，Node 都用了 volatile 给润饰。在扩容时，会给每个线程调配对应的区间，并且为了避免putVal 导致数据不统一，会给线程的所负责的区间加锁”

三歪：“不能，我不会”

三歪：“我在学习的时候也看过 JDK7 的 HashMap 和 ConcurrentHashMap，其实还是有很多不一样的中央，比方 JDK 7 的 HashMap 在扩容时是头插法，在 JDK8 就变成了尾插法，在 JDK7 的 HashMap 还没有引入红黑树 ….ConcurrentHashMap 在 JDK7 还是应用分段锁的形式来实现，而 JDK 8 就又不一样了。但 JDK 7 细节我大多数都忘了。”

三歪：“我就没用过 JDK 7 的 API，我想着当初最低应该也是用 JDK8 了吧？所以我就没去认真看了。要不我给你讲讲多线程相干的常识呗？”

三歪：“哦”

针对这次的面试可能你想理解更多 Map 的细节，比如说 Map 基础知识 /HashMap/LinkedHashMap/TreeMap/ConcurrentHashMap 的源码，能够在微信搜「Java3y」回复「Map」即可获取我之前写的原创文章。