探哈希 - 简书

哈希是什么

数组和向量都可以存储数据，但数据存储的位置是随机的，数据本身和存储位置没有一个必然的联系，当要查找一个指定的数据时，只能按照顺序查找并比较，时间复杂度此时是线性阶O(n)，或者利用一些算法减少到对数阶O(logn)，当数组或向量中的元素很多时查找的效率很低。

最优查找的时间复杂度是常量阶O(1)，不需要顺序遍历也不需要元素之间的对比，一次存取便能够得到所需要的记录，这就需要在数据本身和存储位置之间建立一种特定的对应关系，使得每个数据与一个唯一的位置相对应，查找数据时只需要用数据按照特定的规则算出在集合中的位置即可，这种特定的对应关系我们称为哈希（hash，也叫散列），根据哈希而直接进行访问的数据结构叫哈希表（hash table，也叫散列表）。

哈希构造

平常我们存储数据的时候，数据的数量总是比索引的数目多。比如有十个苹果放到九个抽屉里，无论怎样放，至少有一个抽屉里放的苹果不少于两个，这就是鸽巢原理，所以上面的哈希是存在冲突的（哈希碰撞），且冲突不可避免，不论是多么高明的算法都不可能解决这个问题，但是我们可以减小冲突，这就与hash函数的构造有关，它构造准则也很简单，只有两点：简单和均匀，下面看下hash函数构造的几种方法。

（1）直接定址法

取关键字或关键字的某个线性函数值为哈希地址。即H(key)=key或H(key)=a*key+b（a,b为常数），碰撞概率比较大，不常使用。

（2）相乘取整法

首先用关键字key乘上某个小数A（0<A<1），并抽取出结果的小数部分，然后再用m乘以该小数后取整。

（3）数字分析法

若关键字是以r为基的数（如以10为基的十进制数），并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。依赖特定的格式，使用场景不多。

（4）平方取中法

取关键字平方后的中间几位为哈希地址。（较常使用的一种）

（5）折叠法

将关键字分割成位数相同的几部分，然后取这几部分的叠加和（分为移位叠加和间接叠加）作为哈希地址。适用于关键字位数多，且每一位上数字分布比较均匀。

（6）除留余数法

取关键字被数p除后所得余数为哈希地址，且p为素数，p不大于哈希表大小m。即H(key)=key MOD p, p<= m。此方法最简单也最常用。

（7）随机数法

使用一个随机函数对关键字进行哈希计算，即H(key) = random(key)，适用于关键字长度不等时。

哈希冲突

上面是几个哈希函数构造方法，本着简单和均匀的原则，但是再怎么均匀分布也避免不了碰撞的发生，那当碰撞发生时又该怎么办？下面看下hash冲突解决的几种方法。

（1）开放定址法

当关键字key的哈希地址H(key)出现冲突时就找出一个不冲突的哈希地址。找出方式目前有很多，最常见的是在H(key)位置逐个单元地址往后查找，直到找到给定的关键字，或者找到一个开放地址（即空单元）为止，这种方式我们称之为线性探测。但是线性探测会有数据聚集的问题，所以后来又有了平方探测，平方探测顾名思义就是探测的增量是1²、-1²、2²、-2²…（线性探测是1、2、3、4……），除了平方探测，杜鹃散列和跳房子散列也是对线性探测算法的一种改进，但这两种方法实现比较复杂，解决冲突的计算相对比较耗时，而且需要引入额外的空间，所以使用的场景也比较少，这里不再细说。

（2）再哈希法

再哈希法又叫双哈希法（并不是2个的意思），有多个不同的哈希构造函数，当发生冲突时使用第二个，第三个，第四个...，等哈希函数计算地址，直到计算出无冲突的地址，该方法虽然不易产生聚集，但是新增了计算时间。

（3）链地址法

使用单向链表把分配到同一个位置上的节点链接起来。该方法不会产生聚集，但是会增加空间的消耗，适合不确定表长，经常进行插入和删除的情况，java中的集合大多使用该方式，如HashMap，HashTable。

（4）建立公共溢出区

将哈希表分为基本表和溢出表两部分，有冲突的元素放入到溢出表中存储。

哈希在String的应用

理解了哈希的基本概念，下面我们研究下哈希在Java中的一些应用。

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

上面这段代码是String计算哈希码的方法，从源码中可以看出，有一个固定值31，然后循环字符串进行乘积计算，即H(key)=s[0]31^(n-1) + s[1]31^(n-2) + ... + s[n-1]，其中s [i]是字符串的第i个字符，n是字符串的长度，有点类似直接定址构造方法，但是又加上一层乘积运算，实现起来比较简单，但是为什么选择31作为乘积值呢？

这个问题网上讨论的也比较多，摘取两个比较热门的答案。

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

这段回答来自《Effective Java》的内容，意思是说31是个不大不小的质数，如果是偶数会导致乘积运算溢出，因为乘以2相当于移位运算，此外是为了获得更好的性能，乘法可以被移位和减法代替，即31 * i == (i << 5) - i，目前jvm虚拟机也会自动支持此类的优化。

As Goodrich and Tamassia point out, If you take over 50,000 English words (formed as the union of the word lists provided in two variants of Unix), using the constants 31, 33, 37, 39, and 41 will produce less than 7 collisions in each case. Knowing this, it should come as no surprise that many Java implementations choose one of these constants.

这个从实战角度回答，使用超过50000个英文单词进行哈希计算，并且使用常数31，33，37，39个41作为乘子，得到计算的碰撞结果就知道为什么使用31了。

下面进行简单的测试，准备了十万个单词，哈希函数和String的哈希函数保持一致，只需要替换乘积，循环乘积分别计算所有单词的碰撞概率统计。

public static Integer hashCode(String word, Integer multiplier) {
    int hash = 0;
    for (int i = 0; i < word.length(); i++) {
        hash = multiplier * hash + word.charAt(i);
    }
    return hash;
}

public static void main(String[] args) {
    Set<String> words = new HashSet<>();
    try {
        FileInputStream fileInputStream = new FileInputStream("C:\\Users\\Shane\\Desktop\\单词库.txt");
        InputStreamReader inputStreamReader = new InputStreamReader(fileInputStream, StandardCharsets.*UTF_8*);
        BufferedReader bufferedReader = new BufferedReader(inputStreamReader);
        String word;
        while (Objects.*nonNull*((word = bufferedReader.readLine()))) {
            words.add(word.split("\t")[1]);
        }
        bufferedReader.close();
        inputStreamReader.close();
    } catch (Exception ignore) {
        return;
    }

    List<Integer> multipliers = Arrays.*asList*(2, 3, 7, 17, 31, 32, 33, 37, 39, 41, 64, 101, 199);
    for (Integer multiplier : multipliers) {
        // 获取哈希值列表
        List<Integer> hashList = words.stream().map(word -> *hashCode*(word, multiplier)).collect(Collectors.*toList*());
        int collisionCount = (int) (hashList.size() - hashList.stream().distinct().count());
        double collisionRate = (collisionCount * 1.0) / hashList.size() * 100;
        System.*out*.println(String.*format*("乘数 = %4d, 碰撞数量 =%6d, 碰撞概率 = %.4f%%", multiplier, collisionCount, collisionRate));
    }
}

测试结果

从结果图可以看出，使用较小的质数作为乘子时冲突会很高，尤其是质数2，哈希的取值范围很小，基本一半出现碰撞。随着质数的增大碰撞概率逐渐较小，像31，33，37，39都有很小的碰撞概率，而偶数32和64的碰撞概率很高，最后的质数101和199也有很小的碰撞概率，但这个范围值已经远超过int的取值范围了，用此数计算会丢失信息。

哈希分布

我们上面说了，哈希函数的构造是本着简单和均匀原则，那我们在看看用31作为乘积计算是否会影响哈希值的散列分布。实验也比较简单，在上个实验基础之上，把hash可能值（即int的最小值到最大值）从小到大分成64个区间，然后把我们的计算出的哈希值分别放到对应区间之内就行。

public static void hashDistribute(List<Integer> hashList) {
    // 这里为了分区准确放大100倍进行计算
    long length = Math.*round*(Integer.*MAX_VALUE* * 100L * 2L / 64L / 100L);
    for (long i = Integer.*MIN_VALUE*; i <= Integer.*MAX_VALUE*; i += length) {
        long start = i;
        long end = i + length;
        long count = hashList.stream().filter(hash -> hash >= start && hash < end).count();
        System.*out*.print(String.*format*("%6d", count));
    }
    System.*out*.println();
}

计算结果（太长了，我只截取一半）

为了方便观察，我们把数据转成折线图，如下：

上图可以明显看出乘子是2时数据几乎全部分布在中间区域，3，4，17乘子大部分数据也都在中间，接下来我们把这些分布明显不均匀的乘子数据去掉，结果如下图。

上图可以看出32乘积数据有多个小高锋，32和37相对均匀，但是与31相比还是相差甚多。

哈希在集合中的应用

接下来再看下哈希在java数据集合中的一些应用，我们最常用的就是HashMap和HashTable了，哈希在HashTable中的应用很简单，获取hashCode之后与Int最大值进行与操作，这里是为了保证结果为非负数，之后在于数组长度进行取模运算得到索引下标。

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

相比较于HashTable，HashMap的索引更有意思，它在哈希基础之上又加了一个扰动函数用于优化散列效果，代码如下。

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

“(h = key.hashCode()) ^ (h >>> 16)”简单解释下这段代码，key.hashCode()是获取哈希值，然后再把哈希值右移16为，之后再再用原哈希值和右移之后的哈希值做异或运算，这样会混合哈希值的高低位增大随机性，使散列分布更均匀，得出哈希值之后再与数组长度-1进行取模运算得出数组索引。