数据结构与算法(10)_散列表

散列表

散列表英文名是”Hash Table”,我们平时也叫”哈希表”或者”Hash 表”.

散列表用的是数组支持按照下标随机访问的特性,所以散列表其实就是数组的一种扩展,由数组演化而来.

散列表用的就是数组支持按下标随机访问的时候,时间复杂度为O(1)的特性.我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置.当我们按照键值查询元素时,我们用同样的散列函数,将键值转话为数组下标,从对应的数组下标的位置取出数据.

散列函数

散列函数,顾名思义它是一个函数.我们可以把他定义成hash(key).其中key表示函数的键值,hash(key)的值表示经过散列函数计算得到的散列值.

散列函数设计的基本要求

散列函数计算得到的散列值是一个非负整数.
如果key1 == key2,那hash(key1) == hash(key2).
如果key1 != key2,那hash(key1) != hash(key2).

前两点没什么特别问题.至于第三点,在真实情况下要想找到一个不同的key对应的散列值都不一样的散列函数,几乎是不可能的.即便是MD5,SHA,CRC等哈希算法,也无法避免这种散列冲突.而且,因为数组的存储空间有限也会加大散列冲突的概率.

解决散列冲突

开放寻址法.

核心思想是,如果出现了散列冲突,我们就重新探测一个位置,将其插入.那如何探测新的位置呢?一个简单的方法是线性探测.

当我们往散列表中插入数据时,如果某个数据经过散列函数后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止.

//TODO 图11

图中,黄色表示空闲,橙色表示占用.从图中看出,散列表大小为10,在元素X插入散列表之前,已经有6个元素插入到散列表中.X经过Hash算法之后,被散列到下标为7的位置,但是这个位置已经有数据了,所以就产生了冲突.于是顺序地往后一个一个找,看有没有空闲位置,遍历到尾部之后还是没有找到空闲位置,于是在从表头找,直到找到空闲位置2,于是将其插入到这个位置.

在散列表中查找元素的过程有点类似插入过程.我们通过散列函数求出查找元素的键值对应的散列值,然后比较数组的下标为散列值的元素和要查找的元素.如果相等,则返回.否则就往后依次查找.如果遍历到空闲位置,还没有找到,就说明要查找的元素,不在散列表中.

对于线性探测法解决冲突的散列表,删除操作有些特别.我们不能单独的把删除元素设置为空.因为在查找的时候,通过线性探测方法,找到一个空闲位置,我们就可以认定数据不在散列表中.但是,这个空闲位置是我们通过删除造成的,就会导致查询方法失效.

我们将删除的元素,特殊标记为deleted.当线性探测查找的时候,遇到标记为deleted的空间,并不是停下来,而是继续查找.

线性探测存在很大的问题.当散列表中插入的数据越来越多时,散列冲突发生的可能性就越来越大,空闲位置越来越少,线性探测越来越久.极端情况下,需要变量整个散列表,最坏时间复杂度是O(n).

开发寻址法除了线性探测外,还有另外两种比较经典的探测方法二次探测和双重散列.

不管哪种方法,当散列表中空闲位置不多时,散列冲突的概率都会提高.为了尽可能保证散列表的操作效率,一般情况下,我们会尽可能的保证散列表中有一定比例的空闲位置.我们用装载因子来表示空位多少.公式为

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

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

链表法

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

//TODO, 图12

当插入的时候,我们只需要通过散列函数计算出对应的槽位,将其插入对应的链表即可,所以插入的时间复杂度O(1).当查找,删除一个元素时,我们同样通过散列函数计算出对应的槽,然后遍历链表查询或者删除.这两个操作的时间复杂度跟链表的长度k成正比,也就是O(k).对于散列表比均匀的散列函数来说,理论上k = n/m,其中n表示散列中数据的个数,m表示散列表中槽的个数.

如何打造一个工业级散列表

如何设计散列函数

首先,散列函数的设计不能太复杂.其次散列函数生成的值要尽可能的随机并且均匀的分布.

装载因子过大怎么办?

针对散列表,当装载因子过大时,我们可以进行动态扩容,重新申请一个更大的散列表,将数据搬移到新的散列表中.

针对数组的扩容,数据搬移操作比较简单.但是针对散列表的扩容,数据搬移会复杂的多.因为散列表的大小变了,数据存储的位置变了,所以我们要通过散列函数重新计算每个数据的位置.

对于支持动态扩容的散列表,插入操作的最好时间复杂度是O(1).最坏情况时间复杂度O(n).平均时间复杂度是O(1).

装载因子的阈值,要权衡时间,空间复杂度.如果内存空间不紧张,对执行效率要求很高,可以降低装载因子的阈值;相反,如果内存紧张,对执行效率要求不高,可以增加装载因子的阈值,甚至可以大于1.

如何避免低效的扩容

大部分情况下,动态扩容的散列表插入一个数据都很快,但在特殊情况下,当装载因子达到阈值,需要先进行扩容,再插入数据.这个时候插入数据就会变得很慢.

为了解决这个问题,我们可以将扩容操作,穿插在插入操作过程中,分批完成.当装载因子触达阈值之后,我们只申请新的空间,但并不将老数据搬移到新散列表中.

当有新数据插入时,我们将新数据插入到新散列表中,并且从老的散列表中拿出一个数据放到新的散列表中.每次插入都重复上面过程.经过多次插入操作后老的散列表的数据就一点一点搬移到新的散列表中了.

这个期间的查询操作,为了兼容新老散列表中的数据,我们先从新散列表中查找,如果没有再从老的散列表中查找.

如何选择冲突解决方案

开放寻址法

优点:

散列表的数据都存在数组中,可以有效的利用CPU的缓存,加快查询速度.
序列化比较简单

缺点:

删除数据比较麻烦,需要特殊标记删除掉的数据
所有数据都存在一个数组中,冲突的代价更高,装载因子不能过大,比较浪费空间

总结:

当数据量比较少,装载因子小的时候.适合用开放寻址法.Java中的ThreadLocalMap使用的是此方法解决散列冲突.

链表法

优点:

内存利用率比开放寻址发要高.需要时再创建,不必事先申请好.
对大装载因子的容忍度更高.即使装载因子变成10,也就是链表的长度变长了,虽然查找效率有下降,但也比顺序查找要快.

缺点:

链表需要存储指针,所以对较小的对象存储,是比较耗内存的,还有可能让内存的消耗翻倍.(但是在存储大的对象面前,可以忽略)
链表中的结点时零星分布在内存中的,对CPU缓存不太友好

我们可以对链表法进行改造,可以实现一个更加高效的散列表.那就是可以将链表法中的链表改成其他高效的动态数据结构比如跳表,红黑树.这样即便出现散列冲突,在极端情况下查找时间也不过是O(logn).这样也就避免了散列碰撞攻击.

总结:

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

工业级散列链表举例分析

Java中的HashMap就是一个工业级散列表,具体看一下,这些技术是怎么应用的

初始大小

HashMap的初始大小是16,这个默认值是可以设置的,如果事先知道大概的数据量,可以通过修改默认初始值大小,减少动态扩容次数,提高性能.
装载因子动态扩容

最大装载因子默认是0.75,当HashMap中的元素个数超过0.75*capacity(表示散列表的容量)的时候就会动态扩容,每次扩容为原来的2倍大小
散列冲突的解决办法

HashMap底层采用链表法解决散列冲突.在JDK1.8版本中做了进一步优化,引入红黑树.当链表长度太长(默认超过8)时,链表就转为红黑树.当红黑树结点少于8时又转化为链表.因为红黑树在数据量较小时,红黑树要维护平衡,性能优势不明显.
散列函数

散列函数并不复杂,追求简单高效,分布均匀.

int hash(Objec key){
	int h = key.hashCode();
	return (h ^ (h >>> 16)) & (capacity - 1);
}

其中hashCode的返回是Java对象的hash code.比如String对象的hash code 就是

public int hashCode() {
       int h = hash;
       final int len = length();
       if (h == 0 && len > 0) {
           for (int i = 0; i < len; i++) {
               h = 31 * h + charAt(i);
           }
           hash = h;
       }
       return h;
   }