[next] [prev] [prev-tail] [tail] [up]

4 Basic hash table

Let us assume that we want to use a hash table so that we can lookup an address based on the name (first+middle+last) of a person. First, we define a hash function. Without knowing any better, we use the hash function in listing 1.


Listing 1:hashfunction1
 
1int h(const char *name, int max) 
2{ 
3  int sum = 0; 
4  while (*name) 
5  { 
6    sum += *name++; 
7  } 
8#ifdef ILLUSTRATE 
9  printf("%d\n",sum); 
10#endif 
11  return sum % max; 
12}

We simply add up the ASCII code of all the characters, then mod the sum with max to make sure the return value is between 0 and max-1.

Next, we define an array to store addresses. We define this array according to listing 2.


Listing 2:hashstructure
 
1#define HASHENTRY_INUSE 0x00000001 
2 
3struct _HashEntry 
4{ 
5  int flags; 
6  char value[MAX_ADDR_LEN]; 
7}; 
8 
9struct _HashTab 
10{ 
11  struct _HashEntry table[MAX_ENTRIES]; 
12  int size; 
13} ;

struct _HashTab is the hash table. It is not an array because we want it to encapsulate useful information related to a hash table, such as the number items stored in the hash table. table (as a data member) is the array of struct _HashEntry. Each struct _HashEntry consists of a flags integer and the value.

 4.1 Creation/Initialization
 4.2 Insert
 4.3 Remove
 4.4 Lookup

[next] [prev] [prev-tail] [front] [up]