##########################################################

hashtable.c

// HashTable Implementation Starter Code // CMS 230, 2017

#include #include #include

// Hashtable struct definitions and function prototypes #include "hashtable.h"

//*** Hash a string to an integer ***// // Input // char *s: the string to hash // Returns // The integer hash code // // Implements the basic hashing String hashing algorithm used by Java. unsigned long int hash(char *s) { unsigned long int h = 0;

int i; for (i = 0; i

return h; }

//*** Create a new hashtable_t ***// // Input // tableSize: the number of buckets in the new table // Returns // A pointer to the new table HashTable * hashtableInit(int tableSize) {

// Allocate memory for a new HashTable

// Allocate memory for an array of buckets and assign // them to the table's buckets field

// Set the new HashTable's size field

// Return the new HashTable

}

//*** Insert a key-value pair into a table ***// // Inputs // hashtable *h: the hashtable performing the insertion // char *key: the key string // char *value: the value string // Returns // Nothing void hashtableInsert(HashTable *h, char *key, char *value) {

}

//*** Lookup the value associated with a particular key ***// // Inputs // hashtable_t *h: the table // char *key: the key to find // Returns // The char *value associated with the key or NULL if no match exists char * hashtableLookup(HashTable *h, char *key) {

}

//*** Remove a key-value pair from the table if it exists ***// // Inputs // hashtable_t *h: the table // char *key: the key to find and remove // Returns // The char *value associated with the key or NULL if no match exists // The pair is removed if it exists in the table char * hashtableRemove(HashTable *h, char *key) {

}

//*** Print a hashtable ***// // Input // hashtable_t *h: the table // Output // the hashtable, printed by buckets void hashtablePrint(HashTable *h) { int i; for (i = 0; i size; i++) { HashNode *node = h->buckets[i]; printf("Contents of bucket %d: ", i);

while (node != NULL) { printf(" ", node->key, node->value); node = node->next; } } }

//*** There is no main function --- use the Python test script ***//

##########################################################

hashtable.h

//*** Structure definitions ***//

typedef struct _hashnode_t {

char* key;

char* value;

struct _hashnode_t* next;

} HashNode;

typedef struct _hash_t {

// Each bucket is a linked list accessed by a HashNode* pointer

// The table itself has an array of buckets, which is equivalent to an array

// of HashNode*; this is implemented using HashNode**.

HashNode** buckets;

// The number of buckets in the table

int size;

} HashTable;

//*** Function prototypes ***//

unsigned long int hash(char*);

HashTable* hashtableInit(int);

void hashtableInsert(HashTable*, char*, char*);

void hashtablePrint(HashTable*);

char* hashtableRemove(HashTable*, char*);

char* hashtableLookup(HashTable*, char*);

Hash Table CMS 230, Fall 2018 Due Monday, November 5, at 11:59 PM Description Implement a hash table using structures in C . Your table must support initialization, insert, lookup, remove, and print operations . The keys and values in the table wil both be of type char*. The keys wil be null-terminated strings. Use the included hashtable.c as a starting point. The hashtable.h header contains function prototypes and structure definitions. This project will let you practice using memory allocation and structures to implement a non-trivial data structure. Along the way, you'll get to work witlh hash function (always an important topic) and arrays of pointers. Background Recall that a hash table is used to store key-value pairs and allows for average O(1) insert and lookup times if the load on the table is not too high. A chained hash table consists of an array of buckets. Each bucket contains a linked list of nodes that store the key-value pairs To insert into the table, calculate an integer from the key and use it to determine the bucket that should hold the new key-value pair, as in the following pseudo-C implementation: void hashtableInsert (HashTable* h, char* key, char* value) f unsigned long int hashCode- hash(key) int b hashCode % h->size; / Insert key-value pair into h->buckets [b]