HashMap思考题
1. 为什么HashMap的一个拉链长度大于8后就会转成红黑树？ HashMap中存储的元素所存在的集合（桶，bucket）是一个 单链表 ，或者是一颗 红黑树 。当总bucket数（MIN_TREEIFY_CAPACITY）超过64时，长度超过8（TREEIFY_THRESHOLD）的单链表就会被转化程一颗红黑树。 这样做的目的是为了减少query某个元素时的时间复杂度。在单链表中，查询元素具有线性时间复杂度；而在红黑树中，查找某个元素只需要对数时间复杂度。 长度太长的单链表不利于高效查找元素。 2. 为什么用红黑树，不用AVL树？ 红黑树是一种 弱平衡二叉树 ，它确保没有任何一条路径会大于其他路径长度的二倍。AVL树对于高度的限制比红黑树更加严格，其所有节点的左右子树高度差不超过1。 所以： 查询数据时，AVL树比红黑树更快（因为AVL树高度更低）。 添加或删除数据时，红黑树比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位相同的Hashc