关于separate chaining的Hash Table的一些分析

bdb 1.8x中用一个hash map来索引内存中Page。(代码在http://svn.freebsd.org/base/head/lib/libc/db/mpool/mpool.c)。这是一个静态hash,bucket的数量是固定大小。因为我准备拿这种数据结构给游戏做玩家数据的cache管理,因为首先,游戏的单服在线人数很容易预估,其次,静态hash的并发版本更容易实现。

假设这个Hash Table的capacity(bucket的数量)是m, size(元素的数量)是n。那么很容易算出,每个链表的长度(每个bucket中元素的个数)的数学期望是\(\frac{m}{n}\)。假设是为了查找一个存在的元素,那么这个元素所在的bucket中,除了它自己之外,其它元素的个数的数学期望是\(\frac{m-1}{n}\),所以总长度是\(1+\frac{m-1}{n}\)。如果将\(\frac{m}{n}\)定于为load factor,那么对于一个capacity会动态增长的hash table来说,为了查找一个就在其中的元素,它的平均查找时间是一个常数(因为hash function所需要花的时间也是常数)。查找时间的下限很容易计算,那么上限呢?

假设hash function很完美,以等可能的把元素分配到每个bucket中,那么,n个元素插入的过程就是n次独立重复试验,所以链表的长度恰好符合二项分布,当n比较大的时候,可以用泊松分布来模拟二项分布。假设load factor=1,最终可以得出,对于充分大的n,链表的最大长度至少以\(1-\frac{1}{n}\)的概率至少为\(\frac{\ln{n}}{\ln{\ln{n}}}\)。比如当table size等于1百万的时候,链表的最大长度以99.9999%的概率大于等于6。实际上测试的结果,发现这个估计过于乐观。

测试代码:

public static void main(String[] args) throws Exception {
    Random r = new Random();
    for (int length = 64; length <= 1048576; length *= 2) {
        int[] bucket = new int[length];
        for (int i = 0; i != length; ++i) {
            bucket[r.nextInt(length)]++;
        }
        int max = -1;
        for (int b : bucket) {
            max = Math.max(max, b);
        }
        System.out.println(String.format("size=%d,expect %f,actual %d\n", length,Math.log(length)/Math.log(Math.log(length)),max));
    }
}

输出结果为

size=64,expect 2.918010,actual 4
size=128,expect 3.072077,actual 5
size=256,expect 3.237250,actual 4
size=512,expect 3.407595,actual 7
size=1024,expect 3.580172,actual 6
size=2048,expect 3.753414,actual 6
size=4096,expect 3.926450,actual 6
size=8192,expect 4.098783,actual 6
size=16384,expect 4.270130,actual 6
size=32768,expect 4.440334,actual 8
size=65536,expect 4.609312,actual 8
size=131072,expect 4.777030,actual 9
size=262144,expect 4.943481,actual 10
size=524288,expect 5.108679,actual 9
size=1048576,expect 5.272646,actual 9

今天先睡了,明天我试着为它找一个更准确的估计。

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥