K & R 书中的 C 表

Question

K&R 的第 6.6 节讨论了使用链表的哈希表。

简而言之，哈希表是一个指针数组。指针指向链表。链接列表是一个看起来像这样的结构:

struct nlist {             /* table entry: */
    struct nlist *next;    /* next entry in chain */
    char *name;            /* defined name */
    char *defn;            /* replacement text */
};

名称经过哈希处理，这个哈希值决定了表中的索引。本章随后展示了向表中添加名称/定义对的代码:

struct nlist *install(char *name, char *defn) {
    struct nlist *np;
    unsigned hashval;
    if ((np = lookup(name)) == NULL) { /* not found */
        np = (struct nlist *) malloc(sizeof(*np));
        if (np == NULL || (np->name = strdup(name)) == NULL)
            return NULL;
        hashval = hash(name);
        np->next = hashtab[hashval];
        hashtab[hashval] = np;
    } else /* already there */
        free((void *) np->defn); /*free previous defn */
    if ((np->defn = strdup(defn)) == NULL)
        return NULL;
    return np;
}

除以下两行外，一切都有意义:

np->next = hashtab[hashval];
hashtab[hashval] = np;

我的问题是为什么他们不直接将它分配给 next 而不是插入它？即，

hashtab[hashval]->next = np; 
np->next = NULL;

执行插入技巧有什么好处？

Answer 1

在链式哈希中，您通常会在前面添加新元素，这就是为什么 np 始终位于哈希表中列表的头部。这是一种缓存局部性的使用，即最近访问的那个很可能会再次被访问。

此外，您的更改不会起作用，因为它只是将 np 添加到哈希列表的下一个元素，但 than 之后的所有元素都将丢失。