tpop(2.9): Hash Table

2.9 Hash Tables

Hash tables are one of the great inventions of computer science. They combine arrays, lists, and some mathematics to create an efficient structure for storing and retrieving dynamic data.
The typical application is a symbol table, which associates some value (the data) with each member of a dynamic set of strings (the keys).

/**
  tpop(2):Algorithm and Data Structure,
  created on Jul 11, 2011
  */

#include <stdio.h>
enum {
    NHASH = 1024,
    MULTIPLIER = 31
};
typedef struct Nameval Nameval;
struct Nameval {
    char *name;
    int value;
    Nameval *next; /* in chain */
};
Nameval *symtab[NHASH]; /* a symbol table */

unsigned int hash(char *);

/* lookup: find name in symtab, with optional create */
Nameval* lookup (char *name, int create, int value)
{
    int h;
    Nameval *sym;

    h = hash(name);
    for (sym = symtab[h]; sym != NULL; sym = sym->next)
      if (strcmp(name, sym->name == 0))
    return sym;
    if (create == 1) {
    sym = (Nameval *)malloc(sizeof(Nameval));
    sym->name = name; /* assumed allocated elsewhere */
    sym->value = value;
    sym->next =  symtab[h];
    symtab[h] = sym;
    }
    return sym;
}


/* hash: compute hash value of string */
unsigned int hash(char *str)
{
    unsigned int h;
    unsigned char *p;

    h = 0;
     for (p = (unsigned char *)str; *p != '\0'; p++)
       h = MULTIPLIER * h + *p;
     return h % NHASH;
}

int main (int argc, char* argv[]) {
 Nameval *item ;
 lookup("mark", 1, 101);
 lookup("ht", 1, 102);
lookup("tao", 1, 101);
item = lookup("mht",1, 10);
    printf("The value of name %s is %d\n", item->name, item->value);
}