散列表

散列表(Hash table,也叫哈希表),是根据键 (Key) 而直接访问在内存存储位置的数据结构,散列表需要用到随机访问,所以散列表其实就是一个数组


散列函数(hash function)

我们知道散列表其实就是数组,数组是由下标访问的,所以我们需要一个函数来计算存储对象的key,将其转化为 >0 的整数(即为数组的下标)

如果hash表大小为10,如果我们数字是均匀随机的,无需特殊的散列函数,只要将数字 % 10 即可

一般平常都会对字符串作为key,hash函数可以设计为如下

unsigned int
hash_key(char *data, int len)
{
    unsigned int  i, key;<br>
    key = 0;

    for (i = 0; i < len; i++) {
        key = key*31 + data[i];
    }

    return key;
}

int main()
{
    unsinged int index = hash_key("abc", 3) % 10;
    return 0;
}

对于一些特殊场合,散列方法可以改变,比如手机号码前几位大多情况下是一样的,我们可以忽略前几位来增加hash函数的性能

有些地方不用31,而用13,这些都是前人总结出来的,小的质数可以减少碰撞几率并且性能也不错

for (i = 0; i < len; i++) {
        key = key*13 + data[i];
    }



散列冲突(hash collision)

当我们用散列函数对不同对象计算出相同的索引值时,称为散列冲突,一般有2种解决方案

1.开放寻址法(open addressing)

开放寻址法的核心思想是,如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。

那如何重新探测新的位置呢?我先讲一个比较简单的探测方法,线性探测(Linear Probing)。当我们往散列表中插入数据时,如果某个数据经过散列函数散列之后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止


对于开放寻址冲突解决方法,除了线性探测方法之外,还有另外两种比较经典的探测方法 二次探测 (Quadratic probing) 和双重散列 (Double hashing)。

所谓二次探测,跟线性探测很像,线性探测每次探测的步长是 1,那它探测的下标序列就是 hash(key)+0,hash(key)+1,hash(key)+2……而二次探测探测的步长就变成了原来的“二次方”,也就是说,它探测的下标序列就是 hash(key)+0,hash(key)+1^2,hash(key)+2^2……

所谓双重散列,意思就是不仅要使用一个散列函数。我们使用一组散列函数 hash1(key),hash2(key),hash3(key)……我们先用第一个散列函数,如果计算得到的存储位置已经被占用,再用第二个散列函数,依次类推,直到找到空闲的存储位置

不管采用哪种探测方法,当散列表中空闲位置不多的时候,散列冲突的概率就会提高。为了尽可能保证散列表的操作效率,一般情况下,我们会尽可能保证散列表中有一定比例的空闲槽位

装载因子(load factor)

装载因子 = 填入表中的元素个数 / 散列表的长度

装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降


2.链表法(Separate chaining with linked lists)

链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。我们来看这个图,在散列表中,每个 桶(bucket) 或者 槽(slot) 会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中



如何设计散列函数

散列函数的设计不能太复杂,过于复杂的散列函数,会消耗很多计算时间。其次,散列函数生成的值要尽可能随机并且均匀分布,这样才能避免或者最小化散列冲突,而且即便出现冲突,散列到每个槽里的数据也会比较平均,不会出现某个槽内数据特别多的情况


装载因子过大

当装载因子过大时,散列冲突概率就会提高


装载因子的选择

装载因子阈值的设置要权衡时间、空间复杂度。如果内存空间不紧张,对执行效率要求很高,可以降低负载因子的阈值

相反,如果内存空间紧张,对执行效率要求又不高,可以增加负载因子的值,甚至可以大于 1


开放寻址法优缺点

散列表中的数据都存储在数组中,可以有效地利用 CPU 缓存加快查询速度。而且,这种方法实现的散列表,序列化起来比较简单

缺点是删除数据的时候比较麻烦,需要特殊标记已经删除掉的数据。而且,在开放寻址法中,所有的数据都存储在一个数组中,比起链表法来说,冲突的代价更高。所以,使用开放寻址法解决冲突的散列表,装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间


链表法优缺点

链表法对内存的利用率比开放寻址法要高。因为链表结点可以在需要的时候再创建,并不需要像开放寻址法那样事先申请好

链表法比起开放寻址法,对大装载因子的容忍度更高。开放寻址法只能适用装载因子小于 1 的情况。接近 1 时,就可能会有大量的散列冲突,导致大量的探测、再散列等,性能会下降很多。

但是对于链表法来说,只要散列函数的值随机均匀,即便装载因子变成 10,也就是链表的长度变长了而已,虽然查找效率有所下降,但是比起顺序查找还是快很多

链表法更加灵活,可以将链表改造成跳表、红黑树这样的数据结构,这样就算有大量的冲突也没事,查询控制在O(logn)

缺点:是cpu缓存利用不高,并且需要额外的指针空间开销,不适合序列化

总结:基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表,而且,比起开放寻址法,它更加灵活,支持更多的优化策略,比如用红黑树代替链表


工业级散列表设计例子-java HashMap

1.槽初始大小为16,当然这个默认值是可以设置的,如果事先知道大概的数据量有多大,可以通过修改默认初始大小,减少动态扩容的次数,这样会大大提高 HashMap 的性能

2.最大装载因子默认是 0.75,当超过该装载因子,就会启动扩容,每次扩容都会扩容为原来的两倍大小

3.HashMap 底层采用链表法来解决冲突,当链表的长度超过8,转化为红黑树,当红黑树结点个数少于 8 个的时候,又会将红黑树转化为链表。因为在数据量较小的情况下,红黑树要维护平衡,比起链表来,性能上的优势并不明显

4.一个简单设计精良的散列函数


上一篇: trie树
下一篇: 堆-二叉堆
作者邮箱: 203328517@qq.com