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 under 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 need to implement the missing functions The only file you need change is hash.c. Do not print anything in your code 1 typedef struct HTNodeTag char char struct HTNodeTagnext; key; value; 5HTNode; 6 7 typedef struct HashTableTag unsigned int ne // Number of buckets in the hash table HTNode** 9 ht; 0HashTable 12 unsigned int HashTable_hash (char* str); 13 HashTable newHashTable (unsigned int mxs) 14 void 15 char * 6 void 17 void 18 char* 19 unsigned int HashTable_max_length (HashTablet) HashTable add (HashTablet, char* key, cha HashTable-get (HashTable* t, char* key); HashTable_remove (HashTablet, char* key); deleteHashTable (HashTables t); HashTable_max_key (HashTable*t, char *s); value) 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 "J4F" "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 Figure 2: Diagram of a hash table main.cprovides 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 com!nents not com!nands that 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 under 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 need to implement the missing functions The only file you need change is hash.c. Do not print anything in your code 1 typedef struct HTNodeTag char char struct HTNodeTagnext; key; value; 5HTNode; 6 7 typedef struct HashTableTag unsigned int ne // Number of buckets in the hash table HTNode** 9 ht; 0HashTable 12 unsigned int HashTable_hash (char* str); 13 HashTable newHashTable (unsigned int mxs) 14 void 15 char * 6 void 17 void 18 char* 19 unsigned int HashTable_max_length (HashTablet) HashTable add (HashTablet, char* key, cha HashTable-get (HashTable* t, char* key); HashTable_remove (HashTablet, char* key); deleteHashTable (HashTables t); HashTable_max_key (HashTable*t, char *s); value) 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 "J4F" "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 Figure 2: Diagram of a hash table main.cprovides 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 com!nents not com!nands that
