前言
微信搜【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有可能会有数据失落和获取不了最新数据的问题，比如说：线程Aput进去了，线程Bget不进去。咱们想要线程平安，能够应用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」即可获取我之前写的原创文章。
涵盖Java后端所有知识点的开源我的项目，已有10K+ star！内含1000+页原创电子书！！！
- GitHub
- Gitee拜访更快
PDF文档的内容均为手打，有任何的不懂都能够间接来问我