5. Hashes

Introduction

//------------------------------------------------------------------
#define _GNU_SOURCE

#include <search.h> // hcreate_r() hdestroy_r() struct hsearch_data
#include <string.h>// memset()
#include <stdio.h>// perror()
#include <stdlib.h> //exit()

#define TAB 4

...

struct hsearch_data hash;
size_t max_element = 42; // of elements in search table

...

char * food[] = { "Apple",
                  "Banana",
                  "Lemon",
                  "Carrot"
};
char * color[] = { "red",
                   "yellow",
                   "yellow",
                   "orange"
};

// we create the hash
memset( &hash, 0, sizeof(hash) );
if( hcreate_r(max_element, &hash) == 0 ) {
  perror("hcreate_r");
  exit(1);
}

/*
  adding some elements
*/
  
// we destroy the hash
hdestroy_r( &hash );
  
...

Adding an Element to a Hash

//------------------------------------------------------------------

...

void hash_add_element(char * elmt_key,
                      char * elmt_data,
                      struct hsearch_data * table) {

  ENTRY item;
  ENTRY * ret;
    
  item.key = strdup(elmt_key);
  item.data = strdup(elmt_data);

  if( hsearch_r(item, ENTER, &ret, table) == 0 ) {
    perror("hsearch_r");
    exit(1);
  }
  
  return;
}

...

ENTRY entry;
ENTRY * found;
 
int i;

/*
  hash creation
*/

hash_add_element(food[0], color[0], &hash);
hash_add_element(food[1], color[1], &hash);
hash_add_element(food[2], color[2], &hash);
hash_add_element(food[3], color[3], &hash);

fprintf(stdout, "Known foods:\n");
for( i = 0; i < TAB; i++ ) {
  entry.key = food[i];
  hsearch_r( entry, FIND, &found, &hash );
  fprintf(stdout, "%s\n", found->key);

  // It is the responsibility of the program code
  // to free the elements contained in the hashing table
  free(found->key);
  free(found->data);
}

/*
  hash destruction
*/

...

# Known foods:
# Apple
# Banana
# Lemon
# Carrot

Testing for the Presence of a Key in a Hash

//------------------------------------------------------------------

...

entry.key = "Martini";

if( hsearch_r( entry, FIND, &found, &hash ) != 0 )
  // Martini exists
else
  // it doesn't

...

Deleting from a Hash

//------------------------------------------------------------------

// we can't delete an element with the hashing table
// provided by the GNU C library

Traversing a Hash

Printing a Hash

Retrieving from a Hash in Insertion Order

Hashes with Multiple Values Per Key

Inverting a Hash

Sorting a Hash

Merging Hashes

Finding Common or Different Keys in Two Hashes

Hashing References

Presizing a Hash

Finding the Most Common Anything

Representing Relationships Between Data

Program: dutree