Count Number of Occurrences of Each Word with a Hash Table and Linked Lists

This is the third part of the “number of occurrences” exercise. First, we used the naive approach to store words in an array. Then, we used a hash table with linear probing to make it faster. Now that you learned about linked lists, we can combine the two approaches and implement the hash table, but instead of moving to the next element in case of a collision, just create a linked list of all the elements with the same hash code.

We'll use the following struct as an element of our hash table:

struct word {
  char *word;
  int count;
  struct word *next;
};

Then our hash table will keep pointers to the lists of words:

struct word *data[N] = { NULL }; /* array of pointers */

The array is initialized with all NULL values, which means “no element”. When you read a word, you calculate its hash code code and consider data[code] as a head of the linked list. Iterate over that list. If you see the same word (use strcmp as usual), increment its counter, otherwise, add your word to the beginning of the list.

When you are done, make sure to free all memory, both the words that you allocated with strdup, and the structs that you allocated with malloc.

I'll copy-paste the struct definition and the hash function for you in the code. You write the rest:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 500

struct word {
  char *word;
  int count;
  struct word *next;
};

unsigned int hash(char *s) {
	unsigned int result = 0;
	for ( ; *s; ++s) {
		result = result * 37 + *s;
	}
	return result % N;
}

int main() {
	struct word *data[N] = { NULL };

  /* Your code here! */
}

The complexity calculation of this solution is similar to the calculation for the linear probing case. requires talking about the average and the worst case. For the average input, the hash function will distribute the N words evenly, giving the time complexity of O(NM). In the unlikely case when all words get the same hash code, the complexity will degrade to O(N²M), just like in the linear probing case.