关于Map的一些问题

爱被打了一巴掌 2022-11-29 13:18 147阅读 0赞

## 1 Map数据结构类问题 ##

### 1.1 HashMap底层数据结构 ###

HashMap底层是数组+链表+红黑树的数据结构，数组的主要作用是方便快速查找，时间复杂度是O(1)，默认大小是16，当数组容量不够时，扩容为原来的2倍。数组的下标索引是通过key的hashcode计算出来的，数组元素叫做Node，当多个key的hashcode一致，但是key值不同时，单个Node就会转化成链表，链表的查询复杂度是O(n)，当链表的长度大于等于8并且数组的大小超过64时，链表就会转化成红黑树，红黑树的查询复杂度是O(log(n))，所以其最坏的查询次数就相当于红黑树的最大深度。

### 1.2 HashMap、TreeMap、LinkedHashMap三者有啥相同点，有啥不同点？ ###

相同点：

*  三者在特定的情况下都会使用红黑树；
 *  底层的hash算法相同；
 *  在迭代的过程中，如果Map的数据结构发生改动，都会报ConcurrentModificationException错误；

不同点：

*  HashMap数据结构以数组为主，查询非常快，TreeMap数据结构以红黑树为主，利用了红黑树左小右大的特点，可以实现key的排序，LinkedHashMap在HashMap的基础上增加了链表的结构，实现了插入顺序访问和最少访问删除两种策略；
 *  由于三种Map底层数据结构的差别，导致了三者的使用场景的不同，TreeMap适合需要根据key进行排序的场景，LinkedHashMap适合按照插入顺序访问或者需要删除最少访问元素的场景，其他场景使用HashMap即可；

### 1.3 说一下Map的hash算法? ###

static final int hash(Object key) { 
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    key 在数组中的位置公式：tab[(n - 1) & hash]

首先计算出key的hashcode，然后计算h ^ (h >>> 16)，这么做会让计算出来的hash值比较分散。一般来说，索引下标位置可以用hashcode % 数组大小来求得，这样做可以保证计算出来的索引下标均匀的分布在数组的各个索引位置上，但是取模操作是比较慢的，数学上有个公式，当 b 是 2 的幂次方时，a % b = a &（b-1），所以此处索引位置的计算公式我们可以更换为： (n-1) & hash。

*  为什么不用key % 数组大小，而是用key的hashcode % 数组大小？如果key是数字，直接用key % 数组大小是没问题的，但是key还有可能是字符串或者对象，这俩是不能求模的，所以需要先计算出hashcode。
 *  计算hashcode时候，为什么要右移16位？h ^ (h >>> 16)是为了计算出的hashcode更加分数，所以选择先将h无符号右移16位，然后再和h异或，就能达到h的高16位和低16位都能参与计算，减少了碰撞的可能性。
 *  为什么把取模操作换成了&操作？key.hashcode值还不是数组的索引下标，为了随机的计算出索引的下标位置，我们还会用hashcode % 数组大小得到数组的索引下标，这样计算出的索引下标比较均匀分布。但是取模操作计算的慢，而处理器对&操作比较擅长，而且当 b 是 2 的幂次方时，a % b = a &（b-1），所以使用&操作可以提高处理速度。
 *  为了提倡数组大小是2的幂次方？因为只有大小是2的幂次方的时候，才能使hash 值 % n(数组大小) == (n-1) & hash公式成立

### 1.4 为了解决hash冲突，有哪些办法？ ###

*  好的hash算法
 *  自动扩容，减少hash冲突
 *  hash冲突采用链表或者红黑树解决

## 2. HashMap源码细节 ##

### 2.1 HashMap是如何扩容的？ ###

当put时，如果数组为空，则进行初始化扩容，默认扩容大小为16；当put成功后，发现现有数组大小大于扩容的门阀值时，进行扩容，扩容为老数组大小的2倍。扩容的门阀是threshold，每次扩容时threshold都会被重新计算，门阀值等于数组的大小\*影响因子（0.75）。新数组初始化之后，需要将老数组的值拷贝到新数组。

### 2.2 hash冲突时怎么办？ ###

hash冲突指的是key值的hashcode计算相同，但是key值不同的情况。如果桶中元素原本只有一个或已经是链表了，新增元素直接追加到链表尾部；如果桶中元素已经是链表，并且链表个数大于等于8，此时有两种情况：

1.  如果此时数组大小小于64，数组再次扩容，链表不会转化成红黑树；
2.  如果数组大小大于64，链表就会转化成红黑树；

不仅仅判断链表个数大于等于8，还判断了数组大小，数组容量小于64没有立即转化的原因是因为红黑树占用的空间比链表大得多，转化也耗时，所以数组容量小的情况下冲突严重，会先尝试扩容，看看能否通过扩容来解决冲突的问题。

### 2.3 为什么链表个数大于等于8时，链表要转化成红黑树？ ###

当链表个数太多了，遍历比较耗时，转化成红黑树，可以使遍历的时间复杂度降低，但是转化成红黑树，有空间和转化耗时的成本，通过泊松公式计算，链表个数出现到8的可能性不到千万分之一，所以正常情况下，链表都不会转化成红黑树，这样设计的目的是为了防止非正常情况下，比如hash算法出了问题时，导致链表个数大于等于8时，仍然能快速遍历。当红黑树节点的个数小于等于6时，红黑树会自动转化成链表。

### 2.4 HashMap在put时，如果数组中已经有了这个key，我不想把value覆盖怎么办？取值时，如果得到的value是空时，想返回默认值怎么办？ ###

如果数组有了key，但不想覆盖value，可以选择putIfAbsent方法，这个方法有个内置变量onlyIfAbsent，设置为true，就不会覆盖，平时使用的put方法，默认为false，是允许覆盖的。取值时，如果为空，想返回默认值，就可以使用getOrDefault 方法，比如map.getOrDefault(“2”,“0”)，如果2不存在，就返回0。

### 3 其他Map问题 ###

### 3.1 Java Bean作为Map的key时，有无需要注意的点？ ###

*  HashMap的话，一定要重写equals和hashCode方法，在get和put的时候，需要equals方法进行相等的判断；
 *  TreeHash的话，需要实现Comparable接口，因为TreeMap会使用Comparable接口判断key的大小；
 *  LinkedHashMap和HashMap一样；

### 3.2 LinkedHashMap 中的 LRU 是什么意思，是如何实现的。 ###