CODEWITHSUNDEEP
ckernighan-and-ritchie
Bar K
Bar K

Reputation: 89

I don't understand the hash tables example in K&R

here is the install function from the hash tables example from K&R's book:

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

I don't understand the line np->next = hashtab[hasvall] I thought the reason to have the variable np->next is for putting in the table two string with the same hash value, but the outcome from this is having only one name for every hash value.

Furthermore I cannot seem to understand the function lookup, and the "AFTERTHOUGHT part in the for(because I think there is only one vaule to every struct in the talbe:

/* lookup: look for s in hashtab */
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 */
}

What am I missing?

Upvotes: 5

Views: 1003

Answers (2)

csteel
csteel

Reputation: 468

You can have only one key (name) for every value, but two or more keys can have the same hash. np->next = hashtab[hashval] adds the new hashval to the linked list. Lookup then iterates through the list until the key (name) is matched.

Upvotes: 3

AShelly
AShelly

Reputation: 35540

    np->next = hashtab[hashval]; 
    hashtab[hashval] = np;

These two lines do not replace the old entry, they add to it.

hashtab[hashval]-> existing_node becomes
hashtab[hashval]-> np -(next)-> existing_node

As @Bo Persson mentions in the comments, this is called "chaining".

Given this structure, the lookup function correctly checks the names of each node in the chain.

Upvotes: 2

Related Questions