hash_chaining.c - Examples

  1/*
  2 * hash_chaining.c
  3 * 체이닝(Separate Chaining)을 이용한 해시 테이블 구현
  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 10
 17#define KEY_SIZE 50
 18#define VALUE_SIZE 100
 19
 20// 노드 구조체 (키-값 쌍을 저장)
 21typedef struct Node {
 22    char key[KEY_SIZE];
 23    char value[VALUE_SIZE];
 24    struct Node *next;  // 다음 노드 (체이닝)
 25} Node;
 26
 27// 해시 테이블 구조체
 28typedef struct {
 29    Node *buckets[TABLE_SIZE];  // 버킷 배열
 30    int count;                   // 저장된 항목 개수
 31    int collisions;              // 충돌 횟수
 32} HashTable;
 33
 34// 통계 정보
 35typedef struct {
 36    int total_inserts;
 37    int total_searches;
 38    int total_deletes;
 39    int chain_lengths[TABLE_SIZE];
 40} Statistics;
 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->buckets[i] = NULL;
 63    }
 64    ht->count = 0;
 65    ht->collisions = 0;
 66
 67    return ht;
 68}
 69
 70// 해시 테이블 해제
 71void ht_destroy(HashTable *ht) {
 72    if (!ht) return;
 73
 74    // 각 버킷의 체인 해제
 75    for (int i = 0; i < TABLE_SIZE; i++) {
 76        Node *current = ht->buckets[i];
 77        while (current) {
 78            Node *next = current->next;
 79            free(current);
 80            current = next;
 81        }
 82    }
 83    free(ht);
 84}
 85
 86// 삽입 또는 수정
 87bool ht_set(HashTable *ht, const char *key, const char *value) {
 88    if (!ht || !key || !value) return false;
 89
 90    unsigned int index = hash(key);
 91
 92    // 기존 키가 있는지 확인
 93    Node *current = ht->buckets[index];
 94    while (current) {
 95        if (strcmp(current->key, key) == 0) {
 96            // 기존 키 발견 → 값만 업데이트
 97            strncpy(current->value, value, VALUE_SIZE - 1);
 98            current->value[VALUE_SIZE - 1] = '\0';
 99            return true;
100        }
101        current = current->next;
102    }
103
104    // 새 노드 생성
105    Node *node = malloc(sizeof(Node));
106    if (!node) {
107        fprintf(stderr, "메모리 할당 실패\n");
108        return false;
109    }
110
111    strncpy(node->key, key, KEY_SIZE - 1);
112    node->key[KEY_SIZE - 1] = '\0';
113    strncpy(node->value, value, VALUE_SIZE - 1);
114    node->value[VALUE_SIZE - 1] = '\0';
115
116    // 버킷 맨 앞에 삽입 (O(1))
117    node->next = ht->buckets[index];
118
119    // 충돌 확인 (버킷에 이미 노드가 있으면 충돌)
120    if (ht->buckets[index] != NULL) {
121        ht->collisions++;
122    }
123
124    ht->buckets[index] = node;
125    ht->count++;
126
127    return true;
128}
129
130// 검색
131char* ht_get(HashTable *ht, const char *key) {
132    if (!ht || !key) return NULL;
133
134    unsigned int index = hash(key);
135
136    // 체인 탐색
137    Node *current = ht->buckets[index];
138    while (current) {
139        if (strcmp(current->key, key) == 0) {
140            return current->value;  // 찾음!
141        }
142        current = current->next;
143    }
144
145    return NULL;  // 찾지 못함
146}
147
148// 삭제
149bool ht_delete(HashTable *ht, const char *key) {
150    if (!ht || !key) return false;
151
152    unsigned int index = hash(key);
153
154    Node *current = ht->buckets[index];
155    Node *prev = NULL;
156
157    // 체인에서 노드 찾기
158    while (current) {
159        if (strcmp(current->key, key) == 0) {
160            // 노드 제거
161            if (prev) {
162                prev->next = current->next;  // 중간 또는 끝
163            } else {
164                ht->buckets[index] = current->next;  // 맨 앞
165            }
166            free(current);
167            ht->count--;
168            return true;
169        }
170        prev = current;
171        current = current->next;
172    }
173
174    return false;  // 찾지 못함
175}
176
177// 해시 테이블 출력
178void ht_print(HashTable *ht) {
179    if (!ht) return;
180
181    printf("\n╔════════════════════════════════════════════╗\n");
182    printf("║         해시 테이블 상태 (체이닝)         ║\n");
183    printf("╠════════════════════════════════════════════╣\n");
184    printf("║  항목 개수: %-5d                          ║\n", ht->count);
185    printf("║  충돌 횟수: %-5d                          ║\n", ht->collisions);
186    printf("║  로드 팩터: %.2f                           ║\n",
187           (double)ht->count / TABLE_SIZE);
188    printf("╚════════════════════════════════════════════╝\n\n");
189
190    for (int i = 0; i < TABLE_SIZE; i++) {
191        printf("[%d]: ", i);
192
193        Node *current = ht->buckets[i];
194        if (!current) {
195            printf("(비어있음)\n");
196            continue;
197        }
198
199        // 체인 출력
200        int chain_length = 0;
201        while (current) {
202            printf("[\"%s\":\"%s\"]", current->key, current->value);
203            if (current->next) printf(" → ");
204            current = current->next;
205            chain_length++;
206        }
207        printf(" (길이: %d)\n", chain_length);
208    }
209}
210
211// 통계 수집
212void ht_get_statistics(HashTable *ht, Statistics *stats) {
213    if (!ht || !stats) return;
214
215    memset(stats, 0, sizeof(Statistics));
216
217    stats->total_inserts = ht->count;
218
219    // 각 버킷의 체인 길이 계산
220    for (int i = 0; i < TABLE_SIZE; i++) {
221        int length = 0;
222        Node *current = ht->buckets[i];
223        while (current) {
224            length++;
225            current = current->next;
226        }
227        stats->chain_lengths[i] = length;
228    }
229}
230
231// 통계 출력
232void print_statistics(HashTable *ht) {
233    Statistics stats;
234    ht_get_statistics(ht, &stats);
235
236    printf("\n=== 성능 통계 ===\n\n");
237
238    // 최대 체인 길이
239    int max_length = 0;
240    int empty_buckets = 0;
241    for (int i = 0; i < TABLE_SIZE; i++) {
242        if (stats.chain_lengths[i] > max_length) {
243            max_length = stats.chain_lengths[i];
244        }
245        if (stats.chain_lengths[i] == 0) {
246            empty_buckets++;
247        }
248    }
249
250    double avg_chain_length = (double)ht->count / (TABLE_SIZE - empty_buckets);
251
252    printf("저장된 항목:     %d\n", ht->count);
253    printf("충돌 횟수:       %d\n", ht->collisions);
254    printf("비어있는 버킷:   %d / %d\n", empty_buckets, TABLE_SIZE);
255    printf("최대 체인 길이:  %d\n", max_length);
256    printf("평균 체인 길이:  %.2f\n", avg_chain_length);
257    printf("로드 팩터:       %.2f\n", (double)ht->count / TABLE_SIZE);
258
259    // 체인 길이 분포
260    printf("\n체인 길이 분포:\n");
261    for (int i = 0; i < TABLE_SIZE; i++) {
262        if (stats.chain_lengths[i] > 0) {
263            printf("  버킷 %d: ", i);
264            for (int j = 0; j < stats.chain_lengths[i]; j++) {
265                printf("█");
266            }
267            printf(" (%d)\n", stats.chain_lengths[i]);
268        }
269    }
270}
271
272// 키 존재 여부 확인
273bool ht_contains(HashTable *ht, const char *key) {
274    return ht_get(ht, key) != NULL;
275}
276
277// 모든 키 출력
278void ht_print_keys(HashTable *ht) {
279    if (!ht) return;
280
281    printf("\n=== 저장된 키 목록 ===\n");
282    int count = 0;
283    for (int i = 0; i < TABLE_SIZE; i++) {
284        Node *current = ht->buckets[i];
285        while (current) {
286            printf("  %d. %s\n", ++count, current->key);
287            current = current->next;
288        }
289    }
290    printf("총 %d개\n", count);
291}
292
293// 테스트 함수
294int main(void) {
295    printf("╔════════════════════════════════════════════╗\n");
296    printf("║      체이닝 해시 테이블 구현 및 테스트    ║\n");
297    printf("╚════════════════════════════════════════════╝\n");
298
299    HashTable *ht = ht_create();
300    if (!ht) return 1;
301
302    // 1. 삽입 테스트
303    printf("\n[ 1단계: 삽입 테스트 ]\n");
304    printf("여러 과일 이름과 한글명을 삽입합니다...\n");
305
306    ht_set(ht, "apple", "사과");
307    ht_set(ht, "banana", "바나나");
308    ht_set(ht, "cherry", "체리");
309    ht_set(ht, "date", "대추야자");
310    ht_set(ht, "elderberry", "엘더베리");
311    ht_set(ht, "fig", "무화과");
312    ht_set(ht, "grape", "포도");
313    ht_set(ht, "honeydew", "허니듀 멜론");
314
315    ht_print(ht);
316
317    // 2. 검색 테스트
318    printf("\n[ 2단계: 검색 테스트 ]\n");
319    const char *search_keys[] = {"apple", "grape", "kiwi", "banana"};
320    for (int i = 0; i < 4; i++) {
321        char *value = ht_get(ht, search_keys[i]);
322        if (value) {
323            printf("✓ '%s' → '%s'\n", search_keys[i], value);
324        } else {
325            printf("✗ '%s' → (찾을 수 없음)\n", search_keys[i]);
326        }
327    }
328
329    // 3. 수정 테스트
330    printf("\n[ 3단계: 수정 테스트 ]\n");
331    printf("'apple'의 값을 수정합니다...\n");
332    ht_set(ht, "apple", "맛있는 사과 🍎");
333    printf("수정 후: apple → %s\n", ht_get(ht, "apple"));
334
335    // 4. 삭제 테스트
336    printf("\n[ 4단계: 삭제 테스트 ]\n");
337    printf("'banana'를 삭제합니다...\n");
338    if (ht_delete(ht, "banana")) {
339        printf("✓ 삭제 성공\n");
340    }
341    printf("삭제 확인: banana → %s\n",
342           ht_get(ht, "banana") ?: "(찾을 수 없음)");
343
344    ht_print(ht);
345
346    // 5. 충돌 테스트 (같은 해시값을 가지도록)
347    printf("\n[ 5단계: 충돌 발생 테스트 ]\n");
348    printf("추가 데이터를 삽입하여 충돌을 유발합니다...\n");
349
350    ht_set(ht, "kiwi", "키위");
351    ht_set(ht, "lemon", "레몬");
352    ht_set(ht, "mango", "망고");
353
354    ht_print(ht);
355
356    // 6. 성능 통계
357    print_statistics(ht);
358
359    // 7. 키 목록
360    ht_print_keys(ht);
361
362    // 정리
363    ht_destroy(ht);
364
365    printf("\n프로그램을 종료합니다.\n");
366    return 0;
367}