Hashmap is a special abstract data structure that maps two objects called keys and values in memory for faster lookup times.

How does it work?

The data structure uses a hash function to compute the index(also called hash code). I have used FNV-1a hash function. The algorithm for which is given as…

hash := FNV_offset_basis
   for each byte_of_data to be hashed do
       hash := hash XOR byte_of_data
       hash := hash × FNV_prime

   return hash

This index is used in array of buckets or slots for lookup. During this lookup, the key is hashed and the result hash indicates the index or where the corresponding value is stored.

The methods implemented are:

• Create

Hash_Map *init_hashmap() {
  Hash_Map *tmp_hmap = (Hash_Map *)malloc(sizeof(Hash_Map));
  if (tmp_hmap == NULL) {
    printf("memory allocation failed!\n");
    exit(EXIT_FAILURE);
  }

  tmp_hmap->length = 1;
  allocate_NULL_ITEM(tmp_hmap, tmp_hmap->length);
  return tmp_hmap;
}

• Print

void print_hmap(Hash_Map *hmap) {
  printf("{\n");
  for (int i = 0; i < hmap->length; i++) {
    if ((hmap->map[i]).isEmpty) {
      print_item(NULL_ITEM);
    } else {
      print_item(hmap->map[i]);
    }
  }
  printf("}\n");
}

• Delete

void delete(Hash_Map *hmap, char *key) {
  hmap->map[get_index(key, hmap->length)] = NULL_ITEM;
}

• Insert

Most often problems we encounter is that of collision, which can be solved by many methods and one of them is Linear Probing.