Hash map implementation

Question

I'm a student in college, and while I have coded a lot, I still feel like I've only scraped the surface. I have learned a lot of things over the years, but very few of my professors ever did code reviews and I feel like I may have some bad habits that I may be overlooking, one that was pointed out to me was that I didn't write any comments. I'd like to see if there are any others.

HashMap.h:

#ifndef HASHMAP_H
#define HASHMAP_H

typedef struct HashmapNode{
  unsigned int hash_index;
  int value;
}HashmapNode;

typedef struct HashMap{
  int element_count;
  int map_size;
  HashmapNode ** node_list;
}HashMap;

HashmapNode* hashmap_new_node(unsigned int hash_index, int * values);
HashMap* hashmap_new(int size);
unsigned int hashmap_hash_func(HashMap * hashmap, unsigned int key);
void hashmap_expand(HashMap *hashmap);
void hashmap_delete(HashMap *hashmap, int key);
void hashmap_insert(HashMap *hashmap, unsigned int key, int * values, int values_size);
HashmapNode* hashmap_lookup(HashMap *hashmap, unsigned int key);
void hashmap_destroy(HashMap *hashmap);


#endif

HashMap.c:

#include <stdlib.h>
#include "hashmap.h"

HashmapNode* hashmap_new_node(unsigned int hash_index,int values_size)
{
  HashmapNode *hashmap_node = malloc(sizeof(HashmapNode));
  hashmap_node->hash_index = hash_index;
  hashmap_node->values_size = values_size;
  hashmap_node->values = malloc(sizeof(values_size * sizeof(int)));

  return hashmap_node;
}

HashMap* hashmap_new(int size)
{
  int i;
  HashMap *hashmap = (HashMap*)malloc(sizeof(HashMap));
  hashmap->node_list = malloc(size * sizeof(HashmapNode*));
  hashmap->element_count = 0;
  hashmap->map_size = size;

  for(i = 0; i < size; i++)
  {
    hashmap->node_list[i] = malloc(sizeof(HashmapNode));
    hashmap->node_list[i] = NULL;
  }
  return hashmap;
}

unsigned int hashmap_hash_func(HashMap *hashmap, unsigned int key)
{
   int hash = key;

   hash = (hash >> 3) * 2654435761;
   hash = hash % hashmap->map_size;
   return hash;
}

void hashmap_expand(HashMap *hashmap)
{
  int i;
  int hash_index;
  int old_size = hashmap->map_size;
  HashmapNode *hashmap_node;

  hashmap->map_size = old_size * 2;
  HashmapNode **new_node_list = malloc(hashmap->map_size * sizeof(HashmapNode*));

  for(i = 0; i < hashmap->map_size; i++)
  {
    new_node_list[i] = malloc(sizeof(HashmapNode));
    new_node_list[i] = NULL;
  }

  for(i = 0; i < old_size; i++)
  {
    hashmap_node = hashmap->node_list[i];
    if(hashmap_node != NULL)
    {
      hash_index = hashmap_hash_func(hashmap, hashmap_node->hash_index);
      hashmap_node->hash_index = hash_index;
      new_node_list[hash_index] = hashmap_node;
    }
    free(hashmap_node);
  }
  hashmap->node_list = new_node_list;
}

void hashmap_delete(HashMap *hashmap, int key)
{
  int hash = hashmap_hash_func(hashmap, key);
  HashmapNode *hashmap_node = hashmap->node_list[hash];
  hashmap_node->values = NULL;
  hashmap_node->hash_index = 0;
  hashmap_node->values_size = 0;
}

HashmapNode* hashmap_lookup(HashMap *hashmap, unsigned int key)
{
  unsigned int hash = hashmap_hash_func(hashmap, key);
  HashmapNode *hashmap_node = hashmap->node_list[hash] ;

  if(hashmap_node == NULL)
  {
    return NULL;
  }
  else
  {
    return hashmap->node_list[hash];
  }
}

void hashmap_insert(HashMap *hashmap, unsigned int key, int value)
{
  unsigned int hash = hashmap_hash_func(hashmap, key);
  double map_percentage;
  HashmapNode *hashmap_node = hashmap->node_list[hash];

  map_percentage = (double)hashmap->element_count / (double)hashmap->map_size;

  if(map_percentage >= 0.75)
  {
    hashmap_expand(hashmap);
  }

  if(hashmap_node != NULL && hashmap->node_list[hash]->hash_index == key)
  {
    return;
  }
  else
  {
    hashmap_node = hashmap_new_node(hash, value);
    hashmap->element_count++;
  }

}

void hashmap_update_value(HashMap *hashmap, unsigned int key, int value)
{
  HashmapNode *hashmap_node = hashmap_lookup(hashmap, key);

  if(hashmap_node != NULL && hashmap->node_list[hash]->hash_index == key)
  {
    return;
  }
  else
  {
    hashmap_node->value = value;
  }
}

void hashmap_destroy(HashMap *hashmap)
{
  int i;

  for(i = 0; i < hashmap->map_size; i++)
  {
    free(hashmap->node_list[i]);
  }
  free(hashmap);
}

Answer 1

Always Test the Value Returned From Malloc
The memory allocation functions such as malloc() and calloc() may fail for a number of reasons, such as there is no memory to allocate or there is no block of memory large enough to allocate. When these memory functions fail they return NULL. After every call to malloc() always check the pointer receiving the memory address to see if malloc() returned NULL. This prevents accessing a memory address through a NULL pointer.

Example of a possible correct way:

  HashmapNode *hashmap_node = NULL;

  hashmap->map_size = old_size * 2;
  HashmapNode **new_node_list = calloc(hashmap->map_size, sizeof(HashmapNode*));

  if (new_node_list != NULL)
  {
    for(i = 0; i < hashmap->map_size; i++)
    {
      HashmapNode new_nodep = NULL;
      new_nodep = malloc(sizeof(HashmapNode));
      if (new_nodep == NULL)
      {
        // **PUT ERROR HANDLING CODE HERE**
      }
      else
      {
        memset(*new_nodep, 0, sizeof(HashmapNode); // Initialize memory to null values
        new_node_list[i] = new_nodep;
      }
    }
  }
  else
  {
    // **PUT ERROR HANDLING CODE HERE**
  }

In C Always Initialize the Variables
In C there is no guarantee that a variable on the stack is going to be initialized to zero or NULL. To avoid unknown behavior and unknown results initialize all variables when they are declared. This has saved me a lot of debugging over the years. When I was writing code that integrated many libraries this was one of the type of bugs I often had to track down.

  int i = 0;
  int hash_index = 0;
  int old_size = hashmap->map_size;
  HashmapNode *hashmap_node = NULL;

Portability
The HashMap.c file contains

#include "hashmap.h"

but it is named HashMap.h in the question. Some operating systems ignore case in file names, others are quite strict. To avoid portability issues make sure the name of the included file is the same for both the operating system and in the #include.

calloc() versus malloc()
The function calloc(size_t n_items, size_t size_of_one_location) is meant to allocate arrays of some item. It makes the code clearer with similar results.

Answer 2

hashmap_insert does not correctly implement a hash map:

if(hashmap_node != NULL && hashmap->node_list[hash]->hash_index == key)
{
    return;
}
else
{
    hashmap_node = hashmap_new_node(hash, value);
    hashmap->element_count++;
}

In a hash map, when encountering the same key hash twice, you don't override the old key. Instead you apply another round of the hash function, to guess the next possible location, until you find an empty spot in the hash map.

The same goes when searching elements in a hash map. If the first round doesn't match the key you were searching for, you have to continue iterating until you either find a gap (indicating that the key is not part of the hashmap), or you actually find the specified key.

This also works differently when deleting from a hash map. As the existence of a gap is an indicator that a value has never existed, you can't just delete the first node the hash points to.

---

HashmapNode ** node_list;

Why fiddle around with sparse allocation? There is no need for that double indirection.

One of the characteristics of self resizing a hash map is, that you only have little overallocation anyway. So just allocate all instances of HashmapNode in continuous memory.

---

HashmapNode* hashmap_new_node(unsigned int hash_index, int * values);
HashmapNode* hashmap_new_node(unsigned int hash_index,int values_size){}

The compiler should have warned you of the inconsistent function signatures. Be sure to enable and heed your compiler warnings.

---

hashmap->node_list[i] = malloc(sizeof(HashmapNode));
hashmap->node_list[i] = NULL;

That's a massive memory leak you got there, allocating memory and throwing the reference away. You should use essential tools such as Valgrind to check your code for memory leaks such as this.

And that is not your only memory leak — every second function of yours has one or more.

---

unsigned int hashmap_hash_func(HashMap *hashmap, unsigned int key)
{
   int hash = key;

   hash = (hash >> 3) * 2654435761;
   hash = hash % hashmap->map_size;
   return hash;
}

You should read Knuth's Multiplicative Hash to understand some very specific requirements of hash functions. Notably, the size of the hash table must be prime. Also, you discarded the most important 3 bits without any good reason.

---

To be honest? I recommend reimplementing it from scratch after reading more about how a hash map should work.

Answer 3

Few more comments are:

1. Always better to assign NULL to the pointer which you are freeing:

   free(hashmap); then hashmap = NULL;
   

2. It's always better to define an enum / macro for any numeric value used in the code:

   hash = (hash >> 3) * 2654435761;
   

   Here, define a macro for 2654435761 with a meaningful name.

3. Generally, the curly bracket be placed just after the function name rather than placing that in the next line:

   HashMap* hashmap_new(int size)
   {
   }
   
   HashMap* hashmap_new(int size) {
   
   //Code Here
   
   }