💎一站式轻松地调用各大LLM模型接口,支持GPT4、智谱、星火、月之暗面及文生图 广告
# 练习38:哈希算法 > 原文:[Exercise 38: Hashmap Algorithms](http://c.learncodethehardway.org/book/ex38.html) > 译者:[飞龙](https://github.com/wizardforcel) 你需要在这个练习中实现下面这三个哈希函数: FNV-1a 以创造者Glenn Fowler、Phong Vo 和 Landon Curt Noll的名字命名。这个算法产生合理的数值并且相当快。 Adler-32 以Mark Adler命名。一个比较糟糕的算法,但是由来已久并且适于学习。 DJB Hash 由Dan J. Bernstein (DJB)发明的哈希算法,但是难以找到这个算法的讨论。它非常快,但是结果不是很好。 你应该看到我使用了Jenkins hash作为`Hashmap`数据结构的默认哈希函数,所以这个练习的重点会放在这三个新的函数上。它们的代码通常来说不多,并且没有任何优化。像往常一样我会放慢速度来让你理解。 头文件非常简单,所以我以它开始: ```c #ifndef hashmap_algos_h #define hashmap_algos_h #include <stdint.h> uint32_t Hashmap_fnv1a_hash(void *data); uint32_t Hashmap_adler32_hash(void *data); uint32_t Hashmap_djb_hash(void *data); #endif ``` 我只是声明了三个函数,我会在`hashmap_algos.c`文件中实现它们: ```c #include <lcthw/hashmap_algos.h> #include <lcthw/bstrlib.h> // settings taken from // http://www.isthe.com/chongo/tech/comp/fnv/index.html#FNV-param const uint32_t FNV_PRIME = 16777619; const uint32_t FNV_OFFSET_BASIS = 2166136261; uint32_t Hashmap_fnv1a_hash(void *data) { bstring s = (bstring)data; uint32_t hash = FNV_OFFSET_BASIS; int i = 0; for(i = 0; i < blength(s); i++) { hash ^= bchare(s, i, 0); hash *= FNV_PRIME; } return hash; } const int MOD_ADLER = 65521; uint32_t Hashmap_adler32_hash(void *data) { bstring s = (bstring)data; uint32_t a = 1, b = 0; int i = 0; for (i = 0; i < blength(s); i++) { a = (a + bchare(s, i, 0)) % MOD_ADLER; b = (b + a) % MOD_ADLER; } return (b << 16) | a; } uint32_t Hashmap_djb_hash(void *data) { bstring s = (bstring)data; uint32_t hash = 5381; int i = 0; for(i = 0; i < blength(s); i++) { hash = ((hash << 5) + hash) + bchare(s, i, 0); /* hash * 33 + c */ } return hash; } ``` 这个文件中有三个哈希函数。你应该注意到我默认使用`bstring`作为键,并且使用了`bchare`函数从字符串获取字符,然而如果字符超出了字符串的长度会返回0。 这些算法中每个都可以在网上搜索到,所以你需要搜索它们并阅读相关内容。同时我主要使用维基百科上的结果,之后参照了其它来源。 接着我为每个算法编写了单元测试,同时也测试了它们在多个桶中的分布情况。 ```c #include <lcthw/bstrlib.h> #include <lcthw/hashmap.h> #include <lcthw/hashmap_algos.h> #include <lcthw/darray.h> #include "minunit.h" struct tagbstring test1 = bsStatic("test data 1"); struct tagbstring test2 = bsStatic("test data 2"); struct tagbstring test3 = bsStatic("xest data 3"); char *test_fnv1a() { uint32_t hash = Hashmap_fnv1a_hash(&test1); mu_assert(hash != 0, "Bad hash."); hash = Hashmap_fnv1a_hash(&test2); mu_assert(hash != 0, "Bad hash."); hash = Hashmap_fnv1a_hash(&test3); mu_assert(hash != 0, "Bad hash."); return NULL; } char *test_adler32() { uint32_t hash = Hashmap_adler32_hash(&test1); mu_assert(hash != 0, "Bad hash."); hash = Hashmap_adler32_hash(&test2); mu_assert(hash != 0, "Bad hash."); hash = Hashmap_adler32_hash(&test3); mu_assert(hash != 0, "Bad hash."); return NULL; } char *test_djb() { uint32_t hash = Hashmap_djb_hash(&test1); mu_assert(hash != 0, "Bad hash."); hash = Hashmap_djb_hash(&test2); mu_assert(hash != 0, "Bad hash."); hash = Hashmap_djb_hash(&test3); mu_assert(hash != 0, "Bad hash."); return NULL; } #define BUCKETS 100 #define BUFFER_LEN 20 #define NUM_KEYS BUCKETS * 1000 enum { ALGO_FNV1A, ALGO_ADLER32, ALGO_DJB}; int gen_keys(DArray *keys, int num_keys) { int i = 0; FILE *urand = fopen("/dev/urandom", "r"); check(urand != NULL, "Failed to open /dev/urandom"); struct bStream *stream = bsopen((bNread)fread, urand); check(stream != NULL, "Failed to open /dev/urandom"); bstring key = bfromcstr(""); int rc = 0; // FNV1a histogram for(i = 0; i < num_keys; i++) { rc = bsread(key, stream, BUFFER_LEN); check(rc >= 0, "Failed to read from /dev/urandom."); DArray_push(keys, bstrcpy(key)); } bsclose(stream); fclose(urand); return 0; error: return -1; } void destroy_keys(DArray *keys) { int i = 0; for(i = 0; i < NUM_KEYS; i++) { bdestroy(DArray_get(keys, i)); } DArray_destroy(keys); } void fill_distribution(int *stats, DArray *keys, Hashmap_hash hash_func) { int i = 0; uint32_t hash = 0; for(i = 0; i < DArray_count(keys); i++) { hash = hash_func(DArray_get(keys, i)); stats[hash % BUCKETS] += 1; } } char *test_distribution() { int i = 0; int stats[3][BUCKETS] = {{0}}; DArray *keys = DArray_create(0, NUM_KEYS); mu_assert(gen_keys(keys, NUM_KEYS) == 0, "Failed to generate random keys."); fill_distribution(stats[ALGO_FNV1A], keys, Hashmap_fnv1a_hash); fill_distribution(stats[ALGO_ADLER32], keys, Hashmap_adler32_hash); fill_distribution(stats[ALGO_DJB], keys, Hashmap_djb_hash); fprintf(stderr, "FNV\tA32\tDJB\n"); for(i = 0; i < BUCKETS; i++) { fprintf(stderr, "%d\t%d\t%d\n", stats[ALGO_FNV1A][i], stats[ALGO_ADLER32][i], stats[ALGO_DJB][i]); } destroy_keys(keys); return NULL; } char *all_tests() { mu_suite_start(); mu_run_test(test_fnv1a); mu_run_test(test_adler32); mu_run_test(test_djb); mu_run_test(test_distribution); return NULL; } RUN_TESTS(all_tests); ``` 我在代码中将`BUCKETS`的值设置得非常高,因为我的电脑足够快。如果你将它和`NUM_KEYS`调低,就会比较慢了。这个测试运行之后,对于每个哈希函数,通过使用R语言做统计分析,可以观察键的分布情况。 我实现它的方式是使用`gen_keys`函数生成键的大型列表。这些键从`/dev/urandom`设备中获得,它们是一些随机的字节。之后我使用了这些键来调用`fill_distribution`,填充了`stats `数组,这些键计算哈希值后会被放入理论上的一些桶中。所有这类函数会遍历所有键,计算哈希,之后执行类似`Hashmap`所做的事情来寻找正确的桶。 最后我只是简单打印出一个三列的表格,包含每个桶的最终数量,展示了每个桶中随机储存了多少个键。之后可以观察这些数值,来判断这些哈希函数是否合理对键进行分配。 ## 你会看到什么 教授R是这本书范围之外的内容,但是如果你想试试它,可以访问[r-project.org](http://www.r-project.org/)。 下面是一个简略的shell会话,向你展示了我如何运行`1tests/hashmap_algos_test`来获取`test_distribution`产生的表(这里没有展示),之后使用R来观察统计结果: ```sh $ tests/hashmap_algos_tests # copy-paste the table it prints out $ vim hash.txt $ R > hash <- read.table("hash.txt", header=T) > summary(hash) FNV A32 DJB Min. : 945 Min. : 908.0 Min. : 927 1st Qu.: 980 1st Qu.: 980.8 1st Qu.: 979 Median : 998 Median :1000.0 Median : 998 Mean :1000 Mean :1000.0 Mean :1000 3rd Qu.:1016 3rd Qu.:1019.2 3rd Qu.:1021 Max. :1072 Max. :1075.0 Max. :1082 ``` 首先我只是运行测试,它会在屏幕上打印表格。之后我将它复制粘贴到下来并使用`vim hash.txt`来储存数据。如果你观察数据,它会带有显示这三个算法的`FNV A32 DJB`表头。 接着,我运行R来使用`read.table`命令加载数据集。它是个非常智能的函数,适用于这种tab分隔的数据,我只要告诉它`header=T`,它就知道数据集中带有表头。 最后,我家在了数据并且可以使用`summary`来打印出它每行的统计结果。这里你可以看到每个函数处理随机数据实际上都没有问题。我会解释每个行的意义: Min. 它是列出数据的最小值。FNV似乎在这方面是最优的,因为它有最大的结果,也就是说它的下界最严格。 1st Qu. 数据的第一个四分位点。 Median 如果你对它们排序,这个数值就是最重点的那个数。中位数比起均值来讲更有用一些。 Mean 均值对大多数人意味着“平均”,它是数据的总数比数量。如果你观察它们,所有均值都是1000,这非常棒。如果你将它去中位数对比,你会发现,这三个中位数都很接近均值。这就意味着这些数据都没有“偏向”一端,所以均值是可信的。 3rd Qu. 数据后四分之一的起始点,代表了尾部的数值。 Max. 这是数据中的最大值,代表了它们的上界。 观察这些数据,你会发现这些哈希算法似乎都适用于随机的键,并且均值与我设置的`NUM_KEYS`匹配。我所要找的就是如果我为每个桶中生成了1000个键,那么平均每个桶中就应该有100个键。如果哈希函数工作不正常,你会发现统计结果中均值不是1000,并且第一个和第三个四分位点非常高。一个好的哈希算法应该使平均值为1000,并且具有严格的范围。 同时,你应该明白即使在这个单元测试的不同运行之间,你的数据的大多数应该和我不同。 ## 如何使它崩溃 这个练习的最后,我打算向你介绍使它崩溃的方法。我需要让你变写你能编写的最烂的哈希函数,并且我会使用数据来证明它确实很烂。你可以使用R来进行统计,就像我上面一样,但也可能你知道其他可以使用的工具来进行相同的统计操作。 这里的目标是让一个哈希函数,它表面看起来是正常的,但实际运行就得到一个糟糕的均值,并且分布广泛。这意味着你不能只让你返回1,而是需要返回一些看似正常的数值,但是分布广泛并且都填充到相同的桶中。 如果你对这四个函数之一做了一些小修改来完成任务,我会给你额外的分数。 这个练习的目的是,想像一下一些“友好”的程序员见到你并且打算改进你的哈希函数,但是实际上只是留了个把你的`Hashmap`搞砸的后门。 ## 附加题 + 将`hashmap.c`中的`default_hash`换成`hashmap_algos.c`中的算法之一,并且再次通过所有测试。 + 向`hashmap_algos_tests.c`添加`default_hash`,并将它与其它三个哈希函数比较。 + 寻找一些更多的哈希函数并添加进来,你永远都不可能找到太多的哈希函数!