My reference is to section 6.6 in K&R (Second Edition), which presents an example of Table Lookup. I could not understand the code properly, and would be grateful if any of the members could help.
I assume that almost all the members should have access to the book. Hence I am not reproducing the entire code here; only those chunks that are relevant.
My first doubt is w.r.t to the struct nlist *install(char *name, char *def) routine. The code that I could not understand in the install routine is given below:
hashval = hash(name);/*this will store the value returned by hash routine in hashval */
np->next = hashtab[hashval];/* this will store the pointer in hashtab array at position hashval into np->next*/
Now, how is it assured that hashval is less than or equal to 100, since the size of the array is equal to 101?
hashtab[hashval] = np; /*this will store the pointer in np at position hashval in the hashtab array */
As far as I can understand, when install records a new element into hashtab, it does so before another already existing element, as evinced by the code above. Why?
My second doubt is w.r.t the struct nlist *lookup(char *s) routine. The loop in this routine begins at hashtab[hash(s)] position in the array, and checks for s until null is encountered.
K&R says "The hashing process produces a starting index in the array hashtab; if the string is to be found anywhere, it will be in the list of blocks beginning there."
Could anyone explain this algorithm to me?
My third doubt is w.r.t unsigned hash (char *s) routine. K&R says that "Unsigned arithmetic ensures that the hash value is non-negative."
How is it possible that the only arithmetic operation in the routine
hashval = *s + 31 * hashval;
could end up generating a negative value?
Thanks for all your valuable inputs.