【面试系列】Map集合
小茵：今天来讲讲Map吧，你对Map了解多少？
小奥：Map在Java里边是一个接口，常见的实现类有HashMap、LinkedHashMap、TreeMap和ConcurrentHashMap
小奥：在Java里边，哈希表的结构是数组+链表的方式。
小奥：HashMap底层数据结构是数组+链表/红黑树
小奥：LinkedHashMap底层数据结构是数组+链表/红黑树+双向链表
小奥：TreeMap底层数据结构是红黑树
小奥：而ConcurrentHashMap底层数据结构也是数组+链表/红黑树
image.png
小茵：我们先以HashMap开始吧，你能讲讲当你new一个HashMap的时候，会发生什么吗？
小奥：HashMap有几个构造方法，但最主要的就是指定初始值大小和负载因子的大小。
小奥：如果我们不指定，默认HashMap的大小为16，负载因子的大小为0.75
小奥：HashMap的大小只能是2次幂的，假设你传一个10进去，实际上最终HashMap的大小是16，你传一个7进去，HashMap最终的大小是8，具体的实现在tableSizeFor可以看到。
小奥：我们把元素放进HashMap的时候，需要算出这个元素所在的位置（hash）。
小奥：在HashMap里用的是位运算来代替取模，能够更加高效地算出该元素所在的位置。
小奥：为什么HashMap的大小只能是2次幂，因为只有大小为2次幂时，才能合理用位运算替代取模。
image.png
小奥：而负载因子的大小决定着哈希表的扩容和哈希冲突。
小奥：比如现在我默认的HashMap大小为16，负载因子为0.75，这意味着数组最多只能放12个元素，一旦超过12个元素，则哈希表需要扩容。
小奥：怎么算出是12呢？很简单，就是16*0.75。每次put元素进去的时候，都会检查HashMap的大小有没有超过这个阈值，如果有，则需要扩容。
image.png
小奥：鉴于上面的说法（HashMap的大小只能是2次幂），所以扩容的时候时候默认是扩原来的2倍
小奥：扩容这个操作肯定是耗时的，那能不能把负载因子调高一点，比如我要调至为1，那我的HashMap就等到16个元素的时候才扩容呢。
小奥：是可以的，但是不推荐。负载因子调高了，这意味着哈希冲突的概率会增高，哈希冲突概率增高，同样会耗时（因为查找的速度变慢了）
小茵：那我想问下，在put元素的时候，传递的Key是怎么算哈希值的？
小奥：实现就在hash方法上，可以发现的是，它是先算出正常的哈希值，然后与高16位做异或运算，产生最终的哈希值。
小奥：这样做的好处可以增加了随机性，减少了碰撞冲突的可能性。
image.png
image.png
小茵：了解，你简单再说下put和get方法的实现吧
小奥：在put的时候，首先对key做hash运算，计算出该key所在的index。
小奥：如果没碰撞，直接放到数组中，如果碰撞了，需要判断目前数据结构是链表还是红黑树，根据不同的情况来进行插入。
小奥：假设key是相同的，则替换到原来的值。最后判断哈希表是否满了(当前哈希表大小*负载因子），如果满了，则扩容
小奥：在get的时候，还是对key做hash运算，计算出该key所在的index，然后判断是否有hash冲突
小奥：假设没有冲突直接返回，假设有冲突则判断当前数据结构是链表还是红黑树，分别从不同的数据结构中取出。
image.png
小茵：那在HashMap中是怎么判断一个元素是否相同的呢？
小奥：首先会比较hash值，随后会用==运算符和equals()来判断该元素是否相同。
小奥：说白了就是：如果只有hash值相同，那说明该元素哈希冲突了，如果hash值和equals() || == 都相同，那说明该元素是同一个。
image.png
小茵：你说HashMap的数据结构是数组+链表/红黑树，那什么情况拿下才会用到红黑树呢？
小奥：当数组的大小大于64且链表的大小大于8的时候才会将链表改为红黑树，当红黑树大小为6时，会退化为链表。
小奥：这里转红黑树退化为链表的操作主要出于查询和插入时对性能的考量。
小奥：链表查询时间复杂度O(N)，插入时间复杂度O(1)，红黑树查询和插入时间复杂度O(logN)
image.png
小茵：你在日常开始中LinkedHashMap用的多吗？
小奥：其实在日常开发中LinkedHashMap用得不多。
小奥：在前面也提到了，LinkedHashMap底层结构是数组+链表+双向链表，实际上它继承了HashMap，在HashMap的基础上维护了一个双向链表。
小奥：有了这个双向链表，我们的插入可以是有序的，这里的有序不是指大小有序，而是插入有序。
小奥：LinkedHashMap在遍历的时候实际用的是双向链表来遍历的，所以LinkedHashMap的大小不会影响到遍历的性能
小茵：那TreeMap呢？
小奥：TreeMap在现实开发中用得也不多，TreeMap的底层数据结构是红黑树
小奥：TreeMap的key不能为null（如果为null，那还怎么排序呢），TreeMap有序是通过Comparator来进行比较的，如果comparator为null，那么就使用自然顺序
image.png
小茵：再来讲讲线程安全的Map吧？HashMap是线程安全的吗？
小奥：HashMap不是线程安全的，在多线程环境下，HashMap有可能会有数据丢失和获取不了最新数据的问题，比如说：线程Aput进去了，线程Bget不出来。
小奥：我们想要线程安全，可以使用ConcurrentHashMap
小奥：ConcurrentHashMap是线程安全的Map实现类，它在juc包下的。
小奥：线程安全的Map实现类除了ConcurrentHashMap还有一个叫做Hashtable。
小奥：当然了，也可以使用Collections来包装出一个线程安全的Map。
小奥：但无论是Hashtable还是Collections包装出来的都比较低效（因为是直接在外层套synchronize），所以我们一般有线程安全问题考量的，都使用ConcurrentHashMap
image.png
小奥：ConcurrentHashMap的底层数据结构是数组+链表/红黑树，它能支持高并发的访问和更新，是线程安全的。
小奥：ConcurrentHashMap通过在部分加锁和利用CAS算法来实现同步，在get的时候没有加锁，Node都用了volatile给修饰。
小奥：在扩容时，会给每个线程分配对应的区间，并且为了防止putVal导致数据不一致，会给线程的所负责的区间加锁
小茵：你能给我讲讲JDK 7 和JDK8中HashMap和ConcurrentHashMap的区别吗？
小奥：不能，我不会
小奥：我在学习的时候也看过JDK7的HashMap和ConcurrentHashMap，其实还是有很多不一样的地方
候选者 比如JDK 7 的HashMap在扩容时是头插法，在JDK8就变成了尾插法，在JDK7 的HashMap还没有引入红黑树….
小奥：ConcurrentHashMap 在JDK7 还是使用分段锁的方式来实现，而JDK 8 就又不一样了。但JDK 7细节我大多数都忘了。
小奥：我就没用过JDK 7的API，我想着现在最低应该也是用JDK8了吧？所以我就没去仔细看了。
小茵：嗯...
