For this question, you are asked to implement a hash table ADT in two modules: the ht module with the public interface and the ht$\_$impl module with private declarations and definitions. You are given a header file, ht$.$h$,$ which describes the public interface for the hash table abstract data type. You will implement those function signatures in a file called ht$.$c and declare any additional private datatypes

and functions in another header, called ht$\_$impl.h$.$ Skeleton versions of these additional files are provided. You will first test your hash table ADT with a separate program, before using it to implement a postal code collator. The public interface must be complete, and its header file must not be changed.

In this assignment, our keys will be C strings; however, for hash tables in general, this need not be the case.

Our requirements for your hash table are as follows:

$$ Both the keys and the values that they are mapped to are strings;

$$ Amortized O$(1)$ lookup, insert, and deletion for an arbitrary number of elements;

$$ Safe, correct dynamic memory usage.

Below are some topics which you should investigate and include in your design, including some questions to be answered in the design document.

$1.$ High$-$level operations and the public interface

$2.$ Hash functions, The Division Method

$3.$ Collision resolution

$4.$ Table resizing

$5.$ Data Structures

Testing:

A separate program, named Test.c$,$ to test the hash table implementation. This program must call each of the $7$ functions from ht$.$h$.$

Required files:

$1.$ ht$.$h $($already given in picture$)$

$2.$ ht$.$c

$3.$ ht$\_$impl.h

$4.$ ht$\_$impl.c

$5.$ htTest.c

Most important thing for this question are defining structs for which skeleton is given in ht$.$h$.$

Skeleton version of ht$.$c:

#include $"$ht$.$h$"/*$ Import the public hashtable header. $*/$

#include $"$ht$\_$impl.h$"/*$ Also import the private header. $*/$

struct hasht

I have attached picture of ht$.$h from which you can create ht$.$c and rest header and source file from question.

Thank you!!!