k&r 的表查找安装功能
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;
当我尝试理解这一点时,我不断得出结论,列表现在链接回自身,如果您尝试遍历链表就会像狗追自己的尾巴一样。我希望代码将 np->next 设置为 NULL。
我不明白什么?这段代码怎么起作用?
Section 6.6 of K&R discusses a hash table using a linked list.
In short, a hash table is an array of pointers. The pointers point to a linked list. The linked list is a struct that looks like:
struct nlist { /* table entry: */
struct nlist *next; /* next entry in chain */
char *name; /* defined name */
char *defn; /* replacement text */
};
The name is hashed, and this hash determines the index in the table. The chapter then shows code to add a name/defn pair to the table:
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;
}
Everything makes sense except for the following 2 lines:
np->next = hashtab[hashval];
hashtab[hashval] = np;
When I try to understand this, I keep coming to the conclusion that the list now links back to itself and if you try to traverse the linked list it will be like a dog chasing its own tail. I would expect the code to set np->next to NULL.
What am I not understanding? How come this code works ?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
![扫码二维码加入Web技术交流群](/public/img/jiaqun_03.jpg)
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(5)
它会导致新值插入到列表的开头。
所以它从:
到:
到:
黄金法则是,如果链表代码没有意义,总是画出一个图表!
It results in the new value being inserted at the beginning of the list.
So it goes from:
to:
to:
The golden rule is, if linked-list code doesn't make sense, always draw out a diagram!
hashtab[hashval] 是一个指针,而不是一个值。
它是指向内存中地址的指针,指针表中该特定行的第一个元素所在的位置
(static struct nlist *hashtab[HASHSIZE]) 驻留。
np 和 np->next 也是指针。
所以这两行中发生的事情如下:
第一行:表中该行第一个元素的指针被复制到 np->next 中。 np->next 现在指向内存中该行的第一个元素曾经指向的地址。
第二行:指向新 *np 所在内存地址的指针现在被复制到指针中
变量 hastab[hashval]。 hastab[hashval] 现在再次成为指向该表行的第一个元素所在位置的指针。
因此,正如 Oli 所写,新的 *np 被插入到表中该特定行的开头。
hashtab[hashval] is a pointer, not a value.
It is a pointer to the address in memory where the first element of that particular row in the pointer table
(static struct nlist *hashtab[HASHSIZE]) resides.
np and np->next are also pointers.
So here is what happens in these two lines:
First line: The pointer of the first element in that row of the table is copied into np->next. np->next now points at the address in memory where the first element of that row used to point.
Second line: The pointer to the address in memory where the new *np resides is now copied into the pointer
variable hastab[hashval]. hastab[hashval] now once again becomes the pointer to where the first element of that table row resides.
So, just as Oli wrote, the new *np is inserted at the beginning of that particular row in the table.
那里已经有一个节点了。该节点为空。通过将 nlist 结构定义为静态,它会自动将其所有元素指针初始化为 NULL。
如果我错了请纠正我。
There is already a node there. That node is null. By defining the nlist struct as static, it is automatically initiates all its element pointers to NULL.
Correct me if I'm wrong.
但这里没有原始列表。它正在插入一个没有找到键的节点,对吧?
But there is no original list here. It is inserting a node where no key is found, right?
其实它很简单
考虑两个字符串“IN”和“Hm”。这两个具有相同的哈希值,因此哈希函数在这两种情况下都返回 18。
因此,当一个新的字符串或数据具有相同的哈希值时,就会出现一个链表。具有相同哈希值的新节点将附加到列表的开头
并且它的下一个链接包含前一个节点...
为了让事情变得更漂亮,尝试这个代码...
Actually its really simple
consider two strings "IN" and "Hm" . these two have the same hash value and hence the hashing function returns 18 in both the cases .
so when a new string or data comes with the same hash , then a linked list comes into existence . the new node with the same hash is attached to the beginning of the list
and its next link contains the previous node ...
AND TO MAKE THINGS MORE BEAUTIFUL TRY THIS CODE OUT ...