甘肃龙网

  1. 首页 > 生活 > >

2、HashMap中的常量( 四 )

生活百科链表


为什么不直接调用key.()而还需让高16位与低16位执行异或操作？
答：为了增加随机性 。上面式子其实是将高16位与低16位进行了一个异或操作，因为根据哈希值确定数组位置的方法时hash&(n-1),n-1的大小不会很大，也就是说只有低位的hash值才影响数组的位置，而hash值原本有32位，高位的哈希特征全部都消失了，出现哈希冲突的概率就增加了，因此使用异或操作使得低位和高位均能够影响数组的位置 。所以，异或运算之后，可以让结果的随机性更大，而随机性大了之后，哈希碰撞的概率当然就更小了 。
为什么一定是异或操作？
能够确保结果足够分散：

2、HashMap中的常量

文章插图
7、()扩容机制
在添加一个新的元素后，会判断当前数组的容量是否超过阈值，如果容量>=阈值则会进行扩容 。同样当开始数组为空时也同样会进行扩容 。
final Node[] resize() {//旧数组Node[] oldTab = table;//旧数组的容量int oldCap = (oldTab == null) ? 0 : oldTab.length;//旧数组的扩容阈值，注意看，这里取的是当前对象的 threshold 值，下边的第2种情况会用到 。int oldThr = threshold;//初始化新数组的容量和阈值，分三种情况讨论 。int newCap, newThr = 0;//1.当旧数组的容量大于0时，说明在这之前肯定调用过 resize扩容过一次，才会导致旧容量不为0 。//为什么这样说呢，之前我在 tableSizeFor 卖了个关子，需要注意的是，它返回的值是赋给了 threshold 而不是 capacity 。//我们在这之前，压根就没有在任何地方看到过，它给 capacity 赋初始值 。if (oldCap > 0) {//容量达到了最大值if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//新数组的容量和阈值都扩大原来的2倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}//2.到这里，说明 oldCap <= 0，并且 oldThr(threshold) > 0，这就是 map 初始化的时候，第一次调用 resize的情况//而 oldThr的值等于 threshold，此时的 threshold 是通过 tableSizeFor 方法得到的一个2的n次幂的值(我们以16为例) 。//因此，需要把 oldThr 的值，也就是 threshold ，赋值给新数组的容量 newCap，以保证数组的容量是2的n次幂 。//所以我们可以得出结论，当map第一次 put 元素的时候，就会走到这个分支，把数组的容量设置为正确的值（2的n次幂)//但是，此时 threshold 的值也是2的n次幂，这不对啊，它应该是数组的容量乘以加载因子才对 。别着急，这个会在③处理 。else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;//3.到这里，说明 oldCap 和 oldThr 都是小于等于0的 。也说明我们的map是通过默认无参构造来创建的，//于是，数组的容量和阈值都取默认值就可以了，即 16 和 12 。else {// zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//③ 这里就是处理第2种情况，因为只有这种情况 newThr 才为0，//因此计算 newThr（用 newCap即16 乘以加载因子 0.75，得到 12） ，并把它赋值给 thresholdif (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}//赋予 threshold 正确的值，表示数组下次需要扩容的阈值（此时就把原来的 16 修正为了 12） 。threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})//我们可以发现，在构造函数时，并没有创建数组，在第一次调用put方法，导致resize的时候，才会把数组创建出来 。这是为了延迟加载，提高效率 。Node[] newTab = (Node


上一篇：数组+链表+红黑树 HashMap底层数据结构

下一篇：window10，JDK、Jre安装及环境配置