【备战面试】每日10道面试题打卡-Day4

本篇总结的是Java集合知识相关的面试题，后续也会更新其他相关内容

---

1、HashMap在JDK1.7和JDK1.8中有哪些不同？

答：先看看两个版本HashMap的Hash函数，如下：

JDK1.7的Hash函数

static final int hash(int h){h ^= (h >>> 20) ^ (h >>>12);return h^(h >>> 7) ^ (h >>> 4);
}

JDK1.8的Hash函数

static final int hash(Onject key){    int h;    return (key == null) ? 0 : (h = key.hashCode())^(h >>> 16);
}

可以看到JDK1.8的函数经过了一次异或一次位运算一共两次扰动，而JDK1.7经过了四次位运算五次异或一共九次扰动。

这里简单解释下JDK1.8的hash函数，两次扰动分别是key.hashCode() 与 key.hashCode() 右移16位进行异或。这样做的目的是，高16位不变，低16位与高16位进行异或操作，进而减少碰撞的发生，高低Bit都参与到Hash的计算。如何不进行扰动处理，因为hash值有32位，直接对数组的长度求余，起作用只是hash值的几个低位。

区别

2、HashMap 的长度为什么是2的幂次方？

答：因为 HashMap 是通过 key 的hash值来确定存储的位置，但Hash值的范围是-2147483648到2147483647，不可能建立一个这么大的数组来覆盖所有hash值。所以在计算完hash值后会对数组的长度进行取余操作，如果数组的长度是2的幂次方， (length - 1)&hash 等同于 hash%length ，可以用(length - 1)&hash 这种位运算来代替%取余的操作进而提高性能。

使用位运算比取余性能高

3、HashMap的扩容操作是怎么实现的？

答：

• 初始值为16，负载因子为0.75，阈值为负载因子*容量；
• resize() 方法是在 hashmap 中的键值对大于阀值时或者初始化时，就调用 resize() 方法进行扩容；
• 每次扩容，容量都是之前的两倍；
• 扩容时有个判断 e.hash & oldCap 是否为零，也就是相当于hash值对数组长度的取余操作，若等于0，则位置不变，若等于1，位置变为原位置加旧容量；

1.HashMap默认加载因子为什么选择0.75？

• 这个主要是考虑空间利用率和查询成本的一个折中。如果加载因子过高，空间利用率提高，但是会使得哈希冲突的概率增加；如果加载因子过低，会频繁扩容，哈希冲突概率降低，但是会使得空间利用率变低。具体为什么是0.75，不是0.74或0.76，这是一个基于数学分析（泊松分布）和行业规定一起得到的一个结论。

2.为什么不刚开始就使用红黑树？

• 因为红黑树的节点所占的空间是普通链表节点的两倍，但查找的时间复杂度低，所以只有当节点特别多时，红黑树的优点才能体现出来。至于为什么是8，是通过数据分析统计出来的一个结果，链表长度到达8的概率是很低的，综合链表和红黑树的性能优缺点考虑将大于8的链表转化为红黑树。
• 链表转化为红黑树除了链表长度大于8，还要HashMap 中的数组长度大于64。也就是如果HashMap 长度小于64，链表长度大于8是不会转化为红黑树的，而是直接扩容。

4、HashMap是怎么解决哈希冲突的？

答：哈希冲突： hashMap 在存储元素时会先计算 key 的hash值来确定存储位置，因为 key 的hash值计算最后有个对数组长度取余的操作，所以即使不同的 key 也可能计算出相同的hash值，这样就引起了hash冲突。 hashMap 的底层结构中的链表/红黑树就是用来解决这个问题的。

HashMap 中的哈希冲突解决方式可以主要从三方面考虑（以JDK1.8为背景）

拉链法

• HasMap 中的数据结构为数组+链表/红黑树，当不同的 key 计算出的hash值相同时，就用链表的形式将Node结点（冲突的 key 及 key 对应的 value ）挂在数组后面。

hash函数

• key 的hash值经过两次扰动， key 的 hashCode 值与 key 的 hashCode 值的右移16位进行异或，然后对数组的长度取余（实际为了提高性能用的是位运算，但目的和取余一样），这样做可以让hashCode 取值出的高位也参与运算，进一步降低hash冲突的概率，使得数据分布更平均。

红黑树

• 在拉链法中，如果hash冲突特别严重，则会导致数组上挂的链表长度过长，性能变差，因此在链表长度大于8时，将链表转化为红黑树，可以提高遍历链表的速度。

5、HashMap 多线程导致死循环问题

答：由于JDK1.7的 hashMap 遇到hash冲突采用的是头插法，多线程会导致HashMap的Entry链表形成环形数据结构在多，线程情况下会存在死循环问题，但JDK1.8已经改成了尾插法，不存在这个问题了。但需要注意的是JDK1.8中的 HashMap 仍然是不安全的，在多线程情况下使用仍然会出现线程安全问题。

6、HashMap、ConcurrentHashMap及Hashtable 的区别

答：如下图：

7、HashMap的put方法的具体流程？

答：如下图：

8、说一下 ArrayList 的优缺点

答：
ArrayList的优点

• ArrayList 底层以数组实现，是一种随机访问模式。ArrayList 实现了 RandomAccess 接口，因此查找的时候非常快。
• ArrayList 在顺序添加一个元素的时候非常方便。

ArrayList 的缺点

• 删除元素的时候，需要做一次元素复制操作。如果要复制的元素很多，那么就会比较耗费性能。
• 插入元素的时候，也需要做一次元素复制操作，缺点同上。

ArrayList 比较适合顺序添加、随机访问的场景。

9、如果使用Object作为HashMap的Key，应该怎么办呢？

答：需要重写hashCode()和equals()方法：

• 重写 hashCode() 方法，因为需要计算hash值确定存储位置；
• 重写 equals() 方法，因为需要保证 key 的唯一性；

10、HashTable的底层实现知道吗？

答：HashTable 的底层数据结构是数组+链表，链表主要是为了解决哈希冲突，并且整个数组都是synchronized 修饰的，所以 HashTable 是线程安全的，但锁的粒度太大，锁的竞争非常激烈，效率很低。