K&RC 编程语言书籍中哈希表的有效性

Question

当我在 C 语言中搜索字典示例时，我遇到了 here stackoverflow 中的示例，其中引用了 K&R C 编程语言一书。在那本书中，第 6.6 节中有一个表查找主题。本节将表查找示例为哈希表。

在示例中，哈希表由 101 个大小的 nlist（以下代码片段中的结构）自引用节点组成。

我的问题是为什么他们使用自引用结构作为查找表？查找表作为键值对工作，因此我们不必保存下一个节点。

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

与该示例相关的问题的第二部分是针对 lookup(char *s) 函数中的循环语句。该循环仅工作一次，并且 np = np->next 表达式可能不相关，我认为或者可能有我错过的任何内容！

struct nlist *lookup(char *s)
{
    struct nlist *np;
    for (np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
          return np; /* found */
    return NULL; /* not found */
}

我问题的最后一部分是关于函数 *install(char *name, char *defn) 中的赋值 np->next = hashtab[hashval]; （下面的函数），实际上它将当前节点分配给自己作为下一个节点。

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;
}

提前致谢。

Answer 1

该表不是直接使用键进行索引，而是使用键的散列进行索引。不同的密钥可能具有相同的哈希值。这称为哈希冲突。

1. 此实现将与具有相同哈希的键相对应的所有值存储为链表，因此是一个自引用结构。该表存储键值对的链表。同一列表中的所有键都具有相同的哈希值。 （这不是处理碰撞的唯一方法）。
2. 如果发生碰撞，循环会多次工作。如果您没有看到此循环执行多次，请继续添加条目，直到发生碰撞。
3. 不，它不会为自己分配节点。它将新分配的节点插入链表的头部。列表的前一个头成为列表中的第二个节点。