# 练习37：哈希表
> 原文：[Exercise 37: Hashmaps](http://c.learncodethehardway.org/book/ex37.html)
> 译者：[飞龙](https://github.com/wizardforcel)
哈希表（`HashMap`、`HashTable`以及`Dictionary`）广泛用于许多动态编程语言来储存键值对的数据。哈希表通过在键上执行“哈希”运算产生整数，之后使用它来寻找相应的桶来获取或储存值。它是非常快速的使用数据结构，因为它适用于任何数据并且易于实现。
下面是哈希表（也叫作字典）的一个使用示例：
```c
fruit_weights = {'Apples': 10, 'Oranges': 100, 'Grapes': 1.0}
for key, value in fruit_weights.items():
print key, "=", value
```
几乎所有现代语言都具备这种特性，所以许多人写完代码都不知道它实际上如何工作。通过在C中创建`Hashmap`数据结构，我会向你展示它的工作原理。我会从头文件开始，来谈论整个数据结构。
```c
#ifndef _lcthw_Hashmap_h
#define _lcthw_Hashmap_h
#include <stdint.h>
#include <lcthw/darray.h>
#define DEFAULT_NUMBER_OF_BUCKETS 100
typedef int (*Hashmap_compare)(void *a, void *b);
typedef uint32_t (*Hashmap_hash)(void *key);
typedef struct Hashmap {
DArray *buckets;
Hashmap_compare compare;
Hashmap_hash hash;
} Hashmap;
typedef struct HashmapNode {
void *key;
void *data;
uint32_t hash;
} HashmapNode;
typedef int (*Hashmap_traverse_cb)(HashmapNode *node);
Hashmap *Hashmap_create(Hashmap_compare compare, Hashmap_hash);
void Hashmap_destroy(Hashmap *map);
int Hashmap_set(Hashmap *map, void *key, void *data);
void *Hashmap_get(Hashmap *map, void *key);
int Hashmap_traverse(Hashmap *map, Hashmap_traverse_cb traverse_cb);
void *Hashmap_delete(Hashmap *map, void *key);
#endif
```
这个结构就是`Hashmap`，含有许多`HashmapNode`节点。观察`Hashmap`你会看到它类似这样：
`DArray *buckets`
一个动态数组，设置为100个桶的固定大小。每个桶会含有一个`DArray`，来实际存档`HashmapNode`对。
`Hashmap_compare compare`
这是一个比较函数，被`Hashmap`用于实际用过键寻找元素。它应该和其它的比较函数类似，并且默认设置为`bstrcmp`来比较字符串。
`Hashmap_hash`
这是哈希函数，它用于接收键，处理它的内容，之后产生一个`uint32_t`索引数值。之后你会看到默认的实现。
这些告诉了你数据如何存储，但是用作`buckets`的`DArray`还没有创建。要记住它具有二层结构；
+ 第一层有100个桶，数据基于它们的哈希值储存在桶中。
+ 每个桶都是一个`DArray`，其中含有`HashmapNode`，添加时只是简单地附加到末尾。
`HashMapNode`由下面三个元素组成：
`void *key`
键值对的键。
`void *value`
键值对的值。
`uint32_t hash`
计算出的哈希值，它用于使查找该节点更加迅速，只要判断键是否相等。
有文件的剩余部分没有新的东西，所以我现在可以向你展示`hashmap.c`的实现了：
```c
#undef NDEBUG
#include <stdint.h>
#include <lcthw/hashmap.h>
#include <lcthw/dbg.h>
#include <lcthw/bstrlib.h>
static int default_compare(void *a, void *b)
{
return bstrcmp((bstring)a, (bstring)b);
}
/**
* Simple Bob Jenkins's hash algorithm taken from the
* wikipedia description.
*/
static uint32_t default_hash(void *a)
{
size_t len = blength((bstring)a);
char *key = bdata((bstring)a);
uint32_t hash = 0;
uint32_t i = 0;
for(hash = i = 0; i < len; ++i)
{
hash += key[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
Hashmap *Hashmap_create(Hashmap_compare compare, Hashmap_hash hash)
{
Hashmap *map = calloc(1, sizeof(Hashmap));
check_mem(map);
map->compare = compare == NULL ? default_compare : compare;
map->hash = hash == NULL ? default_hash : hash;
map->buckets = DArray_create(sizeof(DArray *), DEFAULT_NUMBER_OF_BUCKETS);
map->buckets->end = map->buckets->max; // fake out expanding it
check_mem(map->buckets);
return map;
error:
if(map) {
Hashmap_destroy(map);
}
return NULL;
}
void Hashmap_destroy(Hashmap *map)
{
int i = 0;
int j = 0;
if(map) {
if(map->buckets) {
for(i = 0; i < DArray_count(map->buckets); i++) {
DArray *bucket = DArray_get(map->buckets, i);
if(bucket) {
for(j = 0; j < DArray_count(bucket); j++) {
free(DArray_get(bucket, j));
}
DArray_destroy(bucket);
}
}
DArray_destroy(map->buckets);
}
free(map);
}
}
static inline HashmapNode *Hashmap_node_create(int hash, void *key, void *data)
{
HashmapNode *node = calloc(1, sizeof(HashmapNode));
check_mem(node);
node->key = key;
node->data = data;
node->hash = hash;
return node;
error:
return NULL;
}
static inline DArray *Hashmap_find_bucket(Hashmap *map, void *key,
int create, uint32_t *hash_out)
{
uint32_t hash = map->hash(key);
int bucket_n = hash % DEFAULT_NUMBER_OF_BUCKETS;
check(bucket_n >= 0, "Invalid bucket found: %d", bucket_n);
*hash_out = hash; // store it for the return so the caller can use it
DArray *bucket = DArray_get(map->buckets, bucket_n);
if(!bucket && create) {
// new bucket, set it up
bucket = DArray_create(sizeof(void *), DEFAULT_NUMBER_OF_BUCKETS);
check_mem(bucket);
DArray_set(map->buckets, bucket_n, bucket);
}
return bucket;
error:
return NULL;
}
int Hashmap_set(Hashmap *map, void *key, void *data)
{
uint32_t hash = 0;
DArray *bucket = Hashmap_find_bucket(map, key, 1, &hash);
check(bucket, "Error can't create bucket.");
HashmapNode *node = Hashmap_node_create(hash, key, data);
check_mem(node);
DArray_push(bucket, node);
return 0;
error:
return -1;
}
static inline int Hashmap_get_node(Hashmap *map, uint32_t hash, DArray *bucket, void *key)
{
int i = 0;
for(i = 0; i < DArray_end(bucket); i++) {
debug("TRY: %d", i);
HashmapNode *node = DArray_get(bucket, i);
if(node->hash == hash && map->compare(node->key, key) == 0) {
return i;
}
}
return -1;
}
void *Hashmap_get(Hashmap *map, void *key)
{
uint32_t hash = 0;
DArray *bucket = Hashmap_find_bucket(map, key, 0, &hash);
if(!bucket) return NULL;
int i = Hashmap_get_node(map, hash, bucket, key);
if(i == -1) return NULL;
HashmapNode *node = DArray_get(bucket, i);
check(node != NULL, "Failed to get node from bucket when it should exist.");
return node->data;
error: // fallthrough
return NULL;
}
int Hashmap_traverse(Hashmap *map, Hashmap_traverse_cb traverse_cb)
{
int i = 0;
int j = 0;
int rc = 0;
for(i = 0; i < DArray_count(map->buckets); i++) {
DArray *bucket = DArray_get(map->buckets, i);
if(bucket) {
for(j = 0; j < DArray_count(bucket); j++) {
HashmapNode *node = DArray_get(bucket, j);
rc = traverse_cb(node);
if(rc != 0) return rc;
}
}
}
return 0;
}
void *Hashmap_delete(Hashmap *map, void *key)
{
uint32_t hash = 0;
DArray *bucket = Hashmap_find_bucket(map, key, 0, &hash);
if(!bucket) return NULL;
int i = Hashmap_get_node(map, hash, bucket, key);
if(i == -1) return NULL;
HashmapNode *node = DArray_get(bucket, i);
void *data = node->data;
free(node);
HashmapNode *ending = DArray_pop(bucket);
if(ending != node) {
// alright looks like it's not the last one, swap it
DArray_set(bucket, i, ending);
}
return data;
}
```
这个实现中并没有什么复杂的东西，但是`default_hash`和`Hashmap_find_bucket`需要一些解释。当你使用`Hashmap_create`时，你可以传入任何定制的比较和哈希函数。但是如果你没有则会使用`default_compare`和`default_hash`函数。
需要观察的第一件事，是`default_hash`的行为。这是一个简单的哈希函数，叫做“Jenkins hash”，以Bob Jenkins的名字命名。我从[维基百科](http://en.wikipedia.org/wiki/Jenkins_hash_function)上获得了这个算法。它仅仅遍历键（`bstring`）的每个字节来计算哈希，以便得出`uint32_t`的结果。它使用一些加法和异或运算来实现。
哈希函数有很多中，它们具有不同的特性，然而一旦你选择了一种，就需要一种方法来使用它找到正确的桶。`Hashmap_find_bucket`像这样实现它：
+ 首先调用` map->hash(key)`来获得键的哈希值。
+ 之后使用`hash % DEFAULT_NUMBER_OF_BUCKETS`，这样无论哈希值有多大，都能找到匹配的桶。
+ 找到桶之后，它是个`DArray`，可能还没有创建，这取决与`create`变量的内容。
+ 一旦找到了正确的`DArray`桶，就会将它返回，并且`hash_out`变量用于向调用者提供所找到的哈希值。
其它函数都使用`Hashmap_find_bucket`来完成工作：
+ 设置键值对涉及到找到正确的桶，之后创建`HashmapNode`，将它添加到桶中。
+ 获取键值涉及到找到正确的桶，之后找到匹配`hash`和`key`的`HashmapNode`。
+ 删除元素也需要找到正确的桶，找到所需的节点，之后通过与末尾的节点交换位置来删除。
你需要学习的唯一一个其他函数是`Hashmap_travers`，它仅仅遍历每个桶，对于任何含有值的桶，在每个值上调用`traverse_cb`。这就是扫描整个`Hashmap`的办法。
## 单元测试
最后你需要编写单元测试，对于所有这些操作：
```c
#include "minunit.h"
#include <lcthw/hashmap.h>
#include <assert.h>
#include <lcthw/bstrlib.h>
Hashmap *map = NULL;
static int traverse_called = 0;
struct tagbstring test1 = bsStatic("test data 1");
struct tagbstring test2 = bsStatic("test data 2");
struct tagbstring test3 = bsStatic("xest data 3");
struct tagbstring expect1 = bsStatic("THE VALUE 1");
struct tagbstring expect2 = bsStatic("THE VALUE 2");
struct tagbstring expect3 = bsStatic("THE VALUE 3");
static int traverse_good_cb(HashmapNode *node)
{
debug("KEY: %s", bdata((bstring)node->key));
traverse_called++;
return 0;
}
static int traverse_fail_cb(HashmapNode *node)
{
debug("KEY: %s", bdata((bstring)node->key));
traverse_called++;
if(traverse_called == 2) {
return 1;
} else {
return 0;
}
}
char *test_create()
{
map = Hashmap_create(NULL, NULL);
mu_assert(map != NULL, "Failed to create map.");
return NULL;
}
char *test_destroy()
{
Hashmap_destroy(map);
return NULL;
}
char *test_get_set()
{
int rc = Hashmap_set(map, &test1, &expect1);
mu_assert(rc == 0, "Failed to set &test1");
bstring result = Hashmap_get(map, &test1);
mu_assert(result == &expect1, "Wrong value for test1.");
rc = Hashmap_set(map, &test2, &expect2);
mu_assert(rc == 0, "Failed to set test2");
result = Hashmap_get(map, &test2);
mu_assert(result == &expect2, "Wrong value for test2.");
rc = Hashmap_set(map, &test3, &expect3);
mu_assert(rc == 0, "Failed to set test3");
result = Hashmap_get(map, &test3);
mu_assert(result == &expect3, "Wrong value for test3.");
return NULL;
}
char *test_traverse()
{
int rc = Hashmap_traverse(map, traverse_good_cb);
mu_assert(rc == 0, "Failed to traverse.");
mu_assert(traverse_called == 3, "Wrong count traverse.");
traverse_called = 0;
rc = Hashmap_traverse(map, traverse_fail_cb);
mu_assert(rc == 1, "Failed to traverse.");
mu_assert(traverse_called == 2, "Wrong count traverse for fail.");
return NULL;
}
char *test_delete()
{
bstring deleted = (bstring)Hashmap_delete(map, &test1);
mu_assert(deleted != NULL, "Got NULL on delete.");
mu_assert(deleted == &expect1, "Should get test1");
bstring result = Hashmap_get(map, &test1);
mu_assert(result == NULL, "Should delete.");
deleted = (bstring)Hashmap_delete(map, &test2);
mu_assert(deleted != NULL, "Got NULL on delete.");
mu_assert(deleted == &expect2, "Should get test2");
result = Hashmap_get(map, &test2);
mu_assert(result == NULL, "Should delete.");
deleted = (bstring)Hashmap_delete(map, &test3);
mu_assert(deleted != NULL, "Got NULL on delete.");
mu_assert(deleted == &expect3, "Should get test3");
result = Hashmap_get(map, &test3);
mu_assert(result == NULL, "Should delete.");
return NULL;
}
char *all_tests()
{
mu_suite_start();
mu_run_test(test_create);
mu_run_test(test_get_set);
mu_run_test(test_traverse);
mu_run_test(test_delete);
mu_run_test(test_destroy);
return NULL;
}
RUN_TESTS(all_tests);
```
需要学习的唯一一件事情就是我在单元测试的顶端使用了`bstring`的特性来创建静态字符串用于测试。我使用`tagbstring`和`bsStatic`在7~13行创建他们。
## 如何改进
这是一个非常简单的`Hashmap`实现，就像书中的大多数其他数据结构那样。我的目标不是让你以非常快的速度来掌握数据结构。通常这些讨论起来非常复杂，并且会让你偏离真正的基础和实用的数据结构。我的目标是提供一个易于理解的起始点，然后再改进或理解它们如何实现。
对于这和练习，下面是你能够用于改进这个实现的方法：
+ 你可以对每个桶进行排序，使它们有序。这会增加你的插入时间，但是减少寻找时间，因为你可以使用二分搜索来寻找每个节点。到现在为止它遍历桶中的所有节点来寻找元素。
+ 你可以动态设定桶的数量，或者让调用者指定每个`Hashmap`中的该值。
+ 你可以使用更好的`default_hash`函数，有许多这样的函数。
+ 这个实现以及几乎所有实现都有将一些特定的键存到一个桶中的风险。这会使你的程序运行速度变慢，因为它使`Hashmap`的处理过程变成了处理单个的`DArray`。如果你对桶中的数组排序会有帮助，但是你可以仅仅使用更好的哈希函数来避免，并且对于真正的偏执狂，你可以添加一个随机的盐，让键不可预测。
+ 你可以删掉不歪有任何节点的桶来节约空间，或者将空的桶当如缓存中，便于节约创建和销毁它们的开销。
+ 现在为止它可以添加已存在的元素，编写一个替代的实现，使它只能够添加不存在的元素。
像往常一样，你需要浏览每个函数，并且使之健壮。`Hashmap`也可以使用一些调试设置，来执行不变量检查。
## 附加题
+ 研究你最喜欢的编程语言的`Hashmap`实现，了解它们具有什么特性。
+ 找到`Hashmap`的主要缺点，以及如何避免它们。例如，它们不做特定的修改就不能保存顺序，并且当你基于键的一部分来查找元素时，它们就不能生效。
+ 编写单元测试来展示将键都填充到`Hashmap`的一个桶中所带来的缺陷，之后测试这样如何影响性能。一个实现它的好方法，就是把桶的数量减少到一个愚蠢的数值，比如1。
- 笨办法学C 中文版
- 前言
- 导言：C的笛卡尔之梦
- 练习0：准备
- 练习1：启用编译器
- 练习2：用Make来代替Python
- 练习3：格式化输出
- 练习4：Valgrind 介绍
- 练习5：一个C程序的结构
- 练习6：变量类型
- 练习7：更多变量和一些算术
- 练习8：大小和数组
- 练习9：数组和字符串
- 练习10：字符串数组和循环
- 练习11：While循环和布尔表达式
- 练习12：If，Else If，Else
- 练习13：Switch语句
- 练习14：编写并使用函数
- 练习15：指针，可怕的指针
- 练习16：结构体和指向它们的指针
- 练习17：堆和栈的内存分配
- 练习18：函数指针
- 练习19：一个简单的对象系统
- 练习20：Zed的强大的调试宏
- 练习21：高级数据类型和控制结构
- 练习22：栈、作用域和全局
- 练习23：认识达夫设备
- 练习24：输入输出和文件
- 练习25：变参函数
- 练习26：编写第一个真正的程序
- 练习27：创造性和防御性编程
- 练习28：Makefile 进阶
- 练习29：库和链接
- 练习30：自动化测试
- 练习31：代码调试
- 练习32：双向链表
- 练习33：链表算法
- 练习34：动态数组
- 练习35：排序和搜索
- 练习36：更安全的字符串
- 练习37：哈希表
- 练习38：哈希算法
- 练习39：字符串算法
- 练习40：二叉搜索树
- 练习41：将 Cachegrind 和 Callgrind 用于性能调优
- 练习42：栈和队列
- 练习43：一个简单的统计引擎
- 练习44：环形缓冲区
- 练习45：一个简单的TCP/IP客户端
- 练习46：三叉搜索树
- 练习47：一个快速的URL路由
- 后记：“解构 K&R C” 已死