练习38：哈希算法

原文：Exercise 38: Hashmap Algorithms

译者：飞龙

你需要在这个练习中实现下面这三个哈希函数：

FNV-1a

以创造者Glenn Fowler、Phong Vo 和 Landon Curt Noll的名字命名。这个算法产生合理的数值并且相当快。

Adler-32

以Mark Adler命名。一个比较糟糕的算法，但是由来已久并且适于学习。

DJB Hash

由Dan J. Bernstein (DJB)发明的哈希算法，但是难以找到这个算法的讨论。它非常快，但是结果不是很好。

你应该看到我使用了Jenkins hash作为Hashmap数据结构的默认哈希函数，所以这个练习的重点会放在这三个新的函数上。它们的代码通常来说不多，并且没有任何优化。像往常一样我会放慢速度来让你理解。

头文件非常简单，所以我以它开始：

  1. #ifndef hashmap_algos_h
  2. #define hashmap_algos_h
  4. #include <stdint.h>
  6. uint32_t Hashmap_fnv1a_hash(void *data);
  8. uint32_t Hashmap_adler32_hash(void *data);
  10. uint32_t Hashmap_djb_hash(void *data);
  12. #endif

我只是声明了三个函数，我会在hashmap_algos.c文件中实现它们：

  1. #include <lcthw/hashmap_algos.h>
  2. #include <lcthw/bstrlib.h>
  4. // settings taken from
  5. // http://www.isthe.com/chongo/tech/comp/fnv/index.html#FNV-param
  6. const uint32_t FNV_PRIME = 16777619;
  7. const uint32_t FNV_OFFSET_BASIS = 2166136261;
  9. uint32_t Hashmap_fnv1a_hash(void *data)
  10. {
  11.     bstring s = (bstring)data;
  12.     uint32_t hash = FNV_OFFSET_BASIS;
  13.     int i = 0;
  15.     for(i = 0; i < blength(s); i++) {
  16.         hash ^= bchare(s, i, 0);
  17.         hash *= FNV_PRIME;
  18.     }
  20.     return hash;
  21. }
  23. const int MOD_ADLER = 65521;
  25. uint32_t Hashmap_adler32_hash(void *data)
  26. {
  27.     bstring s = (bstring)data;
  28.     uint32_t a = 1, b = 0;
  29.     int i = 0;
  31.     for (i = 0; i < blength(s); i++)
  32.     {
  33.         a = (a + bchare(s, i, 0)) % MOD_ADLER;
  34.         b = (b + a) % MOD_ADLER;
  35.     }
  37.     return (b << 16) | a;
  38. }
  40. uint32_t Hashmap_djb_hash(void *data)
  41. {
  42.     bstring s = (bstring)data;
  43.     uint32_t hash = 5381;
  44.     int i = 0;
  46.     for(i = 0; i < blength(s); i++) {
  47.         hash = ((hash << 5) + hash) + bchare(s, i, 0); /* hash * 33 + c */
  48.     }
  50.     return hash;
  51. }

这个文件中有三个哈希函数。你应该注意到我默认使用bstring作为键，并且使用了bchare函数从字符串获取字符，然而如果字符超出了字符串的长度会返回0。

这些算法中每个都可以在网上搜索到，所以你需要搜索它们并阅读相关内容。同时我主要使用维基百科上的结果，之后参照了其它来源。

接着我为每个算法编写了单元测试，同时也测试了它们在多个桶中的分布情况。

  1. #include <lcthw/bstrlib.h>
  2. #include <lcthw/hashmap.h>
  3. #include <lcthw/hashmap_algos.h>
  4. #include <lcthw/darray.h>
  5. #include "minunit.h"
  7. struct tagbstring test1 = bsStatic("test data 1");
  8. struct tagbstring test2 = bsStatic("test data 2");
  9. struct tagbstring test3 = bsStatic("xest data 3");
  11. char *test_fnv1a()
  12. {
  13.     uint32_t hash = Hashmap_fnv1a_hash(&test1);
  14.     mu_assert(hash != 0, "Bad hash.");
  16.     hash = Hashmap_fnv1a_hash(&test2);
  17.     mu_assert(hash != 0, "Bad hash.");
  19.     hash = Hashmap_fnv1a_hash(&test3);
  20.     mu_assert(hash != 0, "Bad hash.");
  22.     return NULL;
  23. }
  25. char *test_adler32()
  26. {
  27.     uint32_t hash = Hashmap_adler32_hash(&test1);
  28.     mu_assert(hash != 0, "Bad hash.");
  30.     hash = Hashmap_adler32_hash(&test2);
  31.     mu_assert(hash != 0, "Bad hash.");
  33.     hash = Hashmap_adler32_hash(&test3);
  34.     mu_assert(hash != 0, "Bad hash.");
  36.     return NULL;
  37. }
  39. char *test_djb()
  40. {
  41.     uint32_t hash = Hashmap_djb_hash(&test1);
  42.     mu_assert(hash != 0, "Bad hash.");
  44.     hash = Hashmap_djb_hash(&test2);
  45.     mu_assert(hash != 0, "Bad hash.");
  47.     hash = Hashmap_djb_hash(&test3);
  48.     mu_assert(hash != 0, "Bad hash.");
  50.     return NULL;
  51. }
  53. #define BUCKETS 100
  54. #define BUFFER_LEN 20
  55. #define NUM_KEYS BUCKETS * 1000
  56. enum { ALGO_FNV1A, ALGO_ADLER32, ALGO_DJB};
  58. int gen_keys(DArray *keys, int num_keys)
  59. {
  60.     int i = 0;
  61.     FILE *urand = fopen("/dev/urandom", "r");
  62.     check(urand != NULL, "Failed to open /dev/urandom");
  64.     struct bStream *stream = bsopen((bNread)fread, urand);
  65.     check(stream != NULL, "Failed to open /dev/urandom");
  67.     bstring key = bfromcstr("");
  68.     int rc = 0;
  70.     // FNV1a histogram
  71.     for(i = 0; i < num_keys; i++) {
  72.         rc = bsread(key, stream, BUFFER_LEN);
  73.         check(rc >= 0, "Failed to read from /dev/urandom.");
  75.         DArray_push(keys, bstrcpy(key));
  76.     }
  78.     bsclose(stream);
  79.     fclose(urand);
  80.     return 0;
  82. error:
  83.     return -1;
  84. }
  86. void destroy_keys(DArray *keys)
  87. {
  88.     int i = 0;
  89.     for(i = 0; i < NUM_KEYS; i++) {
  90.         bdestroy(DArray_get(keys, i));
  91.     }
  93.     DArray_destroy(keys);
  94. }
  96. void fill_distribution(int *stats, DArray *keys, Hashmap_hash hash_func)
  97. {
  98.     int i = 0;
  99.     uint32_t hash = 0;
  101.     for(i = 0; i < DArray_count(keys); i++) {
  102.         hash = hash_func(DArray_get(keys, i));
  103.         stats[hash % BUCKETS] += 1;
  104.     }
  106. }
  108. char *test_distribution()
  109. {
  110.     int i = 0;
  111.     int stats[3][BUCKETS] = {{0}};
  112.     DArray *keys = DArray_create(0, NUM_KEYS);
  114.     mu_assert(gen_keys(keys, NUM_KEYS) == 0, "Failed to generate random keys.");
  116.     fill_distribution(stats[ALGO_FNV1A], keys, Hashmap_fnv1a_hash);
  117.     fill_distribution(stats[ALGO_ADLER32], keys, Hashmap_adler32_hash);
  118.     fill_distribution(stats[ALGO_DJB], keys, Hashmap_djb_hash);
  120.     fprintf(stderr, "FNV\tA32\tDJB\n");
  122.     for(i = 0; i < BUCKETS; i++) {
  123.         fprintf(stderr, "%d\t%d\t%d\n",
  124.                 stats[ALGO_FNV1A][i],
  125.                 stats[ALGO_ADLER32][i],
  126.                 stats[ALGO_DJB][i]);
  127.     }
  129.     destroy_keys(keys);
  131.     return NULL;
  132. }
  134. char *all_tests()
  135. {
  136.     mu_suite_start();
  138.     mu_run_test(test_fnv1a);
  139.     mu_run_test(test_adler32);
  140.     mu_run_test(test_djb);
  141.     mu_run_test(test_distribution);
  143.     return NULL;
  144. }
  146. RUN_TESTS(all_tests);

我在代码中将BUCKETS的值设置得非常高，因为我的电脑足够快。如果你将它和NUM_KEYS调低，就会比较慢了。这个测试运行之后，对于每个哈希函数，通过使用R语言做统计分析，可以观察键的分布情况。

我实现它的方式是使用gen_keys函数生成键的大型列表。这些键从/dev/urandom设备中获得，它们是一些随机的字节。之后我使用了这些键来调用fill_distribution，填充了stats数组，这些键计算哈希值后会被放入理论上的一些桶中。所有这类函数会遍历所有键，计算哈希，之后执行类似Hashmap所做的事情来寻找正确的桶。

最后我只是简单打印出一个三列的表格，包含每个桶的最终数量，展示了每个桶中随机储存了多少个键。之后可以观察这些数值，来判断这些哈希函数是否合理对键进行分配。

你会看到什么

教授R是这本书范围之外的内容，但是如果你想试试它，可以访问r-project.org。

下面是一个简略的shell会话，向你展示了我如何运行1tests/hashmap_algos_test来获取test_distribution产生的表（这里没有展示），之后使用R来观察统计结果：

  1. $ tests/hashmap_algos_tests
  2. # copy-paste the table it prints out
  3. $ vim hash.txt
  4. $ R
  5. > hash <- read.table("hash.txt", header=T)
  6. > summary(hash)
  7.       FNV            A32              DJB      
  8.  Min.   : 945   Min.   : 908.0   Min.   : 927  
  9.  1st Qu.: 980   1st Qu.: 980.8   1st Qu.: 979  
  10.  Median : 998   Median :1000.0   Median : 998  
  11.  Mean   :1000   Mean   :1000.0   Mean   :1000  
  12.  3rd Qu.:1016   3rd Qu.:1019.2   3rd Qu.:1021  
  13.  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，并将它与其它三个哈希函数比较。
  • 寻找一些更多的哈希函数并添加进来，你永远都不可能找到太多的哈希函数！