12
\$\begingroup\$

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);
}
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I see, I will keep this in mind when I implement it again. Thank you for your suggestions. \$\endgroup\$ – Argus Sep 17 '16 at 4:12
  • 1
    \$\begingroup\$ Certainly you meant memset(new_nodep, 0, sizeof(HashmapNode); and not memset(*new_nodep, 0, sizeof(HashmapNode);. Suggest memset(new_nodep, 0, sizeof *new_nodep); as a further improvement. Using calloc() vs. new_nodep = malloc(.. makes even more sense - as you say later on. \$\endgroup\$ – chux Sep 17 '16 at 12:30
4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ You could be a little less rude with your suggestions, but what can I expect from this place. As usual, I don't know why I wasted my time coming here. The only thing I ever get out of this place are insults and insinuations. \$\endgroup\$ – Argus Sep 17 '16 at 16:09
  • 2
    \$\begingroup\$ Just something to keep in mind codereview.stackexchange.com/help/be-nice. \$\endgroup\$ – pacmaninbw Sep 17 '16 at 18:15
  • 5
    \$\begingroup\$ @Argus The advice in this answer was good, just delivered tactlessly. I've edited it to be more in line with the tone we expect of answers here. \$\endgroup\$ – 200_success Sep 17 '16 at 18:35
  • 3
    \$\begingroup\$ @Argus If you could point to some other place where you've had insults, I'd be grateful, because 99% of the time this community is overwhelmingly positive in my experience. Don't let a bad experience ruin your perception of Code Review. \$\endgroup\$ – Dan Pantry Sep 17 '16 at 18:56
  • 3
    \$\begingroup\$ @Argus I'm sorry, I didn't mean to offend. I should have restrained myself better. \$\endgroup\$ – Ext3h Sep 17 '16 at 22:08
2
\$\begingroup\$

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
    
    }
    
\$\endgroup\$
  • 1
    \$\begingroup\$ In items 1 and 2, the "always" is wrong. If the variable goes out of scope soon, setting it to null is useless. In a hash smearing function (and several other places), a large magic number is ok, provided it can be googled. \$\endgroup\$ – Roland Illig May 23 '18 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.