上一章，简单介绍了 Hash Table，并提出了本教程中要实现的几个 Hash Table 的方法，有 search(a, k)、insert(a, k, v)和 delete(a, k)，本章将介绍 Hash table 使用的数据结构。
Hash table 数据结构
hash 表中存储的每一项 key-value 的数据结构：
// hash_table.h
typedef struct {
char* key;
char* value;
} ht_item;
我们的 hash 表中保存着一个指向每一项的指针数组，里面还包括 hash 表的大小，结构如下：
// hash_table.h
typedef struct {
int size;
int count;
ht_item** items;
} ht_hash_table;
初始化与删除
在 hash 表中，我们需要定义一个函数来初始化一条记录 (ht_item)，这个函数会为每一条记录(ht_item) 申请内存，然后将 k 和 v 保存在这个内存中。为了让该函数只能在我们的 hash table 中使用，我们用 static 来修饰。
// hash_table.c
#include <stdlib.h>
#include <string.h>
#include “hash_table.h”
static ht_item* ht_new_item(const char* k, const char* v) {
ht_item* i = malloc(sizeof(ht_item));
i->key = strdup(k); // 复制操作
i->value = strdup(v);
return i;
}
ht_new 初始化一个新的 hash 表，size 表示这个 hash 表可以存储多少条记录，现在是固定的 53 条。我们将在后面讲解如何扩充这个 hash 表，我们使用 calloc 函数来初始化一条记录（如果对 calloc 不熟悉，可以看看我这篇文章:https://www.jianshu.com/p/dd3…），calloc 会申请一片空间并用 NULL 来填充，记录为 NULL 就代表空的。
// hash_table.c
ht_hash_table* ht_new() {
ht_hash_table* ht = malloc(sizeof(ht_hash_table));
ht->size = 53;
ht->count = 0;
ht->items = calloc((size_t)ht->size, sizeof(ht_item*));
return ht;
}
我们还需要额外的函数来删除 ht_item 和 ht_hash_table，这个函数会释放 (free) 我们之前申请的内存空间，以至于不会造成内存泄漏：
// hash_table.c
static void ht_del_item(ht_item* i) {
free(i->key);
free(I->value);
free(i);
}
void ht_delete_hash_table(ht_hash_table* ht) {
for (int i = 0; i < ht->size; ++i) {
ht_item* item = ht_items[I];
if (item != NULL) {
ht_del_item(item);
}
}
free(ht->items);
free(ht);
}
现在，我们已经完成定义一个 hash 表，现在我们可以试着创建一个 hash 表并试着销毁它，尽管现在并没有做太多东西。
// main.c
#include hash_table.h
int main() {
ht_hash_table* ht = ht_new();
ht_del_hash_table(ht);
}
上一章：hash 表介绍下一章：hash 函数