散列表(中)

Friday, April 26, 2019

如何设计散列函数

散列函数查询效率不能简单的说成O(1),如果设计的不好,甚至有可能会变成O(n)。所以我们要设计一个可以应对各种异常情况的工业级散列表,避免散列冲突的情况下,散列表性能的急剧下降,并且能抵抗散列撞击攻击。

散列函数设计的好坏,决定了散列冲突的概率大小,也决定了散列的性能。

好的散列函数要满足以下几点

  • 散列函数的设计不能过于复杂,过于复杂会消耗很多计算时间,影响性能。
  • 散列函数生成的值要尽可能随机并且均匀分布,这样才能最小化散列冲突。

散列函数的设计方法有很多,比如学生会运动会学生的参赛编号的后两位作为散列值,又比如手机号,前面的重复可能性很大,取后四位作为散列值。这种称为数据分析法。

散列函数的设计方法很多,比如直接寻址法,平方取中法,折叠法,随机数等。

装载因子过大怎么办

  • 装载因子过大,不仅插入过程要多次寻址,查找过程也会变慢。
  • 对于动态散列表来讲,数据集合是频繁变动的,我们事先无法预估将要加入的数据个数,所以需要动态扩容。

我们可以设定当装载因子大于0.8的时候,申请一个两倍大小的空间,将数据迁移过去。 针对数组的迁移比较简单,但是针对散列表则复杂的多,因为散列表的大小变了,数据的存储位置也变了,所以需要重新通过散列函数重新计算数据的位置。

file

插入一个数据,不用扩容的情况下,最好时间复杂度是O(1),最坏是要扩容,O(n),用均摊法后,还是O(1)

实际上随着数据的删除,散列表的数据会越来越少,空闲空间会越来越大,这时我们可以动态缩容。

如何避免低效地扩容

前面我们知道,插入数据很快,当需要扩容的时候则比较慢。假如数据量很大的时候,迁移的时间则是非常耗时的。

为了解决这个问题,我们可以将扩容穿插在插入操作的过程,分批完成。当装载因子达到阈值,我们只申请新空间,不迁移。

当有新数据插入,我们将新数据插入到新散列表,并且从老的散列表拿一个数据到新的。

file

这时查找,我们就先查新的,再查旧的。

如何选择解决冲突的方法

开放寻址法

优点:

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

缺点:

  • 解决冲突的散列表,删除数据时比较麻烦,需要标记。
  • 所有数据都在一个数组中,冲突的代价更高。
  • 因为装载因子不能过大,导致这种方法比链表更浪费内存空间。

当数据量小比较小,装载因子比较小,适合采用开放寻址法。Java的ThreadLocalMap就是使用开放寻址法。

链表法

  • 链表法对内存的利用率更高,可以在需要的时候再创建节点,不需要事先申请好。
  • 对大装载因子容忍度更高。开放寻址法只适合1以内的情况,但是链表法,只要散列函数的值随机均匀,即便装载因子变成10,也能用。
  • 链表因为要存储指针,所以内存消耗会稍微多点,且链表的结点是零散分布在内存中,对CPU缓存不友好,对执行效率有一点影响。
  • 对链表进行改造,可以更高效。比如把链表改成跳表,红黑树。

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

工业级散列表举例分析

下面介绍一下Java的HashMap

初始化大小

HashMap的初始化大小是16,默认值是可以设置的,如果事先知道数据量,可以减少扩容次数,提高性能。

装载因子和动态扩容

最大装载因子默认是0.75,当HashMap元素超过0.75*capacity(散列表容量),就会扩容,扩成两倍。

散列冲突解决方法

HashMap底层采用链表法来解决冲突,但即使设计的再合理,也免不了拉链过长,一旦如此,就会严重影响性能。

在JDK1.8中,为了进一步优化,当链表长度超过8时(默认值),链表就转换为红黑树。

散列函数

散列函数设计的并不复杂,追求的是简单高效,分布均匀。

    int hash(Object key) {
        int h = key.hashCode();
        return (h ^ (h >>> 16)) & (capitity -1); //capicity 表示散列表的大小
    }

hashCode返回的是JAVA对象的hash code,比如string的hashCode()

    public int hashCode() {
      int var1 = this.hash;
      if(var1 == 0 && this.value.length > 0) {
        char[] var2 = this.value;
        for(int var3 = 0; var3 < this.value.length; ++var3) {
          var1 = 31 * var1 + var2[var3];
        }
        this.hash = var1;
      }
      return var1;
    }

总结

一个工业级的散列表,应该有如下特性

  • 支持快速查询,插入,删除操作
  • 内存占用合理,不能浪费过多内存
  • 性能稳定,极端情况下,散列表的性能也不会退化到无法接受

如何设计出来呢?

  • 设计一个合适的散列函数
  • 定义装载因子阈值,并且设计动态扩容
  • 选择合适的散列冲突解决办法
数据结构-算法

散列表(下)

散列表(上)