· 7 years ago · Nov 25, 2018, 03:32 AM
1/*
2 * CS 261 Data Structures
3 * Assignment 5
4 * Name:
5 * Date:
6 */
7
8#include "hashMap.h"
9#include <stdlib.h>
10#include <stdio.h>
11#include <string.h>
12#include <assert.h>
13#include <ctype.h>
14
15int hashFunction1(const char* key)
16{
17 int r = 0;
18 for (int i = 0; key[i] != '\0'; i++)
19 {
20 r += key[i];
21 }
22 return r;
23}
24
25
26/**
27 * Creates a new hash table link with a copy of the key string.
28 * @param key Key string to copy in the link.
29 * @param value Value to set in the link.
30 * @param next Pointer to set as the link's next.
31 * @return Hash table link allocated on the heap.
32 */
33HashLink* hashLinkNew(const char* key, int value, HashLink* next)
34{
35 HashLink* link = malloc(sizeof(HashLink));
36 link->key = malloc(sizeof(char) * (strlen(key) + 1));
37 strcpy(link->key, key);
38
39 link->value = value;
40 link->next = next;
41 return link;
42}
43
44/**
45 * Free the allocated memory for a hash table link created with hashLinkNew.
46 * @param link
47 */
48static void hashLinkDelete(HashLink* link)
49{
50 free(link->key);
51 free(link);
52}
53
54/**
55 * Initializes a hash table map, allocating memory for a link pointer table with
56 * the given number of buckets.
57 * @param map
58 * @param capacity The number of table buckets.
59 */
60void hashMapInit(HashMap* map, int capacity)
61{
62 if (map == NULL)
63 return;
64 map->table = malloc(sizeof(HashLink*) * capacity);
65 map->capacity = capacity;
66 map->size = 0;
67 for (int i = 0; i < capacity; i++)
68 {
69 map->table[i] = NULL;
70 }
71}
72
73/**
74 * Removes all links in the map and frees all allocated memory. You can use
75 * hashLinkDelete to free the links.
76 * @param map
77 */
78void hashMapCleanUp(HashMap* map)
79{
80 // FIXME: implement -11/21
81 struct HashLink *current, *next;
82
83 for (int i = 0; i < map->capacity; i++)
84 {
85 current = map->table[i];
86 while(current != 0)
87 {
88 next = current->next;
89 hashLinkDelete(current); //free links
90 current = next;
91 }
92 map->table[i]= 0;
93 }
94
95}
96
97/**
98 * Creates a hash table map, allocating memory for a link pointer table with
99 * the given number of buckets.
100 * @param capacity The number of buckets.
101 * @return The allocated map.
102 */
103HashMap* hashMapNew(int capacity)
104{
105 HashMap* map = malloc(sizeof(HashMap));
106 hashMapInit(map, capacity);
107 return map;
108}
109
110/**
111 * Removes all links in the map and frees all allocated memory, including the
112 * map itself.
113 * @param map
114 */
115void hashMapDelete(HashMap* map)
116{
117 hashMapCleanUp(map);
118 free(map);
119}
120
121/**
122 * Returns a pointer to the value of the link with the given key
123 * and skip traversing as well. Returns NULL
124 * if no link with that key is in the table.
125 *
126 * Use HASH_FUNCTION(key) and the map's capacity to find the index of the
127 * correct linked list bucket. Also make sure to search the entire list.
128 *
129 * @param map
130 * @param key
131 * @return Link value or NULL if no matching link.
132 */
133int* hashMapGet(HashMap* map, const char* key)
134{
135 // FIXME: implement
136 int idx = HASH_FUNCTION(key) % map->capacity;
137 if (idx < 0)
138 {
139 idx += map->capacity;
140 }
141
142 HashLink *current = map->table[idx];
143
144 //hashMapContainsKey(HashMap* map, const char* key)
145 while (current != NULL) {
146 if (strcmp(current->key, key) == 0){
147 return ¤t->value; //value is not a pointer, return address
148 }
149 current = current->next;
150 }
151 return NULL;
152
153
154}
155
156/**
157 * Resizes the hash table to have a number of buckets equal to the given
158 * capacity (double of the old capacity). After allocating the new table,
159 * all of the links need to rehashed into it because the capacity has changed.
160 *
161 * Remember to free the old table and any old links if you use hashMapPut to
162 * rehash them.
163 *
164 * @param map
165 * @param capacity The new number of buckets.
166 */
167void resizeTable(HashMap* map, int capacity)
168{
169 // FIXME: implement
170 //**newtable
171 HashMap *newMap = hashMapNew(capacity);
172 hashMapInit(map, capacity);
173 HashLink *current;
174 for(int i = 0; i < hashMapCapacity(map); i++)
175 {
176 current = map->table[i];
177 while(current != NULL)
178 {
179 hashMapPut(newMap, current->key, current->value);
180 current = current->next;
181 }
182 }
183 hashMapCleanUp(map);
184 map->capacity = newMap->capacity;
185 map->table = newMap->table;
186 map->size = newMap->size;
187
188 newMap->table = 0;
189 free(newMap);
190}
191
192
193/**
194 * Updates the given key-value pair in the hash table. If a link with the given
195 * key already exists, this will just update the value and skip traversing. Otherwise, it will
196 * create a new link with the given key and value and add it to the table
197 * bucket's linked list. You can use hashLinkNew to create the link.
198 *
199 * Use HASH_FUNCTION(key) and the map's capacity to find the index of the
200 * correct linked list bucket.
201 *
202 * @param map
203 * @param key
204 * @param value
205 */
206void hashMapPut(HashMap* map, const char* key, int value)
207{
208 // FIXME: implement
209
210 int idx = HASH_FUNCTION(key) % map->capacity;
211
212 if(idx < 0)
213 {
214 idx += map->capacity;
215 }
216
217 if(map->table[idx] != NULL)
218 {
219 map->table[idx]->value = value;
220 map->size++;
221 if (hashMapTableLoad(map) >= (float) MAX_TABLE_LOAD) {
222 resizeTable(map, map->capacity*2);
223 }
224 return;
225 }
226 else {
227 //hashLinkNew(const char* key, int value, HashLink* next)
228 map->table[idx] = hashLinkNew(key, value, 0);
229 map->size++;
230 if (hashMapTableLoad(map) >= (float) MAX_TABLE_LOAD) {
231 resizeTable(map, map->capacity*2);
232 }
233 return;
234
235 } while(1){
236
237 if(strcmp(map->table[idx]->key, key) == 0) {
238 map->table[idx]->value=value;
239 return;
240 }
241 if (map->table[idx] == NULL){
242 //hashLinkNew(const char* key, int value, HashLink* next)
243 map->table[idx] = hashLinkNew(key, value, 0);
244 map->size++;
245 if (hashMapTableLoad(map) > (float) MAX_TABLE_LOAD) {
246 resizeTable(map, map->capacity*2);
247 }
248 return;
249
250 }
251 }
252
253
254}
255
256/**
257 * Removes and frees the link with the given key from the table. If no such link
258 * exists, this does nothing. Remember to search the entire linked list at the
259 * bucket. You can use hashLinkDelete to free the link.
260 * @param map
261 * @param key
262 */
263void hashMapRemove(HashMap* map, const char* key)
264{
265 // FIXME: implement
266 assert(map != 0);
267 assert(map->table > 0);
268 //int hashFunction1(const char* key)
269 //calculate hash
270 int idx = HASH_FUNCTION(key) % map->capacity;
271
272 if (idx < 0)
273 {
274 idx += map->capacity;
275 }
276 //see if element exists in bucket
277 HashLink *current = map->table[idx];
278 HashLink *prev = map->table[idx];
279
280 if (current != NULL) {
281 if(strcmp(current->key, key) == 0) {
282 HashLink *next = current->next;
283 hashLinkDelete(current);
284 map->table[idx] = next;
285 map->size--;
286 } else {
287 prev = current;
288 current = current->next;
289 }
290 }
291
292 while (current)
293 {
294 if(strcmp(current->key, key) == 0)
295 {
296 prev->next = current->next;
297 hashLinkDelete(current);
298 map->size--;
299 return;
300 } else {
301 prev = current;
302 current = current->next;
303 }
304 }
305
306
307
308}
309
310/**
311 * Returns 1 if a link with the given key is in the table and 0 otherwise.
312 *
313 * Use HASH_FUNCTION(key) and the map's capacity to find the index of the
314 * correct linked list bucket. Also make sure to search the entire list.
315 *
316 * @param map
317 * @param key
318 * @return 1 if the key is found, 0 otherwise.
319 */
320int hashMapContainsKey(HashMap* map, const char* key)
321{
322 // FIXME: implement
323 int idx = HASH_FUNCTION(key) % map->capacity;
324
325 if (idx < 0) {
326 idx += map->capacity;
327 }
328 while (map->table[idx] != NULL) {
329 if (strcmp(map->table[idx]->key, key) == 0)
330 {
331 return 1;
332 }
333 else {
334 idx++;
335 if (idx >= map->size) {
336 idx = 0;
337 }
338 }
339 } return NULL;
340
341}
342
343/**
344 * Returns the number of links in the table.
345 * @param map
346 * @return Number of links in the table.
347 */
348int hashMapSize(HashMap* map)
349{
350 // FIXME: implement
351 return map->size;
352}
353
354/**
355 * Returns the number of buckets in the table.
356 * @param map
357 * @return Number of buckets in the table.
358 */
359int hashMapCapacity(HashMap* map)
360{
361// FIXME: implement
362 return map->capacity;
363}
364
365/**
366 * Returns the number of table buckets without any links.
367 * @param map
368 * @return Number of empty buckets.
369 */
370int hashMapEmptyBuckets(HashMap* map)
371{
372 // FIXME: implement
373 int empty = 0;
374 for (int i = 0; i < map->capacity; i++)
375 {
376 if (map->table[i] == 0)
377 {
378 empty++;
379 }
380 }
381 return empty;
382}
383
384/**
385 * Returns the ratio of (number of links) / (number of buckets) in the table.
386 * Remember that the buckets are linked lists, so this ratio tells you nothing
387 * about the number of empty buckets. Remember also that the load is a floating
388 * point number, so don't do integer division.
389 * @param map
390 * @return Table load.
391 */
392float hashMapTableLoad(HashMap* map)
393{
394 // FIXME: implement
395 if(map->capacity != 0) {
396 float load = map->size / map->capacity;
397
398 return load;
399 } else
400 return 0;
401}
402
403/**
404 * Prints all the links in each of the buckets in the table.
405 * @param map
406 */
407void hashMapPrint(HashMap* map)
408{
409 // FIXME: implement
410 struct HashLink *print;
411
412 for (int i = 0; i < map->capacity; i++)
413 {
414 print = map->table[i];
415 if (print != 0) {
416 printf("\nBucket index: %d -> ", i);
417 }
418 while (print != 0)
419 {
420 printf("Key: %s", print->key);
421 printf(" -> ");
422 printf("Value: %d", print->value);
423 print = print->next;
424 }
425 }
426
427}