请选择行业
请选择职位
请选择省份
请选择城市

不吹牛,吃下我这篇,面试第一关算是过了(2)

时间: 2022-02-24 10:25   作者: liqianqian1116   点击次数: 
 
  为什么 JDK 1.8 要对 HashMap 做红黑树这个改动?
  主要是避免 hash 冲突导致链表的长度过长,这样 get 的时候时间复杂度严格来说就不是 O(1) 了,因为可能需要遍历链表来查找命中的 Entry。
  为什么定义链表长度为 8 且数组大小大于等于 64 才转红黑树?不要链表直接用红黑树不就得了吗?
  因为红黑树节点的大小是普通节点大小的两倍,所以为了节省内存空间不会直接只用红黑树,只有当节点到达一定数量才会转成红黑树,这里定义的是 8。
  为什么是 8 呢?这个其实 HashMap 注释上也有说的,和泊松分布有关系,这个大学应该都学过。
  简单翻译下就是在默认阈值是 0.75 的情况下,冲突节点长度为 8 的概率为 0.00000006,也就概率比较小(毕竟红黑树耗内存,且链表长度短点时遍历的还是很快的)。
  这就是基于时间和空间的平衡了,红黑树占用内存大,所以节点少就不用红黑树,如果万一真的冲突很多,就用红黑树,选个参数为 8 的大小,就是为了平衡时间和空间的问题。
  为什么节点少于 6 要从红黑树转成链表?
  也是为了平衡时间和空间,节点太少链表遍历也很快,没必要成红黑树,变成链表节约内存。
  为什么定了 6 而不是小于等于 8 就变?
  是因为要留个缓冲余地,避免反复横跳。举个例子,一个节点反复添加,从 8 变成 9 ,链表变红黑树,又删了,从 9 变成 8,又从红黑树变链表,再添加,又从链表变红黑树?
  所以余一点 ,毕竟树化和反树化都是有开销的。
  那 JDK 1.8 对 HashMap 除了红黑树这个改动,还有哪些改动?
  · hash 函数的优化
  · 扩容 rehash 的优化
  · 头插法和尾插法
  · 插入与扩容时机的变更
  hash 函数的优化
  1.7是这样实现的:
  static int hash(int h) {
      h ^= (h >>> 20) ^ (h >>> 12);
      return h ^ (h >>> 7) ^ (h >>> 4);
  }

  而 1.8 是这样实现的:
      static final int hash(Object key) {
          int h;
          return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
      }

  具体而言就是 1.7 的操作太多了,经历了四次异或,所以 1.8 优化了下,它将 key 的哈希码的高16位和低16位进行了异或,得到的 hash 值同时拥有了高位和低位的特性,这样做得出的码比较均匀,不容易冲突。
  这也是 JDK 开发者根据速度、实用性、哈希质量所做的权衡来做的实现:
  扩容 rehash 的优化
  按照我们的思维,正常扩容肯定是先申请一个更大的数组,然后将原数组里面的每一个元素重新 hash 判断在新数组的位置,然后一个一个搬迁过去。
  在 1.7 的时候就是这样实现的,然而 1.8 在这里做了优化,关键点就在于数组的长度是 2 的次方,且扩容为 2 倍。
  因为数组的长度是 2 的 n 次方,所以假设以前的数组长度(16)二进制表示是 01000,那么新数组的长度(32)二进制表示是 10000,这个应该很好理解吧?
  它们之间的差别就在于高位多了一个 1,而我们通过 key 的 hash 值定位其在数组位置所采用的方法是 (数组长度-1) & hash。我们还是拿 16 和 32 长度来举例:
  16-1=15,二进制为 00111
  32-1=31,二进制为 01111
  所以重点就在 key 的 hash 值的从左往右数第四位是否是 1,如果是 1 说明需要搬迁到新位置,且新位置的下标就是原下标+16(原数组大小),如果是 0 说明吃不到新数组长度的高位,那就还是在原位置,不需要迁移。
  所以,我们刚好拿老数组的长度(01000)来判断高位是否是 1,这里只有两种情况,要么是 1 要么是 0 。
  从上面的源码可以看到,链表的数据是一次性计算完,然后一堆搬运的,因为扩容时候,节点的下标变化只会是原位置,或者原位置+老数组长度,不会有第三种选择。
  上面的位操作,包括为什么是原下标+老数组长度等,如果你不理解的话,可以举几个数带进去算一算,就能理解了。
  总结一下,1.8 的扩容不需要每个节点重写 hash 算下标,而是通过和老数组长度的**&**计算是否为 0 ,来判断新下标的位置。
  额外再补充一个问题:为什么 HashMap 的长度一定要是 2 的 n 次幂?
  原因就在于数组下标的计算,由于下标的计算公式用的是 i = (n - 1) & hash,即位运算,一般我们能想到的是 %(取余)计算,但相比于位运算而言,效率比较低,所以推荐用位运算,而要满足上面这个公式,n 的大小就必须是 2 的 n 次幂。
  即:当 b 等于 2 的 n 次幂时,a % b 操作等于 a & ( b - 1 )
  头插法和尾插法
  1.7是头插法,上面的图已经展示了。
  头插法的好处就是插入的时候不需要遍历链表,直接替换成头结点,但是缺点是扩容的时候会逆序,而逆序在多线程操作下可能会出现环,然后就死循环了。
  然后 1.8 是尾插法,每次都从尾部插入的话,扩容后链表的顺序还是和之前一致,所以不可能出现多线程扩容成环的情况。
  其实我在网上找了找,很多文章说尾插法的优化就是避免多线程操作成环的问题,我表示怀疑。因为 HashMap 本就不是线程安全的,我要还优化你多线程的情况?我觉得开发者应该不会做这样的优化。
  那为什么要变成尾插法呢?我也没找到官方解答,如果有谁知道可以教我一下。
  那再延伸一下,改成尾插法之后 HashMap 就不会死循环了吗?

打印本页 | 加入收藏

上一篇:测试开发和纯软件开发哪个更好?    

关闭  
主要城市: 北京 上海 杭州 广州 南京 武汉 长沙
全部城市: