1/*
2 * ν΄μ ν
μ΄λΈ (Hash Table)
3 * Hash Functions, Chaining, Open Addressing
4 *
5 * λΉ λ₯Έ κ²μ, μ½μ
, μμ λ₯Ό μν μλ£κ΅¬μ‘°μ
λλ€.
6 */
7
8#include <stdio.h>
9#include <stdlib.h>
10#include <string.h>
11#include <stdbool.h>
12
13#define TABLE_SIZE 101
14#define DELETED ((void*)-1)
15
16/* =============================================================================
17 * 1. ν΄μ ν¨μλ€
18 * ============================================================================= */
19
20/* λλ¨Έμ§ μ°μ° ν΄μ */
21unsigned int hash_mod(int key, int size) {
22 return ((key % size) + size) % size;
23}
24
25/* λ¬Έμμ΄ ν΄μ (djb2) */
26unsigned int hash_string(const char* str, int size) {
27 unsigned long hash = 5381;
28 int c;
29 while ((c = *str++)) {
30 hash = ((hash << 5) + hash) + c;
31 }
32 return hash % size;
33}
34
35/* λ€νμ ν΄μ */
36unsigned int hash_polynomial(const char* str, int size) {
37 unsigned long hash = 0;
38 unsigned long p_pow = 1;
39 const unsigned long p = 31;
40 while (*str) {
41 hash = (hash + (*str - 'a' + 1) * p_pow) % size;
42 p_pow = (p_pow * p) % size;
43 str++;
44 }
45 return hash;
46}
47
48/* =============================================================================
49 * 2. 체μ΄λ ν΄μ ν
μ΄λΈ
50 * ============================================================================= */
51
52typedef struct ChainNode {
53 char* key;
54 int value;
55 struct ChainNode* next;
56} ChainNode;
57
58typedef struct {
59 ChainNode** buckets;
60 int size;
61 int count;
62} ChainHashTable;
63
64ChainHashTable* chain_create(int size) {
65 ChainHashTable* ht = malloc(sizeof(ChainHashTable));
66 ht->buckets = calloc(size, sizeof(ChainNode*));
67 ht->size = size;
68 ht->count = 0;
69 return ht;
70}
71
72void chain_insert(ChainHashTable* ht, const char* key, int value) {
73 unsigned int idx = hash_string(key, ht->size);
74
75 /* κΈ°μ‘΄ ν€ κ²μ */
76 ChainNode* node = ht->buckets[idx];
77 while (node) {
78 if (strcmp(node->key, key) == 0) {
79 node->value = value;
80 return;
81 }
82 node = node->next;
83 }
84
85 /* μ λ
Έλ μ½μ
*/
86 ChainNode* new_node = malloc(sizeof(ChainNode));
87 new_node->key = strdup(key);
88 new_node->value = value;
89 new_node->next = ht->buckets[idx];
90 ht->buckets[idx] = new_node;
91 ht->count++;
92}
93
94int chain_get(ChainHashTable* ht, const char* key, int* found) {
95 unsigned int idx = hash_string(key, ht->size);
96 ChainNode* node = ht->buckets[idx];
97
98 while (node) {
99 if (strcmp(node->key, key) == 0) {
100 *found = 1;
101 return node->value;
102 }
103 node = node->next;
104 }
105
106 *found = 0;
107 return 0;
108}
109
110void chain_delete(ChainHashTable* ht, const char* key) {
111 unsigned int idx = hash_string(key, ht->size);
112 ChainNode* node = ht->buckets[idx];
113 ChainNode* prev = NULL;
114
115 while (node) {
116 if (strcmp(node->key, key) == 0) {
117 if (prev) {
118 prev->next = node->next;
119 } else {
120 ht->buckets[idx] = node->next;
121 }
122 free(node->key);
123 free(node);
124 ht->count--;
125 return;
126 }
127 prev = node;
128 node = node->next;
129 }
130}
131
132void chain_free(ChainHashTable* ht) {
133 for (int i = 0; i < ht->size; i++) {
134 ChainNode* node = ht->buckets[i];
135 while (node) {
136 ChainNode* next = node->next;
137 free(node->key);
138 free(node);
139 node = next;
140 }
141 }
142 free(ht->buckets);
143 free(ht);
144}
145
146/* =============================================================================
147 * 3. μ€ν μ΄λλ μ± (μ ν νμ¬)
148 * ============================================================================= */
149
150typedef struct {
151 int* keys;
152 int* values;
153 bool* occupied;
154 bool* deleted;
155 int size;
156 int count;
157} LinearHashTable;
158
159LinearHashTable* linear_create(int size) {
160 LinearHashTable* ht = malloc(sizeof(LinearHashTable));
161 ht->keys = malloc(size * sizeof(int));
162 ht->values = malloc(size * sizeof(int));
163 ht->occupied = calloc(size, sizeof(bool));
164 ht->deleted = calloc(size, sizeof(bool));
165 ht->size = size;
166 ht->count = 0;
167 return ht;
168}
169
170void linear_insert(LinearHashTable* ht, int key, int value) {
171 if (ht->count >= ht->size * 0.7) {
172 printf(" Warning: Load factor too high!\n");
173 return;
174 }
175
176 unsigned int idx = hash_mod(key, ht->size);
177
178 while (ht->occupied[idx] && !ht->deleted[idx] && ht->keys[idx] != key) {
179 idx = (idx + 1) % ht->size;
180 }
181
182 if (!ht->occupied[idx] || ht->deleted[idx]) {
183 ht->count++;
184 }
185
186 ht->keys[idx] = key;
187 ht->values[idx] = value;
188 ht->occupied[idx] = true;
189 ht->deleted[idx] = false;
190}
191
192int linear_get(LinearHashTable* ht, int key, int* found) {
193 unsigned int idx = hash_mod(key, ht->size);
194 int start = idx;
195
196 while (ht->occupied[idx]) {
197 if (!ht->deleted[idx] && ht->keys[idx] == key) {
198 *found = 1;
199 return ht->values[idx];
200 }
201 idx = (idx + 1) % ht->size;
202 if (idx == start) break;
203 }
204
205 *found = 0;
206 return 0;
207}
208
209void linear_delete(LinearHashTable* ht, int key) {
210 unsigned int idx = hash_mod(key, ht->size);
211 int start = idx;
212
213 while (ht->occupied[idx]) {
214 if (!ht->deleted[idx] && ht->keys[idx] == key) {
215 ht->deleted[idx] = true;
216 ht->count--;
217 return;
218 }
219 idx = (idx + 1) % ht->size;
220 if (idx == start) break;
221 }
222}
223
224void linear_free(LinearHashTable* ht) {
225 free(ht->keys);
226 free(ht->values);
227 free(ht->occupied);
228 free(ht->deleted);
229 free(ht);
230}
231
232/* =============================================================================
233 * 4. μ΄μ€ ν΄μ±
234 * ============================================================================= */
235
236typedef struct {
237 int* keys;
238 int* values;
239 bool* occupied;
240 bool* deleted;
241 int size;
242 int count;
243} DoubleHashTable;
244
245unsigned int hash2(int key, int size) {
246 return 7 - (key % 7); /* 0μ΄ μλ κ° λ³΄μ₯ */
247}
248
249DoubleHashTable* double_create(int size) {
250 DoubleHashTable* ht = malloc(sizeof(DoubleHashTable));
251 ht->keys = malloc(size * sizeof(int));
252 ht->values = malloc(size * sizeof(int));
253 ht->occupied = calloc(size, sizeof(bool));
254 ht->deleted = calloc(size, sizeof(bool));
255 ht->size = size;
256 ht->count = 0;
257 return ht;
258}
259
260void double_insert(DoubleHashTable* ht, int key, int value) {
261 unsigned int idx = hash_mod(key, ht->size);
262 unsigned int step = hash2(key, ht->size);
263
264 while (ht->occupied[idx] && !ht->deleted[idx] && ht->keys[idx] != key) {
265 idx = (idx + step) % ht->size;
266 }
267
268 if (!ht->occupied[idx] || ht->deleted[idx]) {
269 ht->count++;
270 }
271
272 ht->keys[idx] = key;
273 ht->values[idx] = value;
274 ht->occupied[idx] = true;
275 ht->deleted[idx] = false;
276}
277
278int double_get(DoubleHashTable* ht, int key, int* found) {
279 unsigned int idx = hash_mod(key, ht->size);
280 unsigned int step = hash2(key, ht->size);
281 int start = idx;
282
283 while (ht->occupied[idx]) {
284 if (!ht->deleted[idx] && ht->keys[idx] == key) {
285 *found = 1;
286 return ht->values[idx];
287 }
288 idx = (idx + step) % ht->size;
289 if (idx == start) break;
290 }
291
292 *found = 0;
293 return 0;
294}
295
296void double_free(DoubleHashTable* ht) {
297 free(ht->keys);
298 free(ht->values);
299 free(ht->occupied);
300 free(ht->deleted);
301 free(ht);
302}
303
304/* =============================================================================
305 * 5. μ€μ : Two Sum
306 * ============================================================================= */
307
308int* two_sum(int nums[], int n, int target, int* result_size) {
309 ChainHashTable* ht = chain_create(n * 2);
310 int* result = malloc(2 * sizeof(int));
311 *result_size = 0;
312
313 for (int i = 0; i < n; i++) {
314 int complement = target - nums[i];
315 int found;
316 int idx = chain_get(ht, (char[]){complement + '0', '\0'}, &found);
317
318 if (found) {
319 result[0] = idx;
320 result[1] = i;
321 *result_size = 2;
322 chain_free(ht);
323 return result;
324 }
325
326 /* κ°λ¨ν ν€ λ³ν (μ€μ λ‘λ intλ₯Ό λ¬Έμμ΄λ‘ λ³νν΄μΌ ν¨) */
327 char key[20];
328 sprintf(key, "%d", nums[i]);
329 chain_insert(ht, key, i);
330 }
331
332 chain_free(ht);
333 free(result);
334 return NULL;
335}
336
337/* =============================================================================
338 * 6. μ€μ : λΉλ μΉ΄μ΄νΈ
339 * ============================================================================= */
340
341void count_frequency(int arr[], int n) {
342 LinearHashTable* ht = linear_create(n * 2 + 1);
343
344 for (int i = 0; i < n; i++) {
345 int found;
346 int count = linear_get(ht, arr[i], &found);
347 linear_insert(ht, arr[i], found ? count + 1 : 1);
348 }
349
350 printf(" λΉλ:\n");
351 for (int i = 0; i < ht->size; i++) {
352 if (ht->occupied[i] && !ht->deleted[i]) {
353 printf(" %d: %d\n", ht->keys[i], ht->values[i]);
354 }
355 }
356
357 linear_free(ht);
358}
359
360/* =============================================================================
361 * ν
μ€νΈ
362 * ============================================================================= */
363
364int main(void) {
365 printf("============================================================\n");
366 printf("ν΄μ ν
μ΄λΈ (Hash Table) μμ \n");
367 printf("============================================================\n");
368
369 /* 1. ν΄μ ν¨μ */
370 printf("\n[1] ν΄μ ν¨μ\n");
371 printf(" hash_mod(42, 101) = %u\n", hash_mod(42, TABLE_SIZE));
372 printf(" hash_string(\"hello\", 101) = %u\n", hash_string("hello", TABLE_SIZE));
373 printf(" hash_string(\"world\", 101) = %u\n", hash_string("world", TABLE_SIZE));
374
375 /* 2. 체μ΄λ ν΄μ ν
μ΄λΈ */
376 printf("\n[2] 체μ΄λ ν΄μ ν
μ΄λΈ\n");
377 ChainHashTable* chain_ht = chain_create(TABLE_SIZE);
378 chain_insert(chain_ht, "apple", 100);
379 chain_insert(chain_ht, "banana", 200);
380 chain_insert(chain_ht, "cherry", 300);
381
382 int found;
383 printf(" apple: %d\n", chain_get(chain_ht, "apple", &found));
384 printf(" banana: %d\n", chain_get(chain_ht, "banana", &found));
385
386 chain_delete(chain_ht, "banana");
387 chain_get(chain_ht, "banana", &found);
388 printf(" banana μμ ν: %s\n", found ? "found" : "not found");
389 chain_free(chain_ht);
390
391 /* 3. μ ν νμ¬ */
392 printf("\n[3] μ ν νμ¬ (Linear Probing)\n");
393 LinearHashTable* linear_ht = linear_create(TABLE_SIZE);
394 linear_insert(linear_ht, 10, 100);
395 linear_insert(linear_ht, 111, 200); /* μΆ©λ: 10 % 101 = 10, 111 % 101 = 10 */
396 linear_insert(linear_ht, 212, 300);
397
398 printf(" 10: %d\n", linear_get(linear_ht, 10, &found));
399 printf(" 111: %d\n", linear_get(linear_ht, 111, &found));
400 printf(" 212: %d\n", linear_get(linear_ht, 212, &found));
401 linear_free(linear_ht);
402
403 /* 4. μ΄μ€ ν΄μ± */
404 printf("\n[4] μ΄μ€ ν΄μ± (Double Hashing)\n");
405 DoubleHashTable* double_ht = double_create(TABLE_SIZE);
406 double_insert(double_ht, 10, 100);
407 double_insert(double_ht, 111, 200);
408 double_insert(double_ht, 212, 300);
409
410 printf(" 10: %d\n", double_get(double_ht, 10, &found));
411 printf(" 111: %d\n", double_get(double_ht, 111, &found));
412 double_free(double_ht);
413
414 /* 5. λΉλ μΉ΄μ΄νΈ */
415 printf("\n[5] λΉλ μΉ΄μ΄νΈ\n");
416 int arr[] = {1, 2, 3, 1, 2, 1, 4, 2};
417 printf(" λ°°μ΄: [1,2,3,1,2,1,4,2]\n");
418 count_frequency(arr, 8);
419
420 /* 6. ν΄μ ν
μ΄λΈ λΉκ΅ */
421 printf("\n[6] μΆ©λ ν΄κ²° λ°©λ² λΉκ΅\n");
422 printf(" | λ°©λ² | μ₯μ | λ¨μ |\n");
423 printf(" |------------|-------------------|-------------------|\n");
424 printf(" | 체μ΄λ | μμ μ©μ΄ | λ©λͺ¨λ¦¬ μ€λ²ν€λ |\n");
425 printf(" | μ ν νμ¬ | μΊμ μΉνμ | ν΄λ¬μ€ν°λ§ |\n");
426 printf(" | μ΄μ€ ν΄μ± | ν΄λ¬μ€ν°λ§ κ°μ | ν΄μ κ³μ° λΉμ© |\n");
427
428 printf("\n============================================================\n");
429
430 return 0;
431}