title: Implementing a Hash Table in C Programming with Dynamic Memory Allocation and Rehashing hash table
body: <p>I have a programming assignment in C that requires the implementation of a hash table. I'm trying to get the set function to work properly and rehash each time the load factor exceeds one. Also how should I free the memory spaces in my code?</p>
  
  <p>// Code is below:</p>
  
  <p>hashtable.h Code:</p>
  
  <pre><code>/* This header is intended to be used with a chained
     hash-table implementation.  Correspondingly, there
     are two structure definitions -- one for the table
     itself, and another for the nodes of the individual
     chains. */
  
  #ifndef HASHTABLE_H
  #define HASHTABLE_H
  #include &lt;stddef.h&gt; // size_t
  
  /// structure for the nodes of the chains
  struct node_s {
      char *key;
      int value;
      struct node_s *link;
  };
  
  /// This is the main structure for the overall table.
  struct table_s {
      /// This should be used as a pointer to a dynamically
      /// allocated array of pointers to node structures.
      struct node_s **table;
  
      /// This is for storing the maximum number of buckets/lists in the table.
      size_t bins;
  
      /// This is for storing the current number of elements in the table
      size_t size;
  };
  
  /// A convenience declaration for referring to a pointer to a HT..
  typedef struct table_s *hash_t;
  
  /// Allocate a table with some initial empty bins.
  /// @param bins -- the number of bins in the table (initally empty)
  /// @return -- a pointer to a dynamically allocated hash table
  hash_t create_table(int bins);
  
  /// Set the value for a key in a given hash table.
  /// @note -- if this is the first time setting this key, then the
  ///          table must make a dynamic copy of the string.  This
  ///          copy must be freed when the table is freed.
  /// @note -- if the table exceeds a load factor of 1 after setting
  ///          the key/value pair, then this function should trigger
  ///          rehashing into a larger table.  It will then deallocate
  ///          the table field in the table_s structure, but it will
  ///          NOT free the table address in the table parameter.
  /// @param table -- a pointer to a hash table
  /// @param key -- a key
  /// @param value -- a value
  /// @return nothing
  void set(hash_t table, char *key, int value);
  
  /// Get the value for a key in a given hash table,
  ///   returning a default value if the key is not in the table.
  /// @param table -- a pointer to a hash table
  /// @param key -- a key
  /// @param defval -- the default value for nonexistent keys
  /// @return -- the value associated with the key (or the default value)
  int get(hash_t table, char *key, int defval);
  
  
  /// Free the table and all associated keys.
  /// @param table -- a pointer to a hash table
  /// @return nothing
  void free_table(hash_t table);
  #endif
  </code></pre>
  
  <p>hashtable.c Code:</p>
  
  <pre><code>    // Include statements
      #include &lt;stdio.h&gt;
      #include &lt;stdlib.h&gt;
      #include &lt;string.h&gt;
      #include &lt;limits.h&gt;
      #include "hashtable.h"
      #include "hash.h"
  
      /* Functions */
  
      /* Function get 
         Get the value for a key in a given hash table,
         returning a default value if the key is not in the table.
         @param table -- a pointer to a hash table
         @param key -- a key
         @param defval -- the default value for nonexistent keys
         @return -- the value associated with the key (or the default value)
      */
  
      int get(hash_t table, char *key, int defval) {
  
      // set key value to default value
      int keyValue;
  
      // Obtain the unsigned int of the hash key
      unsigned int hashValue = hash(key);
  
      // Obtain the bin index by finding the moduluus of hash value and number of bins
      int bin_index = hashValue % table-&gt;bins;
  
      // while loop
      while(table-&gt;table[bin_index] != NULL) {
  
          if(strcmp(key, table-&gt;table[bin_index]-&gt;key) == 0) {
              // Set the current node to the adjacent one
              keyValue = table-&gt;table[bin_index]-&gt;value;
  
          } else if(strcmp(key, table-&gt;table[bin_index]-&gt;key) != 0) {
  
              // Create a temporary struct node
              struct node_s *temp_Node = table-&gt;table[bin_index];
  
              while(temp_Node-&gt;link != NULL) {
                  if(strcmp(key, temp_Node-&gt;key) != 0){
                      // Set the temp node to the adjacent linked node
                      temp_Node = temp_Node-&gt;link;
                  } else {
                      keyValue = temp_Node-&gt;value;
                  }
              }
  
          } else {
              // Key value equals default value
              keyValue = defval;
          } 
  
      }
  
      return keyValue;
  
  }
  
  /* Function create_table */
  hash_t create_table(int bins) {
  
      size_t numberOfBins = bins;
      int index;
  
      // Declare a hash table
      hash_t hashTable = malloc(sizeof(hash_t));
  
      // Callocing the table pointer
      hashTable-&gt;table = calloc(numberOfBins, sizeof(struct node_s*) * bins);
  
      // Fill in the bins
      hashTable-&gt;bins = bins;
  
      for(index = 0; index &lt; bins; index++) {
          hashTable-&gt;table[index] = NULL;
      }
  
      // Initialize the size to 0
      hashTable-&gt;size = 0;
  
      return hashTable;
  
  }
  
  /* Function set */
  void set(hash_t table, char *key, int value) {
  
      unsigned int hash_number = hash(key);
        int bin_index = hash_number % table-&gt;bins;
  
        printf("Index Number: %d ", bin_index);
  
      // Create pointer current_Node
        //struct node_s *current_Node = malloc(sizeof(struct node_s));
        struct node_s *current_Node = table-&gt;table[bin_index];
  
       // Create pointer updated_Node
      struct node_s *updated_Node = malloc(sizeof(struct node_s));
        updated_Node-&gt;key = key;
        updated_Node-&gt;value = value;
        updated_Node-&gt;link = NULL;
  
        printf("Updated node key: %s ", updated_Node-&gt;key);
        printf("Updated node value: %d ", updated_Node-&gt;value);
  
  
      // If else statement
  
        if(current_Node == NULL) {
              table-&gt;table[bin_index] = updated_Node;
  
              // Increase the size of the table by 1
              table-&gt;size += 1;
        } else if(current_Node != NULL) {
              /*While the current node's adjacent one is not null
               Assign the current node to it's adjacent one.
          */
  
              while(current_Node-&gt;link != NULL) {
                  current_Node = current_Node-&gt;link;
              }
  
              // Assign the node's adjacent one to the updated node
              current_Node-&gt;link = updated_Node;
        }
  
        printf("\n");
  
  
        // Calculate the load factor
      int count = 0;
      double load_factor = count;
  
      for(unsigned int j = 0; j &lt; table-&gt;bins; j++) {
  
              current_Node = table-&gt;table[j];
  
              // While loop
              while(current_Node) {
                  count++;
                  // Update the reference node
                  current_Node = current_Node-&gt;link;
              }   
  
              if(count &gt; load_factor) {
                  load_factor = count;
              }
  
              count = 0; // reset the count
  
      } 
  
       // Nested for loop for each particular bin
       if(load_factor &gt; 1) {
           //size_t reference_size = table-&gt;size;
  
           // Double the size of the table and rehash each element
           table-&gt;size = table-&gt;size * 2;
  
           //for(int k = 0; k &lt; 
           // Rehashing each element
  
       }
  
  
  
  }
  
  
  
  /* Function free_table - Free the table and all associated keys.
     @param table -- a pointer to a hash table
     @return nothing  
  */
  void free_table(hash_t table) {
  
      // Traverse each individual node
      for(unsigned int pos = 0; pos &lt; table-&gt;size; pos++) {
          struct node_s *currentNode = table-&gt;table[pos];
  
          // Free the elements of the node
          free(currentNode-&gt;key);
  
          while(currentNode-&gt;link != NULL) {
            currentNode = currentNode-&gt;link;
            free(currentNode-&gt;link);
          }
          // Free the current node
          free(currentNode);
      }  
  
      // Free the table and the table inside
      free(table-&gt;table);
      free(table);
  
  
  }
  </code></pre>
  
  <p>hash.c Code:</p>
  
  <pre><code>#include "hash.h"
  
  /// Calculate a hash function.
  /// @param key -- a null-teriminated character string
  /// @return -- the hash value
  unsigned int hash(char *key) {
      unsigned int sum = 0;
      while (*key != '\0')
      sum += *(key++);
      return sum;
  }
  </code></pre>
  
  <p>hash.h code:</p>
  
  <pre><code>/// Defines a declaration for a hash function.
  
  #ifndef HASH_H
  #define HASH_H
  
  /// Calculate a hash function.
  /// @param key -- a null-teriminated character string
  /// @return -- the hash value
  unsigned int hash(char *key);
  #endif
  </code></pre>
  
  <p>driver.c code:</p>
  
  <pre><code>#include "hashtable.h"
  
  #include &lt;assert.h&gt; // assert
  #include &lt;stdint.h&gt; // uint64_t
  #include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt; // rand
  #include &lt;time.h&gt; // clock, CLOCKS_PER_SEC
  
  // The maximum length of a key for THIS DRIVER ONLY.
  // The general implementation should support arbitrary length keys!
  // If you do not support arbitrary length keys, then you should lose points.
  static const int max_key = 11; // strlen("4294967295") + 1;
  
  // Generate random key/value pairs, and check they are set correctly.
  // @param max_num -- the largest number to for a key
  // @param trials -- the number of trials
  static void checkit(int max_num, int trials) {
      char key[max_key];
      hash_t table = create_table(10);
      for (int i = 0; i &lt; trials; i++) {
          int sample = rand() % max_num;
          sprintf(key, "%d", sample);
          set(table, key, sample);
      }
      unsigned int failures = 0;
      for (int i = 0; i &lt; max_num; i++) {
          sprintf(key, "%d", i);
          int value = get(table, key, i);
          if(value != i) {
              fprintf(stderr, "error: key/val mismatch for %s - got %d\n",key, value);
              failures++;
          }
      }
      free_table(table);
      if (failures == 0) // ignoring the possibility of overflow
          printf("Sucessfully stored %d key/value pairs without"
                 " loss of information.\n", trials);
      else
          printf("Failed on %u of %d trials (%.2f).\n", failures, trials,
                 failures/(float)trials);
  }
  
  // Generate random key/value pairs and time the operation.
  // @param max_num -- the largest number to for a key
  // @param trials -- the number of trials
  void timeit(int max_num, int trials) {
      char key[max_key];    
      hash_t table = create_table(10);
      uint64_t tics = 0;
      for (int i = 0; i &lt; trials; i++) {
          int sample = rand() % max_num;
          sprintf(key, "%d", sample);
          uint64_t t1 = clock();
          set(table,key, 1 + get(table, key, 0));
          tics += clock() - t1;
      }
      free_table(table);
      printf("Test took %.2f seconds.\n", (float)tics/(float)CLOCKS_PER_SEC);
  
  }
  
  int main(int argc, char **argv) {
      // Default values
      int max_num = 100;
      int trials = 1000;
  
      if (argc == 3) {
          max_num = strtol(argv[1], NULL, 10);
          trials = strtol(argv[2], NULL, 10);
      } else if (argc != 1) {
          fprintf(stderr, "unexpected arguments.\n");
          fprintf(stderr, "usage: %s [max_num trials]\n", argv[0]);
          exit(1);
      }
      checkit(max_num, trials);
      timeit(max_num, trials);
      return 0;
  }
  </code></pre>