COMPLETE THE FOLLWING PROGRAM IN C USING THE TEMPLATES BELOW:

hash.h:

#ifndef __HASH_H

#define __HASH_H

typedef struct HTNodeTag {

char* key;

char* value;

struct HTNodeTag * next;

} HTNode;

typedef struct HashTableTag {

unsigned int ne;

HTNode ** ht;

} HashTable;

unsigned int HashTable_hash(char* str);

HashTable * newHashTable(unsigned int mxs);

void HashTable_add(HashTable* t, char* key, char* value);

char * HashTable_get(HashTable* t, char* key);

void HashTable_remove(HashTable* t, char* key);

void deleteHashTable(HashTable* t);

unsigned int HashTable_max_length(HashTable* t);

char * HashTable_max_key(HashTable* t, char *s);

#endif

hash.c:

#define _POSIX_C_SOURCE 200809L

#include

#include

#include

#include

#include

#include "hash.h"

#define HT_HASH_PRIME 41U

int power(int base, unsigned int exp){

int i, result = 1;

for(i =0; i

result *= base;

return result;

}

/* The function maps a string to an unsigned int */

unsigned int HashTable_hash(char* str)

{

if (str == NULL)

return 0;

}

HashTable* newHashTable(unsigned int mxs)

{

/* Implement a constructor that builds a hashtable relying

on auxiliary chaining (lists) and capable to hold up to

mxs lists in its primary structure. Write a hash function

that is suitable for strings. */

//TODO

}

* return NULL if the key is not on the list */

static HTNode* findInList(HTNode * head, char * key)

{

// TODO

return NULL;

}

/* Add the pair key/value to the hash table t.

* Do nothing is the key is already in the hash table.

* */

void HashTable_add(HashTable* t, char* key, char* value)

{

if (t == NULL)

return;

}

char* HashTable_get(HashTable* t, char* key)

{

/* Returns the value associated to key in t. If there is no

such value (key does not appear in t) simply return NULL */

// TODO

return NULL;

}

void HashTable_remove(HashTable* t, char* key)

{

/* Removes the pair identified by key from the hashtable t */

// TODO

}

void deleteHashTable(HashTable* t)

{

/* Deallocate all the memory needed for t and its auxiliary structures */

}

/* Find the length of the longest list

* Return 0 if the hash table is empty.

* */

unsigned int HashTable_max_length(HashTable* t)

{

// TODO

return 0;

}

/* If s is NULL, return a pointer to the largest key in the hash table.

*

* If s not NULL, return the largest of the keys that are smaller than s.

*

* Do not clone the key.

*

* Return NULL if no key is found.

*

* Note that an empty string is the smallest. So pass NULL to

* find the max.

*/

char * HashTable_max_key(HashTable* t, char *s)

{

// TODO

if (t == NULL)

return NULL;

return NULL;

}

Exercise 2. Hash Table (100 points) In this exercise, you complete the implementation of a hash table with string keys and string values. All hash related files are placed uder directory hash. The hash table API is provided in the git repository in file hash.h. Part of it is shown below in Figure 1. Some but not all API functions are implemented in hash.c. You will nced to implement the missing functions. The only file you need change is hash.c. Do not print anything in your code l typedef struct HTNodeTag char char struct HTNodeTag net eyi alue 5 HTNode 6 7 typedof struct HashTableTag l Number of buckets in the hash table unsigned int ne HTode ht 10 HashTable; 12 unsigaed int HaahTable_has char* atr) 13 HashTable HashTable (igned int nxs) 14 vaid 15 char 16 voicd 17 void 18 char* 19 unsigned int HashTable max length HashTable* t) HashTable.add (HashTablet, char. key, char. value) HashTable get (HashTable t, char ey) HashTable remove(HashTable char* key) deleteHaslTable (HashTable t) HaahTable nax_key (HashTable* t, char a) Figure 1: The hash table API You can picture the data in a hash table as shown in Figure 2. A hash table has a number (ne in HashTable) of "buckets". When adding a value to a hash table, the key is mapped to a hash value, which determines which bucket the value should reside. Multiple values may be placed in the same bucket because of hash collisions. So each bucket maintains a list of key-value pairs. Note that in this problem, both key and value are strings. You need to manage memory space for them properly "34F" "Just for fun" Buckets ne-1:0x key,value,next HTNode HashTable ne-2:0x. ne more HTNode.. 1: NULL key, value, NULLHTNode 0: NULL "Crying" Figure 2: Diagram of a hash table main.c provides an interactive interface that helps you test the code. The commands you can enter are listed below (check the source code for details). The lines start with"#, are comments, not commands that 3 Exercise 2. Hash Table (100 points) In this exercise, you complete the implementation of a hash table with string keys and string values. All hash related files are placed uder directory hash. The hash table API is provided in the git repository in file hash.h. Part of it is shown below in Figure 1. Some but not all API functions are implemented in hash.c. You will nced to implement the missing functions. The only file you need change is hash.c. Do not print anything in your code l typedef struct HTNodeTag char char struct HTNodeTag net eyi alue 5 HTNode 6 7 typedof struct HashTableTag l Number of buckets in the hash table unsigned int ne HTode ht 10 HashTable; 12 unsigaed int HaahTable_has char* atr) 13 HashTable HashTable (igned int nxs) 14 vaid 15 char 16 voicd 17 void 18 char* 19 unsigned int HashTable max length HashTable* t) HashTable.add (HashTablet, char. key, char. value) HashTable get (HashTable t, char ey) HashTable remove(HashTable char* key) deleteHaslTable (HashTable t) HaahTable nax_key (HashTable* t, char a) Figure 1: The hash table API You can picture the data in a hash table as shown in Figure 2. A hash table has a number (ne in HashTable) of "buckets". When adding a value to a hash table, the key is mapped to a hash value, which determines which bucket the value should reside. Multiple values may be placed in the same bucket because of hash collisions. So each bucket maintains a list of key-value pairs. Note that in this problem, both key and value are strings. You need to manage memory space for them properly "34F" "Just for fun" Buckets ne-1:0x key,value,next HTNode HashTable ne-2:0x. ne more HTNode.. 1: NULL key, value, NULLHTNode 0: NULL "Crying" Figure 2: Diagram of a hash table main.c provides an interactive interface that helps you test the code. The commands you can enter are listed below (check the source code for details). The lines start with"#, are comments, not commands that 3