Answered step by step
Verified Expert Solution
Question
1 Approved Answer
// =================== Support Code ================= // Hashmap // // - Implement each of the functions to create a working hashmap. // - Do not change
// =================== Support Code ================= | |
// Hashmap | |
// | |
// - Implement each of the functions to create a working hashmap. | |
// - Do not change any of the function declarations | |
// - (i.e. hashmap_t* hashmap_create() should not have additional arguments) | |
// - You should not have any 'printf' statements in your functions other | |
// than functions that explicitly ask for printf output. | |
// - (You may consider using these printf statements to debug, but they should be removed from your final version) | |
// - You may add any helper functions that you think you need (if any, or otherwise for debugging) | |
// ================================================== | |
#ifndef MY_HASHMAP_T | |
#define MY_HASHMAP_T | |
#include | |
#include | |
// A key value pair | |
// This is specifically for a (char*, char*) key value pair | |
typedef struct pair{ | |
char* key; | |
char* value; | |
}pair_t; | |
// Each node holds a key and a value | |
typedef struct node{ | |
struct node* next; | |
pair_t* kv; // 'kv' stands for key/value pair | |
}node_t; | |
// Simple hash function that will put a key into a bucket | |
// You should not modify this | |
int stringHash(char* myKey, int numberOfBuckets){ | |
return strlen(myKey) % numberOfBuckets; | |
} | |
// Create a function prototype to a function that takes | |
// in a char* and an int. | |
typedef int(*hashFunctionPointer)(char*,int) ; | |
// Chained implementation of a hashmap | |
typedef struct hashmap{ | |
unsigned int buckets; // i.e. size of the hashmap | |
node_t** arrayOfLists; // An array of linked lists for our buckets | |
// Read another way | |
// - an array of node_t* | |
// A function pointer to a hash function | |
// The hash_function must take in a 'char*' as a key, and have a | |
// second parameter specifying the number of buckets. | |
hashFunctionPointer hashFunction; | |
}hashmap_t; | |
// Creates a new hashmap | |
// Allocates memory for a new hashmap. | |
// Initializes the capacity(i.e. number of buckets) | |
hashmap_t* hashmap_create(unsigned int _buckets){ | |
// Allocate memory for our hashmap | |
//TODO | |
// Set the number of buckets | |
//TODO | |
// Initialize our array of lists for each bucket | |
//TODO | |
// Setup our hashFunction to point to our | |
// stringHash function. | |
//TODO | |
// Return the new map that we have created | |
return NULL; | |
} | |
// Frees a hashmap | |
// Responsibility to free a hashmap that has been previously allocated. | |
// Must also free all of the chains in the hashmap | |
// This function should run in O(n) time | |
void hashmap_delete(hashmap_t* _hashmap){ | |
if(_hashmap != NULL){ | |
//TODO | |
} | |
} | |
// Returns a boolean value if a key has been put into | |
// the hashmap | |
// - Returns a '1' if a key exists already | |
// - Returns a '0' if the key does not exist | |
// - Returns a '-9999' if the hashmap is NULL | |
// The algorithm is: | |
// - Call the _hashmap's hash function on the key | |
// - Search that bucket to see if the key exists. | |
// This function should run in average-case constant time | |
int hashmap_hasKey(hashmap_t* _hashmap, char* key){ | |
//TODO | |
} | |
// Insert a new key/value pair into a hashmap | |
// The algorithm is: | |
// - If a key already exists, do not add it--return | |
// - Call the _hashmap's hash function on the key | |
// - Store the key/value pair at the end of the buckets chain | |
// - You should malloc the key/value in this function | |
// This function should run in average-case constant time | |
void hashmap_insert(hashmap_t* _hashmap,char* key,char* value){ | |
// TODO | |
} | |
// Return a value from a key | |
// Returns NULL if the key is not found | |
// The algorithm is: | |
// - If the key does not exist, then--return NULL if not found. | |
// - Call the _hashmap's hash function on the key | |
// - Search the _hashmap's bucket for the key and return the value | |
// This function should run in average-case constant time | |
char* hashmap_getValue(hashmap_t* _hashmap, char* key){ | |
//TODO | |
} | |
// TODO NOTE THAT I DID NOT FINISH REMOVE KEY BECAUSE... | |
// Remove a key from a hashmap | |
// The algorithm is: | |
// - Determine if the key exists--return if it does not. | |
// - Call the _hashmap's hash function on the key | |
// - Search the _hashmap's bucket for the key and then remove it | |
// This function should run in average-case constant time | |
void hashmap_removeKey(hashmap_t* _hashmap, char* key){ | |
//TODO | |
} | |
// Update a key with a new Value | |
// The algorithm is: | |
// - Returns immediately if the key does not exist | |
// - Call the _hashmap's hash function on the key | |
// - Updates the value of the key to the new value | |
// This function should run in average-case constant time | |
void hashmap_update(hashmap_t* _hashmap, char* key, char* newValue){ | |
//TODO | |
} | |
// Prints all of the keys in a hashmap | |
// The algorithm is: | |
// - Iterate through every bucket and print out the keys | |
// This function should run in O(n) time | |
void hashmap_printKeys(hashmap_t* _hashmap){ | |
//TODO | |
} | |
#endif |
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started