Write the following in c: (in a file called hashing.c)

Declare a struct type HASHCELL, which is used to contain data in a hash table. A HASHCELL should contain two fields: a word field that is a string it should be of type char *, so its a pointer, not an allocated array and a next field that is a pointer to a HASHCELL, so that HASHCELLs can be linked together in a list.

Declare a global variable hashtable, representing a hash table, which is an array of HASHCELL pointers. You should use #define to define a constant SIZE to be 100 and declare hashtable to have SIZE elements.

Define a function hash_string which takes a string (a char *) as a parameter and returns an unsigned integer between 0 and SIZE -1, by hashing the string. You are free to choose your own hash algorithm, but here is a simple one you can use:

o Define an unsigned integer variable hash and initialize it to 1.

o In a loop that iterates over each character in the string, set hash equal to (hash * 7) + c in each iteration of the loop, where c is the current character. Since a char is just an 8-bit number, so its fine to do arithmetic on it.

o Return the value of hash mod SIZE (where % is the mod operator).

Remember that you can recognize the end of a string by the terminating 0. The quality of the hash (i.e., how evenly it distributes hash values between 0 and SIZE - 1) isnt so important here.

Define a function insert_hash_cell that takes a string (again, a char *) as a parameter and inserts the string into the hash table as follows:

o It calls hash_string on the string, assigning the result of the hash to an unsigned integer variable index.

o It creates a HASHCELL (using malloc), such that the word field of the cell points to the string. IMPORTANT: You will need to make a copy of the string by performing the following steps:

Using malloc again, allocate a block of memory large enough to hold the string (including the 0 at the end). I suggest using the built-in strlen function, described at the bottom of this assignment, which gives you the length of a string without the 0 at the end (so youll need to add 1).

Set the word field of the cell to point to the new block of memory.

Copy the characters of the string into the new block. I suggest using the strcpy function

o It inserts the new cell into the linked list of cells pointed to by hashtable[index]. However, if the word in the new cell already exists in that linked list, do not insert the new cell. This prevents duplicate words from being inserted into the hash table. I suggest using the built-in strcmp function to compare two strings to see if they are the same.