数据结构中的散列与散列函数

2018年2月3日 0条评论 0人点赞

介绍数据结构中的散列的基本概念，以及散列函数，Java中HashMap中的散列函数以及Java8中HashMap中引入的红黑树。

文章目录

散列的基本概念

散列表（hash table）的实现常常叫做散列（hashing），散列是一种用于以常数平均时间执行插入、删除和查找的技术。

理想的散列表数据结构只不过是一个包含一些项（item）的具有固定大小的数组。每个关键字（key）被映射到从0到TableSize-1这个范围中的某个数，并且放到适当的单元中。这个映射就叫做散列函数（hash function）。

两个关键字映射到同一个值（哈希值一样）就叫做冲突（collision）。

散列函数

TableSize的选择

如果输入的关键字是整数，则一般合理的方法是直接返回key mod tableSize。而这时如果采用10作为tableSize，而关键字都以0为个位时，就会特别容易产生冲突。为了避免上面那样的情况，好的办法通常是保证表的大小是素数。

如何证明散列表的TableSize最好是素数？参考：Hash的TableSize最好是素数

Hash(N) = N % M

首先，我们要明白Hash的意义在于把一个大的集合A，映射到小的集合B。比如通过取余的方式进行Hash，集合A = {0, 1, …, M, M+1, …, 2*M, 2*M+1, …, 3*M, 3*M+1, …}就会被映射到集合B = {0, 1, 2, …, M – 1}。

然后，如果集合A的元素分布是{0, 1, 2, 3, 4, …}这样的话，M取质数还是合数都可以，最后整个集合A会被均匀地映射到{0, 1, …, M-1}。

（例子）但是，很多情况下我们的元素分布是有非1步长的，比如集合A = {0, 6, 12, 18, 24, 30, 36, …}，这时候就出现问题了。当M取合数时，比如M = 10，我们来看看映射的情况。0->0, 6->6, 12->2, 18->8, 24->4, 30->0, 36->6, …。此时我们很容易发现，最后映射到了集合B = {0, 6, 2, 8, 4} = {0, 2, 4, 6, 8}，和我们理想中的{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}差距很大啊。

有问题我们就要去解决啊。我们回到代数形式上来看，在N与M最大公因数为1的情况下，N % M后可以得到的一系列的余数r，而全体余数r的集合R就是{0, 1, 2, …, M-1}。每个余数r代表了一个N的集合，比如在上面的例子中余数0代表了N的集合{0, 10, 20, 30, …}，这个集合就叫做“同余类”。即余数集合R中有M个余数，每个余数r代表一个同余类。现在思路就很清晰了，我们最理想的方式就是将集合A映射到余数集合R上，即B = R。

接下来我们讨论一下为什么有时候无法完全利用余数集合R：

假设N = kn, M = km， N和M存在最大公因数k，此时可以将N % M = r转化为公式N = Mq + r，即kn = kmq + r。其中q是商，r是余数。“表面上”r的取值范围是{0, 1, 2, …, M-1}（忽视了只有N与M最大公因数为1时，才能取整个余数集合R的定理），一片和谐。但是可以对公式进行稍微的变换，n = mq + (r/k)，由于n和mq都是整数，则(r/k)也是整数。此时我们看一看到(r/k)的取值范围是{0, 1, 2, …, M/k} = {0, 1, 2, …, m}。恢复到原式，也是就r的“实际”取值范围是{0, k, 2*k, 3*k, …, m*k}，缩小了k倍。

一切都明了了，我们最后的目标就是保证N与M最大公因数为1。最简单的方式就是直接取M为质数！

HashMap中的散列

首先，HashMap中散列表的长度并不是素数，而是2的N次方。

HashMap用2的N次方作为散列表的长度是为了效率，在算下标的时候，HashMap调用的方法是：

(length - 1) & hash

如果length是2的N次方，那么(length-1)&hash就可以代替h%length来获取下标，这样，就用位运算代替了耗时的取模运算，而这个运算在HashMap中的使用频率很高，因此用位运算可以大大提高效率。

那么，HashMap如何保证长度不为素数却依然可以实现均匀散列呢？参考：https://stackoverflow.com/questions/15437345/java-a-prime-number-or-a-power-of-two-as-hashmap-size

HashMap通过对object的hashCode()再hash()缓和了这种冲突：

    /**
     * Computes key.hashCode() and spreads (XORs) higher bits of hash
     * to lower.  Because the table uses power-of-two masking, sets of
     * hashes that vary only in bits above the current mask will
     * always collide. (Among known examples are sets of Float keys
     * holding consecutive whole numbers in small tables.)  So we
     * apply a transform that spreads the impact of higher bits
     * downward. There is a tradeoff between speed, utility, and
     * quality of bit-spreading. Because many common sets of hashes
     * are already reasonably distributed (so don't benefit from
     * spreading), and because we use trees to handle large sets of
     * collisions in bins, we just XOR some shifted bits in the
     * cheapest possible way to reduce systematic lossage, as well as
     * to incorporate impact of the highest bits that would otherwise
     * never be used in index calculations because of table bounds.
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

HashMap通过将key的hashCode()的高16位与低16位进行异或操作，如果length-1比较短15(0x1111)，那么其实起作用的只有低4位，而进行了异或操作后就可以让更多的位数参与了运算，降低了冲突。具体理由在hash()方法的注释中也有了详细的说明。

HashMap中引入红黑树

虽然对散列表的长度与取值进行了优化，但是冲突在所难免，那么Java8中对于冲突进行了哪些优化呢？

Improve the performance of java.util.HashMap under high hash-collision conditions by using balanced trees rather than linked lists to store map entries. Implement the same improvement in the LinkedHashMap class.

在put()时，如果长度超过了8，就会将链表存储转成红黑树存储，将搜索速度由N提高到了logN。

//...
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);
//...

其他更多关于Java中的HashMap内部实现，参考：数据结构中的树

flyzy小站