練習38：哈希算法 · 笨辦法學C

# 練習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`，并將它與其它三個哈希函數比較。 + 尋找一些更多的哈希函數并添加進來，你永遠都不可能找到太多的哈希函數！