· 8 years ago · Nov 22, 2017, 05:40 PM
1#include <stdlib.h>
2#include <stdio.h>
3#include <string.h>
4#include <assert.h>
5#include <math.h>
6#include "hashMap.h"
7
8struct hashLink {
9 KeyType key; /*the key is what you use to look up a hashLink*/
10 ValueType value; /*the value stored with the hashLink, a pointer to int in the case of concordance*/
11 struct hashLink * next; /*notice how these are like linked list nodes*/
12};
13typedef struct hashLink hashLink;
14
15struct hashMap {
16 hashLink ** table; /*array of pointers to hashLinks*/
17 int tableSize; /*number of buckets in the table*/
18 int count; /*number of hashLinks in the table*/
19};
20typedef struct hashMap hashMap;
21
22/*the first hashing function you can use*/
23int stringHash1(char * str)
24{
25 int i;
26 int r = 0;
27 for (i = 0; str[i] != '\0'; i++)
28 r += str[i];
29 return r;
30}
31
32/*the second hashing function you can use*/
33int stringHash2(char * str)
34{
35 int i;
36 int r = 0;
37 for (i = 0; str[i] != '\0'; i++)
38 r += (i+1) * str[i]; // the difference between 1&2
39 return r;
40}
41
42/* initialize the supplied hashMap struct*/
43void _initMap (struct hashMap * ht, int tableSize)
44{
45 int index;
46 if(ht == NULL)
47 return;
48 ht->table = (hashLink**)malloc(sizeof(hashLink*) * tableSize);
49 ht->tableSize = tableSize;
50 ht->count = 0;
51 for(index = 0; index < tableSize; index++)
52 ht->table[index] = NULL;
53}
54
55/* allocate memory and initialize a hash map*/
56hashMap *createMap(int tableSize) {
57 assert(tableSize > 0);
58 hashMap *ht;
59 ht = malloc(sizeof(hashMap));
60 assert(ht != 0);
61 _initMap(ht, tableSize);
62 return ht;
63}
64
65/*
66 Free all memory used by the buckets.
67 Note: Before freeing up a hashLink, free the memory occupied by key and value
68 */
69 void _freeMap (struct hashMap * ht)
70 {
71 int i;
72 struct hashLink *temp;
73 struct hashLink *temp2;
74 for(i=0; i<ht->tableSize; i++){
75 temp=ht->table[i];
76 while(temp!=0){
77 temp2=temp->next;
78 free(temp->key);
79 free(temp->value); /* also free the memory pointed by value*/
80 free(temp);
81 temp=temp2;
82 }
83 }
84 free(ht->table);
85 ht->count=0;
86 ht->table=0;
87 ht->tableSize=0;
88 }
89
90/* Deallocate buckets and the hash map.*/
91void deleteMap(hashMap *ht) {
92 assert(ht!= 0);
93 /* Free all memory used by the buckets */
94 _freeMap(ht);
95 /* free the hashMap struct */
96 free(ht);
97}
98
99int isItPrime(int n){
100 for (int i = 2; i <= sqrt(n); i++){
101 if (n%i == 0){
102 return 0;
103 }
104 }
105 return 1;
106}
107
108//"probably prime" bc some values will fall through sieve due to rounding
109int nextPrime(int n){
110 n++;
111 if (n == 0 || n == 1){
112 return 2;
113 }
114 if (n == 2){
115 return 3;
116 }
117 else if (n == 3){
118 return 5;
119 }
120 else if (isItPrime(n) == 1){
121 return n;
122 }
123 return nextPrime(n);
124}
125
126/*
127Resizes the hash table to be the size newTableSize
128Remember what you had to do for the dynamic array!
129This isn't elegant. Values have to be moved.
130*/
131void _setTableSize(struct hashMap * ht, int newTableSize)
132{
133 /*TODO*/
134 struct hashMap *tempHash = createMap(nextPrime(newTableSize));
135 for (int i = 0; i <= ht->tableSize; i++){
136
137 hashLink* currentLink = ht->table[i];
138 if (ht->table[i] == NULL){
139 continue;
140 }
141 while (currentLink != NULL){
142 insertMap(tempHash, currentLink->key, currentLink->value);
143 currentLink = currentLink->next;
144 }
145 }
146
147 _freeMap(ht);
148 ht = tempHash;
149 _freeMap(tempHash);
150 printf("ey fuckface, the new table size is%i\n", size(ht));
151}
152
153/*
154 insert the following values into a hashLink, you must create this hashLink but
155 only after you confirm that this key does not already exist in the table. For example, you
156 cannot have two hashLinks for the word "taco".
157
158 if a hashLink already exists in the table for the key provided you should
159 replace that hashLink--this requires freeing up the old memory pointed by hashLink->value
160 and then pointing hashLink->value to value v.
161
162 also, you must monitor the load factor and resize when the load factor is greater than
163 or equal LOAD_FACTOR_THRESHOLD (defined in hashMap.h).
164 */
165void insertMap (struct hashMap * ht, KeyType k, ValueType v)
166{
167 /*TODO*/
168int idx;
169struct hashLink* put = malloc(sizeof(struct hashLink));
170 put->next = 0;
171 put->key = k;
172 put->value = v;
173
174 //check to see if map contains key. If so, remove it.
175 if(containsKey(ht, k)){
176 removeKey(ht, k);
177 }
178
179 idx = stringHash2(k) % ht->tableSize;
180
181 if(idx < 0){
182 idx += ht->tableSize;
183 }
184 if(!ht->table[idx]){
185 ht->table[idx] = put;
186 } else {
187 struct hashLink* cur = ht->table[idx];
188 while(cur->next){
189 cur = cur->next;
190 }
191 cur->next = put;
192 }
193 ht->count++;
194}
195
196/*
197 this returns the value (which is void*) stored in a hashLink specified by the key k.
198
199 if the user supplies the key "taco" you should find taco in the hashTable, then
200 return the value member of the hashLink that represents taco.
201
202 if the supplied key is not in the hashtable return NULL.
203 */
204ValueType atMap (struct hashMap * ht, KeyType k)
205{
206 /*TODO*/
207 int idx = stringHash2(k)%ht->tableSize;
208 if(idx < 0){
209 idx += ht->tableSize;
210 }
211 if(ht->table[idx]!=NULL){
212 struct hashLink *check = (hashLink * )malloc(sizeof(hashLink));
213 check = ht->table[idx];
214 while(check != NULL){
215 if(*(check->key) == *k){
216 return check->value;
217 }
218 check = check->next;
219 }
220 return NULL;
221 }
222
223else return NULL;
224}
225
226/*
227 a simple yes/no if the key is in the hashtable.
228 0 is no, all other values are yes.
229 */
230int containsKey (struct hashMap * ht, KeyType k)
231{
232 /*TODO*/
233 int idx = stringHash2(k)%ht->tableSize;
234 if(idx < 0){
235 idx += ht->tableSize;
236 }
237 if(ht->table[idx]!=NULL){
238 struct hashLink *cur = (hashLink *)malloc(sizeof(hashLink));
239 cur = ht->table[idx];
240 while(cur!=NULL){
241 if(*(cur->key)==*k){
242 return 1;
243 }
244 cur=cur->next;
245 }
246 return 0;
247 }
248 else return 0;
249}
250
251/*
252 find the hashlink for the supplied key and remove it, also freeing the memory
253 for that hashlink. it is not an error to be unable to find the hashlink, if it
254 cannot be found do nothing (or print a message) but do not use an assert which
255 will end your program.
256 */
257void removeKey (struct hashMap * ht, KeyType k)
258{
259 /*TODO*/
260if (containsKey(ht, k) == 1){
261
262}
263}
264
265/*
266 returns the number of hashLinks in the table
267 */
268int size (struct hashMap *ht)
269{
270 /*TODO*/
271 return(ht->count);
272
273}
274
275/*
276 returns the number of buckets in the table
277 */
278int capacity(struct hashMap *ht)
279{
280 /*TODO*/
281 return(ht->tableSize);
282}
283
284/*
285 returns the number of empty buckets in the table, these are buckets which have
286 no hashlinks hanging off of them.
287 */
288int emptyBuckets(struct hashMap *ht)
289{
290 /*TODO*/
291 int empBuckets = 0;
292 int i;
293 for(i=0; i<ht->tableSize; i++) {
294 if(ht->table[i] == NULL)
295 empBuckets++;
296 }
297 return empBuckets;
298}
299
300/*
301 returns the ratio of: (number of hashlinks) / (number of buckets)
302
303 this value can range anywhere from zero (an empty table) to more then 1, which
304 would mean that there are more hashlinks then buckets (but remember hashlinks
305 are like linked list nodes so they can hang from each other)
306 */
307float tableLoad(struct hashMap *ht)
308{
309 /*TODO*/
310 return((float)ht->count/ht->tableSize);
311}
312
313/* print the hashMap */
314void printMap (struct hashMap * ht)
315{
316 int i;
317 struct hashLink *temp;
318 for(i = 0;i < capacity(ht); i++){
319 temp = ht->table[i];
320 if(temp != 0) {
321 printf("\nBucket Index %d -> ", i);
322 }
323 while(temp != 0){
324 printf("Key:%s|", temp->key);
325 printValue(temp->value);
326 printf(" -> ");
327 temp=temp->next;
328 }
329 }
330}