For this assignment you will be writing a C program that creates and uses a hash table. Your program will load a file of words into a hash table, support searching for a word, and returning the line number$($s$)$ containing that word.

All assignment submissions will be validated using the class VM$.$

Program Requirements

Below are the requirements for your program.

Hash table implementation

Hash table must implement separate chaining

Use a linked list for each node $($see below$)$

typedef struct Node

$\{$

$$ char $*$key;

$$ int value;

$$ struct Node $*$next;

$\}$ Node;

Static bucket array of size $100($see below$)$

#define BUCKET$\_$SIZE $100$

typedef struct

$\{$

$$ Node $*$bucket$[$BUCKET$\_$SIZE$]$;

$$int slots$\_$used; $//$ Number of used bucket elements $($slots$)$ used in the hash table

$$int nodes$\_$used; $//$ Number of nodes used in the hash table

$$ int max$\_$nodes; $//$ Maximum number of nodes used by a slot in the hash table

$\}$ HashTable;

Required functions

You project must include and implement the following function prototypes. You may include other functions if needed.

unsigned int hash$($const char $*$key$)$;

The hash$()$ function uses the key, and calculates and returns the bucket index value. The source code for this function is provided later in the project.

void initialize$($HashTable $*$ht$)$;

The initialize$()$ function sets all bucket values to NULL, and slots$\_$used, nodes$\_$used, and max$\_$nodes to $0.$

Node $*$createNode$($const char $*$key$,$ int value$)$;

The createNode$()$ function uses dynamic memory to create a new Node, and assign the new Node properties: key, value, next. Ensure dynamic memory allocation works, or output "Failed to allocate memory for new node.".

void insert$($HashTable $*$ht$,$ const char $*$key$,$ int value$)$;

The insert$()$ function calls hash$()$ to create a bucket index, and createNode$()$ to create a new Node, and add$/$append the Node to the linked list associated with the bucket index. You will also need to update$$slots$\_$used, nodes$\_$used, and max$\_$nodes$$appropriately$.$

void get$($HashTable $*$ht$,$ const char $*$key$,$ int $**$results$,$ int $*$count$)$;

The get$()$ function uses the key parameter to set the results parameter to an array of line numbers that match the key, and set the count parameter to the number of returned line numbers.

void freeHashTable$($HashTable $*$ht$)$;

The freeHashTable$()$ function frees all memory used by the hash table.

float calculateLoadFactor$($HashTable $*$ht$)$;

The calculateLoadFactor$()$ calculates and returns the hash table load factor $($slots$\_$used $/$ BUCKET$\_$SIZE$).$