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