1/*
2 * hash_linear_probing.c
3 * μ ν νμ¬(Linear Probing)λ₯Ό μ΄μ©ν μ€ν μ΄λλ μ± ν΄μ ν
μ΄λΈ
4 *
5 * μ ν νμ¬ λ°©μ:
6 * - μΆ©λ λ°μ μ λ€μ λΉ μ¬λ‘―μ μμ°¨μ μΌλ‘ νμ
7 * - μ₯μ : μΊμ ν¨μ¨ μ’μ, μΆκ° λ©λͺ¨λ¦¬ λΆνμ
8 * - λ¨μ : ν΄λ¬μ€ν°λ§ νμ, μμ μ²λ¦¬ 볡μ‘
9 */
10
11#include <stdio.h>
12#include <stdlib.h>
13#include <string.h>
14#include <stdbool.h>
15
16#define TABLE_SIZE 20
17#define KEY_SIZE 50
18#define VALUE_SIZE 100
19
20// μ¬λ‘― μν
21typedef enum {
22 EMPTY, // λΉμ΄μμ (ν λ²λ μ¬μ© μ λ¨)
23 OCCUPIED, // μ¬μ© μ€
24 DELETED // μμ λ¨ (νμ μ 건λλ°μ§ μμ)
25} SlotStatus;
26
27// μ¬λ‘― ꡬ쑰체
28typedef struct {
29 char key[KEY_SIZE];
30 char value[VALUE_SIZE];
31 SlotStatus status;
32} Slot;
33
34// ν΄μ ν
μ΄λΈ ꡬ쑰체
35typedef struct {
36 Slot slots[TABLE_SIZE];
37 int count; // νμ¬ μ μ₯λ νλͺ© μ (OCCUPIED)
38 int probes; // μ΄ νμ¬ νμ
39 int collisions; // μΆ©λ νμ
40} HashTable;
41
42// djb2 ν΄μ ν¨μ
43unsigned int hash(const char *key) {
44 unsigned int hash = 5381;
45 int c;
46 while ((c = *key++)) {
47 hash = ((hash << 5) + hash) + c;
48 }
49 return hash % TABLE_SIZE;
50}
51
52// ν΄μ ν
μ΄λΈ μμ±
53HashTable* ht_create(void) {
54 HashTable *ht = malloc(sizeof(HashTable));
55 if (!ht) {
56 fprintf(stderr, "λ©λͺ¨λ¦¬ ν λΉ μ€ν¨\n");
57 return NULL;
58 }
59
60 // λͺ¨λ μ¬λ‘― μ΄κΈ°ν
61 for (int i = 0; i < TABLE_SIZE; i++) {
62 ht->slots[i].status = EMPTY;
63 ht->slots[i].key[0] = '\0';
64 ht->slots[i].value[0] = '\0';
65 }
66
67 ht->count = 0;
68 ht->probes = 0;
69 ht->collisions = 0;
70
71 return ht;
72}
73
74// ν΄μ ν
μ΄λΈ ν΄μ
75void ht_destroy(HashTable *ht) {
76 free(ht);
77}
78
79// μ½μ
λλ μμ
80bool ht_set(HashTable *ht, const char *key, const char *value) {
81 if (!ht || !key || !value) return false;
82
83 // ν
μ΄λΈμ΄ κ°λ μ°¬ κ²½μ°
84 if (ht->count >= TABLE_SIZE) {
85 fprintf(stderr, "ν΄μ ν
μ΄λΈμ΄ κ°λ μ°Όμ΅λλ€!\n");
86 return false;
87 }
88
89 unsigned int index = hash(key);
90 unsigned int original_index = index;
91 int probe_count = 0;
92
93 // μ ν νμ¬
94 do {
95 probe_count++;
96
97 // 1. λΉ μ¬λ‘― λλ μμ λ μ¬λ‘― β μλ‘ μ½μ
98 if (ht->slots[index].status != OCCUPIED) {
99 if (probe_count > 1) {
100 ht->collisions++; // μΆ©λ λ°μ
101 }
102
103 strncpy(ht->slots[index].key, key, KEY_SIZE - 1);
104 ht->slots[index].key[KEY_SIZE - 1] = '\0';
105 strncpy(ht->slots[index].value, value, VALUE_SIZE - 1);
106 ht->slots[index].value[VALUE_SIZE - 1] = '\0';
107 ht->slots[index].status = OCCUPIED;
108
109 ht->count++;
110 ht->probes += probe_count;
111 return true;
112 }
113
114 // 2. κ°μ ν€ λ°κ²¬ β κ° μ
λ°μ΄νΈ
115 if (strcmp(ht->slots[index].key, key) == 0) {
116 strncpy(ht->slots[index].value, value, VALUE_SIZE - 1);
117 ht->slots[index].value[VALUE_SIZE - 1] = '\0';
118 ht->probes += probe_count;
119 return true;
120 }
121
122 // 3. λ€μ μ¬λ‘―μΌλ‘
123 index = (index + 1) % TABLE_SIZE;
124
125 } while (index != original_index);
126
127 // λͺ¨λ μ¬λ‘― νμνμ§λ§ μ€ν¨ (μ΄λ‘ μ λλ¬ λΆκ°)
128 return false;
129}
130
131// κ²μ
132char* ht_get(HashTable *ht, const char *key) {
133 if (!ht || !key) return NULL;
134
135 unsigned int index = hash(key);
136 unsigned int original_index = index;
137
138 // μ ν νμ¬
139 do {
140 // EMPTY λ°κ²¬ β ν€κ° μμ (νμ μ’
λ£)
141 if (ht->slots[index].status == EMPTY) {
142 return NULL;
143 }
144
145 // OCCUPIEDμ΄κ³ ν€κ° μΌμΉ β μ°Ύμ!
146 if (ht->slots[index].status == OCCUPIED &&
147 strcmp(ht->slots[index].key, key) == 0) {
148 return ht->slots[index].value;
149 }
150
151 // DELETED λλ λ€λ₯Έ ν€ β κ³μ νμ
152 index = (index + 1) % TABLE_SIZE;
153
154 } while (index != original_index);
155
156 return NULL; // μ°Ύμ§ λͺ»ν¨
157}
158
159// μμ
160bool ht_delete(HashTable *ht, const char *key) {
161 if (!ht || !key) return false;
162
163 unsigned int index = hash(key);
164 unsigned int original_index = index;
165
166 do {
167 // EMPTY λ°κ²¬ β ν€κ° μμ
168 if (ht->slots[index].status == EMPTY) {
169 return false;
170 }
171
172 // OCCUPIEDμ΄κ³ ν€κ° μΌμΉ β μμ
173 if (ht->slots[index].status == OCCUPIED &&
174 strcmp(ht->slots[index].key, key) == 0) {
175
176 // EMPTYκ° μλ DELETEDλ‘ νμ (μ€μ!)
177 // μ΄μ : νμ 체μΈμ λμ§ μκΈ° μν΄
178 ht->slots[index].status = DELETED;
179 ht->count--;
180 return true;
181 }
182
183 index = (index + 1) % TABLE_SIZE;
184
185 } while (index != original_index);
186
187 return false; // μ°Ύμ§ λͺ»ν¨
188}
189
190// ν΄μ ν
μ΄λΈ μΆλ ₯
191void ht_print(HashTable *ht) {
192 if (!ht) return;
193
194 printf("\nββββββββββββββββββββββββββββββββββββββββββββββ\n");
195 printf("β ν΄μ ν
μ΄λΈ μν (μ ν νμ¬) β\n");
196 printf("β βββββββββββββββββββββββββββββββββββββββββββββ£\n");
197 printf("β νλͺ© κ°μ: %-5d / %-5d β\n",
198 ht->count, TABLE_SIZE);
199 printf("β λ‘λ ν©ν°: %.2f β\n",
200 (double)ht->count / TABLE_SIZE);
201 printf("β μΆ©λ νμ: %-5d β\n", ht->collisions);
202 printf("β νκ· νμ¬: %.2f β\n",
203 ht->count > 0 ? (double)ht->probes / ht->count : 0.0);
204 printf("ββββββββββββββββββββββββββββββββββββββββββββββ\n\n");
205
206 for (int i = 0; i < TABLE_SIZE; i++) {
207 printf("[%2d] ", i);
208
209 switch (ht->slots[i].status) {
210 case EMPTY:
211 printf("(λΉμ΄μμ)\n");
212 break;
213
214 case DELETED:
215 printf("(μμ λ¨) [μ΄μ ν€: %s]\n",
216 ht->slots[i].key[0] ? ht->slots[i].key : "?");
217 break;
218
219 case OCCUPIED: {
220 unsigned int original_hash = hash(ht->slots[i].key);
221 if (original_hash == (unsigned int)i) {
222 printf("\"%s\" : \"%s\" β\n",
223 ht->slots[i].key, ht->slots[i].value);
224 } else {
225 printf("\"%s\" : \"%s\" (μλ: [%u], μΆ©λ)\n",
226 ht->slots[i].key, ht->slots[i].value, original_hash);
227 }
228 break;
229 }
230 }
231 }
232}
233
234// ν΄λ¬μ€ν°λ§ λΆμ
235void analyze_clustering(HashTable *ht) {
236 printf("\n=== ν΄λ¬μ€ν°λ§ λΆμ ===\n\n");
237
238 int max_cluster = 0;
239 int current_cluster = 0;
240 int num_clusters = 0;
241
242 for (int i = 0; i < TABLE_SIZE; i++) {
243 if (ht->slots[i].status == OCCUPIED) {
244 current_cluster++;
245 } else {
246 if (current_cluster > 0) {
247 num_clusters++;
248 if (current_cluster > max_cluster) {
249 max_cluster = current_cluster;
250 }
251 }
252 current_cluster = 0;
253 }
254 }
255
256 // λ§μ§λ§ ν΄λ¬μ€ν° μ²λ¦¬
257 if (current_cluster > 0) {
258 num_clusters++;
259 if (current_cluster > max_cluster) {
260 max_cluster = current_cluster;
261 }
262 }
263
264 printf("ν΄λ¬μ€ν° κ°μ: %d\n", num_clusters);
265 printf("μ΅λ ν΄λ¬μ€ν°: %dκ° μ°μ\n", max_cluster);
266
267 // μκ°ν
268 printf("\nν΄λ¬μ€ν° μκ°ν:\n");
269 printf("[");
270 for (int i = 0; i < TABLE_SIZE; i++) {
271 if (ht->slots[i].status == OCCUPIED) {
272 printf("β");
273 } else if (ht->slots[i].status == DELETED) {
274 printf("β");
275 } else {
276 printf(" ");
277 }
278 }
279 printf("]\n");
280 printf("β: μ¬μ©μ€ β: μμ λ¨ (곡백): λΉμ΄μμ\n");
281}
282
283// μ±λ₯ ν
μ€νΈ
284void performance_test(void) {
285 printf("\nββββββββββββββββββββββββββββββββββββββββββββββ\n");
286 printf("β λ‘λ ν©ν°λ³ μ±λ₯ λΉκ΅ β\n");
287 printf("ββββββββββββββββββββββββββββββββββββββββββββββ\n\n");
288
289 int test_sizes[] = {5, 10, 15, 18}; // 25%, 50%, 75%, 90%
290
291 printf("λ‘λ ν©ν° | νκ· νμ¬ | μΆ©λ νμ\n");
292 printf("-----------|-----------|----------\n");
293
294 for (int t = 0; t < 4; t++) {
295 HashTable *ht = ht_create();
296 int n = test_sizes[t];
297
298 // ν
μ€νΈ λ°μ΄ν° μ½μ
299 char key[20], value[20];
300 for (int i = 0; i < n; i++) {
301 sprintf(key, "key%d", i);
302 sprintf(value, "value%d", i);
303 ht_set(ht, key, value);
304 }
305
306 double load_factor = (double)ht->count / TABLE_SIZE;
307 double avg_probes = ht->count > 0 ? (double)ht->probes / ht->count : 0.0;
308
309 printf("%6.0f%% | %9.2f | %9d\n",
310 load_factor * 100, avg_probes, ht->collisions);
311
312 ht_destroy(ht);
313 }
314
315 printf("\nβ» λ‘λ ν©ν°κ° λμμλ‘ μ±λ₯ μ ν\n");
316 printf("β» 0.7 μ΄ν μ μ§ κΆμ₯\n");
317}
318
319// λ©μΈ ν
μ€νΈ
320int main(void) {
321 printf("ββββββββββββββββββββββββββββββββββββββββββββββ\n");
322 printf("β μ ν νμ¬ ν΄μ ν
μ΄λΈ ꡬν λ° ν
μ€νΈ β\n");
323 printf("ββββββββββββββββββββββββββββββββββββββββββββββ\n");
324
325 HashTable *ht = ht_create();
326 if (!ht) return 1;
327
328 // 1. μ½μ
ν
μ€νΈ
329 printf("\n[ 1λ¨κ³: μ½μ
ν
μ€νΈ ]\n");
330 printf("μ¬λ¬ λ°μ΄ν°λ₯Ό μ½μ
ν©λλ€...\n");
331
332 ht_set(ht, "apple", "μ¬κ³Ό");
333 ht_set(ht, "banana", "λ°λλ");
334 ht_set(ht, "cherry", "체리");
335 ht_set(ht, "date", "λμΆμΌμ");
336 ht_set(ht, "elderberry", "μλλ² λ¦¬");
337 ht_set(ht, "fig", "무νκ³Ό");
338 ht_set(ht, "grape", "ν¬λ");
339
340 ht_print(ht);
341
342 // 2. κ²μ ν
μ€νΈ
343 printf("\n[ 2λ¨κ³: κ²μ ν
μ€νΈ ]\n");
344 const char *keys[] = {"apple", "grape", "kiwi", "banana"};
345 for (int i = 0; i < 4; i++) {
346 char *value = ht_get(ht, keys[i]);
347 if (value) {
348 printf("β '%s' β '%s'\n", keys[i], value);
349 } else {
350 printf("β '%s' β (μ°Ύμ μ μμ)\n", keys[i]);
351 }
352 }
353
354 // 3. μμ ν
μ€νΈ
355 printf("\n[ 3λ¨κ³: μμ ν
μ€νΈ ]\n");
356 printf("'apple'μ κ°μ μμ ν©λλ€...\n");
357 ht_set(ht, "apple", "λ§μλ μ¬κ³Ό π");
358 printf("μμ ν: %s\n", ht_get(ht, "apple"));
359
360 // 4. μμ ν
μ€νΈ
361 printf("\n[ 4λ¨κ³: μμ ν
μ€νΈ ]\n");
362 printf("'banana'λ₯Ό μμ ν©λλ€...\n");
363
364 if (ht_delete(ht, "banana")) {
365 printf("β μμ μ±κ³΅\n");
366 }
367
368 printf("μμ νμΈ: %s\n", ht_get(ht, "banana") ?: "(μ°Ύμ μ μμ)");
369
370 ht_print(ht);
371
372 // 5. μΆ©λ μ λ° ν
μ€νΈ
373 printf("\n[ 5λ¨κ³: μΆ©λ λ° ν΄λ¬μ€ν°λ§ ν
μ€νΈ ]\n");
374 printf("μΆκ° λ°μ΄ν°λ₯Ό μ½μ
ν©λλ€...\n");
375
376 ht_set(ht, "honeydew", "νλλ");
377 ht_set(ht, "kiwi", "ν€μ");
378 ht_set(ht, "lemon", "λ λͺ¬");
379 ht_set(ht, "mango", "λ§κ³ ");
380
381 ht_print(ht);
382
383 // 6. ν΄λ¬μ€ν°λ§ λΆμ
384 analyze_clustering(ht);
385
386 // 7. μμ ν μ¬μ½μ
ν
μ€νΈ
387 printf("\n[ 6λ¨κ³: μμ ν μ¬μ½μ
ν
μ€νΈ ]\n");
388 printf("μ¬λ¬ νλͺ©μ μμ ν ν μλ‘μ΄ νλͺ©μ μ½μ
ν©λλ€...\n\n");
389
390 ht_delete(ht, "cherry");
391 ht_delete(ht, "fig");
392
393 printf("μμ ν:\n");
394 ht_print(ht);
395
396 printf("\nμ νλͺ© μ½μ
:\n");
397 ht_set(ht, "orange", "μ€λ μ§");
398 ht_set(ht, "peach", "볡μμ");
399
400 ht_print(ht);
401
402 // μ 리
403 ht_destroy(ht);
404
405 // 8. μ±λ₯ ν
μ€νΈ
406 performance_test();
407
408 printf("\nνλ‘κ·Έλ¨μ μ’
λ£ν©λλ€.\n");
409 return 0;
410}