README.md

hash复杂度计算例子

之前学过不少平衡树, 便一度认为对类似于Set集合的查询和插入操作, 最低都只能为O(logn);

最近请教别人思路后, 尝试计算了一下hash算法的复杂度, 发现用hash来实现确实是能将复杂度将为O(1);

如此看来, 平衡树实现Set的好处是能同时维护数据的有序性, 缺点则是复杂度增高, 不如hash快;

下面通过一个简单的hash算法来举例计算其复杂度;

算法描述

需求

需要你实现一个数据结构, 支持下面两种操作:

• set(k, v): 将k作为键值, v作为内容存入该数据结构中;
• get(k): 根据k, 从该数据结构中取出其v;

hash算法设计

hash函数

首先假定我们有一个hash函数, hash(k, seed, lim);

他能把键值k, 根据hash种子值seed, hash成一个[0, lim)范围内的数字;

算法实现

接下来利用上述hash函数实现我们的算法;

假设我们有n个kv键值对需要插入;

于是我们提前开辟2n大小的空间作为卡槽来存放这些数据;

对于set(k, v), 我们操作如下:

for i := 0; ; i++ {
    x := hash(k, i, 2*n)
    if slots[x].k == nil || slots[x].v == v {
        slots[x] = {k, v}
        break
    }
}

大致思路就是不断的用hash重试, 直到找到空的卡槽来存放数据;

对于get(k), 类似:

for i := 0; ; i++ {
    x := hash(k, i, 2*n)
    if slots[x].k == nil {
        return nil
    }
    if slots[x].k == k {
        return slots[x].v
    }
}

同set(k, v)类似;

复杂度计算

前提概念

我们直接看将全部n个键值对全部进行set的均摊复杂度;

我们用E(k), 来表示将第k个数set进去的hash次数期望, k从0开始;

同时用P(k, i), 表示第k个数, 被hash了i次后就能被放入的概率;

则E(k) = Sigma(P(k, i) * i), (i=1, 2, 3, 4, ...)

初步计算

首先, E(0) = P(0, 1) = 1; 这是显然的, 因为一开始所有卡槽都是空的, 只需要一次hash;

现在计算E(1);

P(1, 1) = (2n-1)/2n;

P(1, 2) = 1/2n * P(1, 1);

P(1, 3) = 1/2n * P(1, 2);

P(1, k) = 1/2n * P(1, k-1);

...

展开后, 可以得到E(1)为一个无穷级数, 最后很容易能计算出其值为: 2n/(2n-1);

进一步计算

现在计算E(k), (0 < k < n);

P(k, 1) = (2n-k)/2n

P(k, 2) = k/2n * P(1, 1);

...

同理, 很容易得到E(k) = 2n/(2n-k);

最后计算

由于k < n, 于是E(k) < 2;

因此, 整体均摊复杂度 < 2, 于是复杂度为O(1);

其他

上述计算过程只假设了set操作;

引入get后的计算方式类似, 就不赘述了;