关于K&R《C程序设计语言》中哈希表实现的三项技术疑问

Hey there! These are really solid questions that get to the core of how classic hash table implementations work. Let's walk through each one step by step:

1. Why use a self-referential struct for the hash table? #

The next pointer isn't unnecessary—it's how the implementation handles hash collisions.

When you compute a hash value for a key, different keys might end up with the same hash (this is unavoidable with hash functions, especially when the number of possible keys is way larger than the 101 buckets in this table). To store multiple key-value pairs that hash to the same bucket, we use a linked list for each bucket.

The self-referential struct lets us chain together all entries that share the same hash index. For example, if two different name values hash to index 42, the first entry will be stored in hashtab[42], and the second entry's next pointer will point to the first one (or vice versa, depending on insertion order), creating a linked list at that bucket.

Here's the struct again for reference:

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

2. Why does the lookup loop use np = np->next? #

You're probably assuming that each hash index maps to exactly one entry—but that's not the case when collisions happen! This loop is designed to traverse the entire linked list at the target hash bucket.

Let's break down the loop logic:

• np = hashtab[hash(s)] starts at the head of the linked list in the bucket corresponding to s's hash.
• If the current np's name matches s, we return it immediately.
• If not, np = np->next moves us to the next entry in the chain.
• We keep going until np is NULL (meaning we've reached the end of the list and didn't find the key).

So this loop absolutely can run multiple times—whenever there are multiple entries hashed to the same bucket. If there's only one entry (or none), it runs once or zero times, but the logic accounts for collisions.

Here's the lookup function again:

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 */
}

3. What's the point of np->next = hashtab[hashval]; in install? #

This line isn't pointing the node to itself—it's part of a head insertion into the linked list. Let's break it down:

1. When we create a new nlist node for a key that doesn't exist yet, we first get the hash value hashval for the key.
2. np->next = hashtab[hashval]; sets the new node's next pointer to the current head of the linked list at hashtab[hashval] (which could be NULL if the bucket was empty).
3. Then hashtab[hashval] = np; updates the bucket's head to point to the new node.

This way, the new node becomes the first entry in the bucket's linked list, and the old list is attached to its next pointer. Head insertion is efficient because it doesn't require traversing the entire linked list to find the end—we just adjust two pointers.

For example:

• If hashtab[hashval] was pointing to A -> B -> NULL, after insertion, np->next points to A, and hashtab[hashval] points to np, making the list np -> A -> B -> NULL.

Here's the relevant snippet from install:

hashval = hash(name);
np->next = hashtab[hashval];
hashtab[hashval] = np;

内容的提问来源于stack exchange，提问作者Nazim