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