Description

Implement basic operations for hash table, which are search insert delete. Besides, we will require you to implement some easy extra functions to create and free your hash table.

Header file

In order to test your code, we have specified the interface of your implemetation.

#ifndef HASH_HASH_H
#define HASH_HASH_H
void *initializer(int size);
// EFFECT: initialize an empty hash table with number of buckets specified by size

void insert(void* hashtable, int size, int key, int value);
// EFFECT: If the key does not exist, insert an element(a key-value pair) to hash table. If key already exists, update the value.

void delete(void* hashtable, int size, int key);
// EFFECT: Delete an element(key-value pair) specified by the key. If it does not exist, do nothing

void* search(void* hashtable, int size, int key);
// EFFECT: Given a hash table, return the pointer to the element(key-value pair) specified by the key, return NULL if not found.

int getValue(void* element);
// EFFECT: obtain the value of the element

void freeHashtable(void* hashtable, int size);

#endif //HASH_HASH_H

Submission

Requirement

You are required to implement the hash table with separate chaining.

Files

You should submit a tar or zip file containing a c source file named as hash.c. It should be like:

// define your only data structure here, you may define hashtable, buckets, elements, etc...
void *initializer(int size)
{
        // your code here
}

void insert(void* hashtable, int size, int key, int value)
{
        // your code here
}

void delete(void* hashtable, int size, int key)
{
        // your code here
}

void* search(void* hashtable, int size, int key)
{
        // your code here
}

int getValue(void* element)
{
        // your code here
}

void freeHashtable(void* hashtable, int size)
{
        // your code here
}

Testing

Test Program

We will test your hash table with a testing program. You don't need to consider too much about it, only for a reference.

#include <stdio.h>
#include <string.h>
#include "hash.h"

int main()
{
    int size;
    scanf("%d", &size);
    void* hashtable=initializer(size);
    int n;
    scanf("%d", &n);
    char buffer[100];
    for (int i = 0; i < n; ++i)
    {
        printf("%d\n", i);
        scanf("%s", buffer);
        if (strcmp(buffer, "insert") == 0)
        {
            int key, value;
            scanf("%d", &key);
            scanf("%d", &value);
            insert(hashtable, size, key, value);
        } else if (strcmp(buffer, "delete") == 0)
        {
            int key;
            scanf("%d", &key);
            delete(hashtable, size, key);
        } else if (strcmp(buffer, "search") == 0)
        {
            int key;
            scanf("%d", &key);
            void* element=search(hashtable, size, key);
            if(element!=NULL)
            {
                int value=getValue(element);
                printf("The value is %d.\n",value);
            }
        }
        printf("***End***\n");
    }
    freeHashtable(hashtable, size);
    return 0;
}

IO format

Input

the number of bucket \(size\) on the first line
the number of operations \(n\) on the first line.
an operation on the next \(n\) lines

Output

the searching results
detailed output can be found by testing it yourself

Sample IO

Input

7
5
insert 15 11
delete 23
search 22
search 15
insert 21 24

Output

0
***End***
1
***End***
2
***End***
3
The value is 11.
***End***
4
***End***