练习37：哈希表

哈希表（、HashTable以及Dictionary）广泛用于许多动态编程语言来储存键值对的数据。哈希表通过在键上执行“哈希”运算产生整数，之后使用它来寻找相应的桶来获取或储存值。它是非常快速的使用数据结构，因为它适用于任何数据并且易于实现。

下面是哈希表（也叫作字典）的一个使用示例：

几乎所有现代语言都具备这种特性，所以许多人写完代码都不知道它实际上如何工作。通过在C中创建Hashmap数据结构，我会向你展示它的工作原理。我会从头文件开始，来谈论整个数据结构。

这个结构就是Hashmap，含有许多HashmapNode节点。观察Hashmap你会看到它类似这样：

DArray *buckets

一个动态数组，设置为100个桶的固定大小。每个桶会含有一个DArray，来实际存档HashmapNode对。

Hashmap_compare compare

这是一个比较函数，被Hashmap用于实际用过键寻找元素。它应该和其它的比较函数类似，并且默认设置为bstrcmp来比较字符串。

这是哈希函数，它用于接收键，处理它的内容，之后产生一个uint32_t索引数值。之后你会看到默认的实现。

这些告诉了你数据如何存储，但是用作buckets的DArray还没有创建。要记住它具有二层结构；

由下面三个元素组成：

void *key

键值对的键。

void *value

键值对的值。

uint32_t hash

计算出的哈希值，它用于使查找该节点更加迅速，只要判断键是否相等。

这个实现中并没有什么复杂的东西，但是default_hash和Hashmap_find_bucket需要一些解释。当你使用Hashmap_create时，你可以传入任何定制的比较和哈希函数。但是如果你没有则会使用default_compare和default_hash函数。

需要观察的第一件事，是default_hash的行为。这是一个简单的哈希函数，叫做“Jenkins hash”，以Bob Jenkins的名字命名。我从上获得了这个算法。它仅仅遍历键（bstring）的每个字节来计算哈希，以便得出uint32_t的结果。它使用一些加法和异或运算来实现。

哈希函数有很多中，它们具有不同的特性，然而一旦你选择了一种，就需要一种方法来使用它找到正确的桶。Hashmap_find_bucket像这样实现它：

其它函数都使用Hashmap_find_bucket来完成工作：

你需要学习的唯一一个其他函数是Hashmap_travers，它仅仅遍历每个桶，对于任何含有值的桶，在每个值上调用traverse_cb。这就是扫描整个Hashmap的办法。

最后你需要编写单元测试，对于所有这些操作：

需要学习的唯一一件事情就是我在单元测试的顶端使用了bstring的特性来创建静态字符串用于测试。我使用tagbstring和bsStatic在7~13行创建他们。

这是一个非常简单的Hashmap实现，就像书中的大多数其他数据结构那样。我的目标不是让你以非常快的速度来掌握数据结构。通常这些讨论起来非常复杂，并且会让你偏离真正的基础和实用的数据结构。我的目标是提供一个易于理解的起始点，然后再改进或理解它们如何实现。

对于这和练习，下面是你能够用于改进这个实现的方法：

你可以对每个桶进行排序，使它们有序。这会增加你的插入时间，但是减少寻找时间，因为你可以使用二分搜索来寻找每个节点。到现在为止它遍历桶中的所有节点来寻找元素。
你可以使用更好的default_hash函数，有许多这样的函数。
这个实现以及几乎所有实现都有将一些特定的键存到一个桶中的风险。这会使你的程序运行速度变慢，因为它使Hashmap的处理过程变成了处理单个的DArray。如果你对桶中的数组排序会有帮助，但是你可以仅仅使用更好的哈希函数来避免，并且对于真正的偏执狂，你可以添加一个随机的盐，让键不可预测。
你可以删掉不歪有任何节点的桶来节约空间，或者将空的桶当如缓存中，便于节约创建和销毁它们的开销。
现在为止它可以添加已存在的元素，编写一个替代的实现，使它只能够添加不存在的元素。