在C中实现字典的快速方法

Question

在用C编写程序时，我想念的一件事就是字典数据结构。用C实现一个最方便的方法是什么？我不是在寻找性能，而是希望从头开始编写它。我也不希望它是通用的-像string-> int这样的东西。但是我确实希望它能够存储任意数量的项目。

这更多地是作为练习。我知道有一个第三方库可供使用。但是请考虑一下，它们不存在。在这种情况下，实现满足以上要求的字典的最快方法是什么。

Answer 1

为了易于实现，很难天真地搜索数组。除了一些错误检查之外，这是一个完整的实现（未经测试）。typedef struct dict_entry_s {&nbsp; &nbsp; const char *key;&nbsp; &nbsp; int value;} dict_entry_s;typedef struct dict_s {&nbsp; &nbsp; int len;&nbsp; &nbsp; int cap;&nbsp; &nbsp; dict_entry_s *entry;} dict_s, *dict_t;int dict_find_index(dict_t dict, const char *key) {&nbsp; &nbsp; for (int i = 0; i < dict->len; i++) {&nbsp; &nbsp; &nbsp; &nbsp; if (!strcmp(dict->entry[i], key)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return i;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return -1;}int dict_find(dict_t dict, const char *key, int def) {&nbsp; &nbsp; int idx = dict_find_index(dict, key);&nbsp; &nbsp; return idx == -1 ? def : dict->entry[idx].value;}void dict_add(dict_t dict, const char *key, int value) {&nbsp; &nbsp;int idx = dict_find_index(dict, key);&nbsp; &nbsp;if (idx != -1) {&nbsp; &nbsp; &nbsp; &nbsp;dict->entry[idx].value = value;&nbsp; &nbsp; &nbsp; &nbsp;return;&nbsp; &nbsp;}&nbsp; &nbsp;if (dict->len == dict->cap) {&nbsp; &nbsp; &nbsp; &nbsp;dict->cap *= 2;&nbsp; &nbsp; &nbsp; &nbsp;dict->entry = realloc(dict->entry, dict->cap * sizeof(dict_entry_s));&nbsp; &nbsp;}&nbsp; &nbsp;dict->entry[dict->len].key = strdup(key);&nbsp; &nbsp;dict->entry[dict->len].value = value;&nbsp; &nbsp;dict->len++;}dict_t dict_new(void) {&nbsp; &nbsp; dict_s proto = {0, 10, malloc(10 * sizeof(dict_entry_s))};&nbsp; &nbsp; dict_t d = malloc(sizeof(dict_s));&nbsp; &nbsp; *d = proto;&nbsp; &nbsp; return d;}void dict_free(dict_t dict) {&nbsp; &nbsp; for (int i = 0; i < dict->len; i++) {&nbsp; &nbsp; &nbsp; &nbsp; free(dict->entry[i].key);&nbsp; &nbsp; }&nbsp; &nbsp; free(dict->entry);&nbsp; &nbsp; free(dict);}