As I am searching dictionary example in C, I have come accross the example in here stackoverflow which references K&R The C Programming Language book. In that book, there is a table lookup topic in section 6.6. The section exemplifies table lookup as a hash table.

The hashtable is formed by 101 sized nlist(the struct in the below code snippet) self-referential nodes in the example.

My question is here why they have used self-referential struct for a lookup table? Look-up tables work as key-value pair so we dont have to hold next node.

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

The second part of my question related with the example is for the loop statement in the lookup(char *s) function. The loop works only for one time and also np = np->next expression may irrelevant, i think or there could be anything that i missed!

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

The last part of my question is about the assignment np->next = hashtab[hashval]; (the function below) in the function *install(char *name, char *defn), actually it assignes its current node to itself as a next node.

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

Thanks in advance.

CodePudding user response：

The table is not indexed with keys directly, but with hashes of keys. Different keys may have the same hash. This is called hash collisions.

1. This implementation stores all values that correspond to keys with the same hash as a linked list, thus a self referential structure. The table stores linked lists of key-value pairs. All keys in the same list have the same hash. (This is not the only method of handling collisions).
2. In case of a collision, the loop does work more than once. It you don't see this loop executing more than once, keep adding entries until you hit a collision.
3. No, it does not assign a node to itself. It inserts a newly allocated node at the head of the linked list. The former head of the list becomes the second node in the list.