K&R C Programming Language Book 哈希表的有效性

Question

当我在 C 中搜索字典示例时，我遇到了 here Whosebug which references K&R The C Programming Language 书中的示例。在那本书中，第 6.6 节有一个 table 查找主题。该部分将 table 查找示例为散列 table.

散列table由示例中的101个大小nlist（以下代码片段中的结构）自引用节点组成。

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

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

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

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

K&R C Programming Language Book 哈希表的有效性

Validity of Hashtable From K&R C Progamming Language Book

c

lookup

hashtable