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

Question

在用C编写程序时，我想念的一件事就是字典数据结构。用C实现一个最方便的方法是什么？我不是在寻找性能，而是希望从头开始编写它。我也不希望它是通用的-像string-> int这样的东西。但是我确实希望它能够存储任意数量的项目。这更多地是作为练习。我知道有一个第三方库可供使用。但是请考虑一下，它们不存在。在这种情况下，实现满足以上要求的字典的最快方法是什么。

Answer 1

为了易于实现，很难天真地搜索数组。除了一些错误检查之外，这是一个完整的实现（未经测试）。

typedef struct dict_entry_s {

    const char *key;

    int value;

} dict_entry_s;

typedef struct dict_s {

    int len;

    int cap;

    dict_entry_s *entry;

} dict_s, *dict_t;

int dict_find_index(dict_t dict, const char *key) {

    for (int i = 0; i < dict->len; i++) {

        if (!strcmp(dict->entry[i], key)) {

            return i;

        }

    }

    return -1;

}

int dict_find(dict_t dict, const char *key, int def) {

    int idx = dict_find_index(dict, key);

    return idx == -1 ? def : dict->entry[idx].value;

}

void dict_add(dict_t dict, const char *key, int value) {

   int idx = dict_find_index(dict, key);

   if (idx != -1) {

       dict->entry[idx].value = value;

       return;

   }

   if (dict->len == dict->cap) {

       dict->cap *= 2;

       dict->entry = realloc(dict->entry, dict->cap * sizeof(dict_entry_s));

   }

   dict->entry[dict->len].key = strdup(key);

   dict->entry[dict->len].value = value;

   dict->len++;

}

dict_t dict_new(void) {

    dict_s proto = {0, 10, malloc(10 * sizeof(dict_entry_s))};

    dict_t d = malloc(sizeof(dict_s));

    *d = proto;

    return d;

}

void dict_free(dict_t dict) {

    for (int i = 0; i < dict->len; i++) {

        free(dict->entry[i].key);

    }

    free(dict->entry);

    free(dict);

}