关于HashMap中的二次Hash
问题引入 :
在学习HashMap的底层源码的时候 ，发现 :
在putVal的时候会调用一个hash()对key进行hash操作 :
先通过key.hashCode()获得了哈希值h ，这是第一次hash操作 ;
再进行 :
h^h>>>16也就是二次Hash操作 ;
那么为什么要进行二次hash操作呢 ?
二次hash的效果代码演示 :
package com.it.Map;import java.util.* ;public class DistributionAffectedByCapacity {public static int[] randomArray(int n) {Random random = new Random();int[] arr = new int[n];for (int i = 0; i < n; i++)arr[i] = random.nextInt(100000000) ;return arr;}// 要么取余16==0 , 1// 构造一千个随机数 ，每个随机数要求取余16==0或者==1public static int[] lowSameArray(int n) {Random random = new Random();int[] arr = new int[n];for (int i = 0; i < n; i++){int x = random.nextInt(100000000) ;if(x%16==0||x%16==2) arr[i] = x;else {if (x % 16 >= 8) x -= (x % 16);else x = x - (x % 16) + 2;arr[i] = x ;}}return arr;}public static void printDistribution(int[] arr, int[] sizes) {for (int size : sizes) {Map<Integer, Integer> map = new HashMap<>();for (int i : arr) {// int p = i ;int p = i^i>>>16 ;// 增加随机性// 假设不进行二次hash ，原hash的高位根本不会影响得到的下标,在size比较小的情况之下 ，只会受到低位的影响 ;// HashMap通过将哈希码的高16位与低16位进行异或运算，得到一个新的哈希码，这样就可以让高位也参与到运算，这个函数也被称作「扰动函数」。map.put(p%size, map.getOrDefault(p%size, 0) + 1);}for(int i=0;i<size;i++){if(map.get(i)==null) System.out.print(i+" : "+ 0 + " ,");else System.out.print(i+" : "+ map.get(i) + " ,");}}}public static void main(String[] args) {int[] a = randomArray(1000);// 足够随机int[] b = lowSameArray(1000);// System.out.println(Arrays.toString(a));System.out.println(Arrays.toString(b));int[] sizes = {16} ;printDistribution(b, sizes);}
}
1 . 先用随机数生成一个size=1000的数组 ， 模拟放入大小为16的hash数组中 :
能看到数据还是比较分散的 ;
2 . 先用随机数生成一个size=1000的数组(但是处理是数组中只存在模16==0/1的数据) ， 模拟放入大小为16的hash数组中 :
可以发现数据及其分布不均 ;
3 . 先用随机数生成一个size=1000的数组(但是处理是数组中只存在模16==0/1的数据) ， 模拟放入大小为16的hash数组中 , 这次模拟进行二次hash操作 :
可以看到数据较上次是随机的
结论 :
-
假设不进行二次hash ，原hash的高位根本不会影响得到的下标,在size比较小的情况之下 ，只会受到低位的影响 ， 就算散列值分布得再松散 ，只取低位的几位的情况下(假设4位) ，很可能出现重复 ,发生hash碰撞的概率也会增大 ;
-
HashMap通过将哈希码的高16位与低16位进行异或运算，得到一个新的哈希码，这样就可以让高位也参与到运算，这个函数也被称作「扰动函数」。