• 欢迎光临flyzy小站!分享一些学习路上遇到的坑坑洼洼~

adad

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

介绍数据结构中的散列的基本概念,以及散列函数,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内部实现,参考:数据结构中的树

点赞