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