练习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数据结构的默认哈希函数，所以这个练习的重点会放在这三个新的函数上。它们的代码通常来说不多，并且没有任何优化。像往常一样我会放慢速度来让你理解。

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

#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文件中实现它们：

#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。

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

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

#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。

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

$ 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，并将它与其它三个哈希函数比较。
寻找一些更多的哈希函数并添加进来，你永远都不可能找到太多的哈希函数！

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

ex38.md

ex38.md

练习38：哈希算法

你会看到什么

如何使它崩溃

附加题

Files

ex38.md

Latest commit

History

ex38.md

File metadata and controls

练习38：哈希算法

你会看到什么

如何使它崩溃

附加题