当我在 C 语言中搜索字典示例时,我遇到了 here stackoverflow 中的示例。其中引用了 K&R The C Programming Language书。在那本书中,第 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 *)中的赋值
,实际上它将当前节点分配给自己作为下一个节点。np->next = hashtab[hashval];
(下面的函数) defn)
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;
}
提前致谢。
最佳答案
该表不是直接使用键进行索引,而是使用键的散列进行索引。不同的 key 可能具有相同的哈希值。这称为哈希冲突。
- 此实现将与具有相同哈希值的键对应的所有值存储为链表,因此是一个自引用结构。该表存储键值对的链表。同一列表中的所有键都具有相同的哈希值。 (这不是处理冲突的唯一方法)。
- 如果发生冲突,循环会多次工作。如果您没有看到此循环执行多次,请继续添加条目,直到发生冲突。
- 不,它不会为自己分配节点。它将新分配的节点插入链表的头部。列表的前一个头成为列表中的第二个节点。
关于c - K&R C 编程语言书籍中哈希表的有效性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/71537899/