01-备战秋招之Map

一、概述

1. Map 在 Java 里边是一个接口，常见的实现类有 HashMap、LinkedHashMap、TreeMap、ConcurrentHashMap
2. 数据结构
   1. 哈希表的实现： 数组+链表/红黑树
   2. LinkedHashMap 底层：数组+链表+双向链表
   3. TreeMap 底层：红黑树
   4. ConcurrentHashMap底层：数组+链表/红黑树

二、hashMap

1. hashMap 有几个构造方法，但最主要的就是指定初始值及负载因子的大小（默认hashmap的大小为16，负载因子的大小为0.75）

2. hashmap的大小只能是2次幂，举例：传入的值为10，实际上最终的 HashMap 的大小为16；传入一个7进去，hashmap最终的大小是8，具体的实现在 tableSizeFor可以看到

3. 位运算：我们把元素放进HashMap的时候，需要算出这个元素所在的位置（hash)，在HashMap里用的是位运算来代替取模，index = hash值 % 数组长度这样的话 index 的值就永远都在数组长度之内，也就可以作为数组下标了，但缺点是效率低。 所以采用减一与运算index = hash值 & (数组长度 - 1)
   

4. 负载因子的大小决定着哈希表的扩容和哈希冲突。比如默认的hashmap 的大小为 16，负载因子为 0.75，这意味着数组最多只能放 12 个元素（16 * 0.75），一旦超过12 个元素，哈希表就需要扩容。每次 put 元素进去的时候，都会检查 HashMap 的大小有没有超过这个阈值，如果有，则需要扩容（由于HashMap 的大小只能是 2 次幂，所以扩容的时候默认是扩原来的 2 倍）。虽然扩容操作耗时，但也不推荐将负载因子调高（比如调至为 1，那 HashMap 就等到 16 个元素的时候才扩容，但负载因子调高则意味着哈希冲突的概率会增高，会导致查找的速度变慢）

5. put 和 get 方法

   1. put 方法
      1. 首先调用 key 对象的 hashccode() 方法，获取 hashcode，根据 hashcode 计算出 hash值（要求在[0, 数组长度-1]区间），根据 hash 计算出该 key 所在的 index
      2. 如果没有碰撞，直接放到数组中，如果碰撞，需要判断目前数据结构是链表还是红黑树，根据不同的情况进行插入
      3. key 相同，则替换原来的值，最后判断哈希表是否满了（当前哈希表大小 * 负载因子），如果满了，则扩容
   2. get 方法
      1. 同put，根据 key 做 hash 运算，计算出该 key 所在的 index, 然后判断是否有 hash 冲突
      2. 有冲突直接返回，没有冲突则判断当前数据结构是链表还是红黑树，分别从不同的结构中取出。

6. HashMap 中怎么判断一个元素是否相同？

   1. 首先比较 hash 值，随后用 == 或者 equals
   2. 计算hashcode使用的是杂凑算法，可能会让多个对象返回相同的杂凑值。hash值相同，那么

三、LinkedHashMap

1. 底层是数组+链表+双向链表，继承了 HashMap，在HashMap基础上维护了一个双向链表，有了这个双向链表，插入可以是有序的（插入有序，非大小有序）
2. LinkedHashMap 在遍历的时候实际用的是双向链表来遍历的，所以LinkedHashMap的大小不会影响到遍历的性能。

四、TreeMap

1. TreeMap的key不能为null（如果为 null，那还怎么没排序？），TreeMap有序是通过 Comparator 来进行比较的，如果 comparator 为 null，那么就使用自然顺序。

五、线程安全的 Map

1. HashMap 不是线程安全的，在多线程环境下， HashMap可能会有数据丢失和获取不了最新数据的问题，比如说：线程A put 进去了，线程B get 不出来。
2. 若想线程安全，一般使用 ConcurrentHashMap,是线程安全的Map实现类，它在juc包下。支持高并发的访问和更新。ConcurrentHashMap通过在部分加锁和利用CAS算法来实现同步，在get的时候没有加锁，Node用了volatile 来修饰。在扩容时，会给每个线程分配对应的区间，并且为了防止putVal导致数据不一致，会给线程所负责区间加锁
3. 此外，还有 HashTable 实现类。或者使用 Collections 来包装出一个线程安全的Map。但无论是HashTable还是Collections包装出来的都比较低效（因为直接在外层套synchronize）,所以我们一般有线程安全问题的考量，都是用 ConcurrentHashMap。

本文地址：https://blog.csdn.net/weixin_45501561/article/details/114300008