HashMap思考题

 1. 为什么HashMap的一个拉链长度大于8后就会转成红黑树？

HashMap中存储的元素所存在的集合（桶，bucket）是一个单链表，或者是一颗红黑树。当总bucket数（MIN_TREEIFY_CAPACITY）超过64时，长度超过8（TREEIFY_THRESHOLD）的单链表就会被转化程一颗红黑树。

这样做的目的是为了减少query某个元素时的时间复杂度。在单链表中，查询元素具有线性时间复杂度；而在红黑树中，查找某个元素只需要对数时间复杂度。长度太长的单链表不利于高效查找元素。

---

​

2. 为什么用红黑树，不用AVL树？

红黑树是一种弱平衡二叉树，它确保没有任何一条路径会大于其他路径长度的二倍。AVL树对于高度的限制比红黑树更加严格，其所有节点的左右子树高度差不超过1。

所以：

1. 查询数据时，AVL树比红黑树更快（因为AVL树高度更低）。
2. 添加或删除数据时，红黑树比AVL树更快（因为AVL树更严格，所以对节点的旋转操作更频繁）。

HashMap选择红黑树是一种对查询效率和增删效率的折衷。

---

​

3. 为什么生成哈希值要对hashcode进行高低位异或处理？

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

这是生成哈希值的代码。

为啥要把hashcode高16位和低16位做异或操作呢？

原来就是为了减少哈希冲突。

在将某一个Key加入HashMap时，如何确定这个Key该放到那个bucket中呢？正常来讲，应该是先计算这个Key的哈希值，然后对HashMap的容量进行模运算来确定这个Key放到第几个bucket里。比如向一个容量位16个bucket的HashMap加入一个哈希值为17的Key，那么就应该把这个Key放到第17 % 16 = 1个bucket。

实际上HashMap在处理这个操作时并不是做模运算，而是让哈希值和（HashMap容量 - 1）作与运算。

比如HashMap容量为16，16 - 1 = 15的二进制表示是1111。

也就是hashcode的高位都没用了，都被与没了。

只要后4位相同的Hashcode就会产生碰撞。

所以在计算哈希值时将高位引入做一个扰动，可以减少发生哈希冲突的概率。

---

​

4. 为什么要重写Key的hashCode和equals方法？

先说为什么要重写equals方法。Key默认是以Object来进行比较的，值相同而地址不同是不会让equals返回true的。为了保证HashMap中Key的值的唯一性，必须要重写equals方法。

那么为什么还要重写hashCode方法呢？

正是因为我们重写了equals方法，我们才要重写hashCode方法。

下面是文档中关于hashCode方法的约定：

• Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
• If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
• It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.

第二条说，如果两个对象被equals方法判定为相同，那么hashCode方法的值必须也相同。而原生的Object中的equals并不是比较值而是比较地址，而我们的Key是比较值，所以我们最好重写hashCode方法。

在实际使用时，这样做会提高效率。HashMap先比较两个对象的hashCode来确定两个对象是否相等，如果hashCode相等，就不用再调用equals了。

5. 为什么HashMap的查询时间复杂度是O(1)？（下次再写。。）

参考资料

• https://blog.csdn.net/qq_38182963/article/details/78940047
• https://stackoverflow.com/questions/37959941/what-exactly-is-bucket-in-hashmap
• https://stackoverflow.com/questions/47921663/when-and-how-does-hashmap-convert-the-bucket-from-linked-list-to-red-black-trees
• https://docs.oracle.com/javase/7/docs/api/java/lang/Object.html
• https://blog.csdn.net/world6/article/details/52127510