CSE2425 Hash map

CSE2425, C programming lab, course 2020-2021

Final assignment: Hash map

1 Introduction

In this final assignment you will implement a hash map1 . A hash map is a datastructure that associates a key with a value (a chunk of data). Most hash mapsare implemented as an array of so-called buckets. A hash function translatesa given key (e.g., a name) to an index in the array, where the correspondingbucket is stored.Below we will specify the data structures that you have to provide, and thefunctions that you have to implement. This assignment includes two bonusfunctions that can raise your score from pass (C) to good (B) to excellent (A).

2 Testing The first part of the assignment consist of implementing a test set for the hash map. We have created a number of incorrect hash map implementations. Theyourownimplementation by copy&pasting it into the my tests of the Hashmap assignmentin Weblab.3 Hash map structure Define a type HashMap, which represents the hash map data structure.Note: Use typedef such that a HashMap structure can be used without usingHashMap *hm;4 Creating a hash map

1. Implement a function create_hashmap that returns a pointer to the newlconstructed HashMap structure and has parameter❼ key_space, a size_t2 that represents the number of buckets in the hasmap.1http://en.wikipedia.org/wiki/Hashmap2http://en.wikipedia.org/wiki/Size_t1CSE2425, C programming lab, course 2020-2021This function should allocate enough memoryto fit key_space buckets, and theallocated memory should be zeroed (i.e., NULLed).

2. A hash function maps a string (i.e. an array of chars ending with a nullcharacter) to an index, so it returns a unsigned int. The parameter of a hashfunction is simply a❼ key, a null-terminated string of characters.As the hash map can only hold up to key_space buckets, using the hash function–for example to lookup a mapping– requires some care; apply modulo key_spaceto the result such that the value will be in the available bucket range.

A default hash function named hash should be implemented. This functionshould sum all ASCII values of the characters of the key.For example:char *key = "AC";unsigned int h = hash(key);=> h = 1325 Inserting data Implement a function insert_data that has parameters❼ hm, a pointer to a hash map;

❼ key, a null-terminated string of characters;❼ data, a void pointer to the source data;❼ resolve_collision, a ResolveCollisionCallback (see below).The function should store the data pointer and a copy of the key in the bucketthat can be found by applying the hash function on the key. In case of acollision, i.e. when there already is data with the same key in the hash map, theresolve_collision function should be called with the the previously storeddata and data as arguments and the returned void pointer should be stored inthe bucket insteadResolveCollisionCallback, a pointer to a function that returns a void pointerand has two parameters:❼ old_data, a void pointer to the previously stored data;

❼ new_data, a void pointer to the data that is being newly inserted.The function should determine what data is stored in the has map in case of akey collision by returning the void pointer to the data that is to be stored.2CSE2425, C programming lab, course 2020-20216 Retrieving data Implement a function get_data that has parameters

❼ hm, a pointer to a hash map;❼ key, a null-terminated string of characters.

The function should return the data pointer 代写CSE2425 Hash map (a void pointer) in the hash mathat is associated with the key. If the key is not present in the hash map, NULLshould be returned.

7 Iterator Implement a function iterate that has parameters❼ hm, a pointer to a hash map;

❼ callback, a pointer to a function that returns nothing (i.e. void) and hastwo parameters:– key, a null-terminated string of characters;– data, a void pointer to the dataThis function should iterate over the entire hash map. For each data elementit finds, the callback function should be called with the two members of theelement.8 Removing data Implement a function remove_data that has parameters

❼ hm, a pointer to a hash map;

❼ key, a null-terminated string of characters.

❼ destroy_data, a DestroyDataCallback (see below).This function should remove the element in the hash map that is associated withthe given key. If the destroy_data parameter is non-NULL it should be calledwith the data pointer of the element as argument. If the key is not present, thehash map should remain untouched. As the remove_data function cannot fail,its return typeis void.DestroyDataCallback, a pointer to to a function that returns nothing (i.e.void) and has one parameter:❼ data, a void pointer.The function should clean up the data (e.g. free allocated memory).

3CSE2425, C programming lab, course 2020-20219 Deleting a hash map Implement a function delete_hashmap that has parameters❼ hm, a pointer to the hash map thatis to be deleted;❼ destroy_data, a DestroyDataCallback (see 8).The function should deallocate all memory that was allocated by the hash map.If the destroy_data parameter is non-NULL it should be called for every dataelement that is stored in the hash map with the data pointer of the element as

argument.10 Bonus: New hash function Implement a function set_hash_function that has parameters❼ hm, a pointer to a hash map;

❼ hash_function, a pointer to a hash function that returns a unsigned int

and a single parameter:– key, a null-terminated string of characters.This function should set hash_function as the new hash function of the hashmap hm. Changing the hashfunction means that a particular key may now behashed to different bucket than it was with the previous hash function. Thehash map must beupdated (rehashed) to reflectthis so that all data in thehash map can still be retrieved with their corresponding keys.11 Bonus: Counting Words Implement a function count_words that has parameters❼ stream, a pointer to a FILE.This function should count the number of times each word in the stream occursusing the hash map you implemented. A word is defined as a sequence of one ormore alphanumeric characters (case sensitive). You may use fscanf3 to read aparticular set of characters from a stream but other solutions are also accepted.The data stored in the hash map should be properly allocated and deallocated,do not simply store an integer that is cast to a pointer type. The return typeof the function is void.3http://en.cppreference.com/w/c/io/fscanf, C programming lab, course 2020-2021Given the input:foo bar_, foo!bar "baz". program should writethe following to the standard output:bar: 2baz: 1foo: 3The order in which the output is printed is not important.12 Submission The assignment should be implemented on Weblab.

❼ All test code should be located in the Testing assignment.

❼ All hash map code should be located in the Hashmap assignment.

❼ Put all the word count source code inside the Wordcount assignment;

❼ If you have implemented the first bonus exercise, add the following macroto your Hashamp submission#define NEW_HASH❼ Do not include a main function. (We will use our own test driver, just like

the example test provided.)Submissions violating the above requirements will be automatically rejected bythe Weblab system