README.md - Examples

  1# Hash Table Project (해시 테이블 프로젝트)
  2
  3다양한 해시 함수와 충돌 해결 기법을 구현한 해시 테이블 프로젝트입니다.
  4
  5## 파일 구성
  6
  7### 1. hash_functions.c
  8다양한 해시 함수의 비교 및 분석 도구
  9
 10**구현된 해시 함수:**
 11- `hash_simple` - 단순 합산 (충돌 많음, 나쁜 예)
 12- `hash_djb2` - Daniel J. Bernstein (추천)
 13- `hash_sdbm` - sdbm 데이터베이스 해시
 14- `hash_fnv1a` - Fowler-Noll-Vo 1a
 15
 16**기능:**
 17- 해시 값 비교 출력
 18- 충돌 횟수 및 충돌률 분석
 19- 분포 균일성 분석 (분산 계산)
 20- 해시 분포 시각화
 21
 22### 2. hash_chaining.c
 23체이닝(Separate Chaining)을 이용한 해시 테이블 구현
 24
 25**특징:**
 26- 충돌 시 연결 리스트로 저장
 27- 테이블 크기 제한 없음
 28- 삽입/삭제 간단
 29
 30**구현 기능:**
 31- `ht_create()` - 해시 테이블 생성
 32- `ht_set()` - 삽입/수정
 33- `ht_get()` - 검색
 34- `ht_delete()` - 삭제
 35- `ht_print()` - 테이블 출력
 36- `ht_get_statistics()` - 통계 수집
 37- 체인 길이 분포 시각화
 38
 39### 3. hash_linear_probing.c
 40선형 탐사(Linear Probing)를 이용한 오픈 어드레싱 해시 테이블
 41
 42**특징:**
 43- 충돌 시 다음 빈 슬롯 탐색
 44- 캐시 효율 좋음
 45- DELETED 상태로 삭제 처리
 46
 47**구현 기능:**
 48- 세 가지 슬롯 상태 (EMPTY, OCCUPIED, DELETED)
 49- 선형 탐사 알고리즘
 50- 클러스터링 분석
 51- 로드 팩터별 성능 비교
 52- 클러스터 시각화
 53
 54### 4. dictionary.c
 55해시 테이블을 활용한 실용적인 사전 프로그램
 56
 57**주요 기능:**
 58- 단어 추가/검색/삭제
 59- 전체 목록 출력
 60- 파일 저장/불러오기 (dictionary.txt)
 61- 검색 제안 (부분 일치)
 62- 검색 통계 및 인기 단어 Top 10
 63- 대소문자 구분 없는 검색
 64
 65**데이터 구조:**
 66- 체이닝 방식
 67- 테이블 크기: 1000
 68- 검색 횟수 추적
 69
 70## 컴파일 및 실행
 71
 72### 개별 컴파일
 73```bash
 74gcc -Wall -Wextra -std=c11 -o hash_functions hash_functions.c
 75gcc -Wall -Wextra -std=c11 -o hash_chaining hash_chaining.c
 76gcc -Wall -Wextra -std=c11 -o hash_linear_probing hash_linear_probing.c
 77gcc -Wall -Wextra -std=c11 -o dictionary dictionary.c
 78```
 79
 80### Makefile 사용
 81```bash
 82make                # 모든 프로그램 컴파일
 83make hash_functions # 특정 프로그램만 컴파일
 84make clean          # 생성된 파일 삭제
 85make run_dict       # 사전 프로그램 실행
 86```
 87
 88### 실행
 89```bash
 90./hash_functions        # 해시 함수 비교
 91./hash_chaining         # 체이닝 테스트
 92./hash_linear_probing   # 선형 탐사 테스트
 93./dictionary            # 사전 프로그램
 94```
 95
 96## 학습 포인트
 97
 98### 해시 함수 선택
 99- **djb2**: 일반적인 용도, 균형있는 성능
100- **FNV-1a**: 빠른 속도 필요 시
101- **sdbm**: 데이터베이스 용도
102- **Simple은 사용하지 말 것** (충돌률 높음)
103
104### 충돌 해결 방법 비교
105
106| 비교 항목 | 체이닝 | 오픈 어드레싱 |
107|-----------|--------|---------------|
108| 메모리 | 동적 할당 | 고정 크기 |
109| 삭제 | 간단 | DELETED 표시 필요 |
110| 캐시 효율 | 불리 | 유리 |
111| 로드 팩터 | >1 가능 | <1 필수 |
112| 구현 복잡도 | 낮음 | 중간 |
113
114### 시간 복잡도
115
116| 연산 | 평균 | 최악 |
117|------|------|------|
118| 삽입 | O(1) | O(n) |
119| 검색 | O(1) | O(n) |
120| 삭제 | O(1) | O(n) |
121
122### 성능 최적화 팁
1231. 로드 팩터 0.7 이하 유지
1242. 좋은 해시 함수 선택 (djb2 추천)
1253. 테이블 크기는 소수(prime number) 사용 권장
1264. 체이닝 vs 오픈 어드레싱 선택은 용도에 따라
127
128## 예제 출력
129
130### hash_functions 실행 결과
131```
132=== 해시 함수 비교 ===
133
134Key          | Simple | djb2 | sdbm | fnv1a
135-------------|--------|------|------|------
136apple        |     30 |   43 |   58 |    67
137banana       |      9 |   42 |   49 |    52
138
139=== 충돌 분석 ===
140Simple       |        14 | 28.0%
141djb2         |         6 | 12.0%  ← 최소 충돌
142```
143
144### dictionary 사용 예
145```
146선택: 1
147단어: programming
148뜻: 프로그래밍; 컴퓨터에 명령을 작성하는 작업
149✓ 'programming' 추가됨
150
151선택: 2
152검색할 단어: prog
153'prog'로 시작하는 단어:
154  - programming
155총 1개 발견
156```
157
158## 확장 아이디어
159
1601. **동적 크기 조절**: 로드 팩터가 0.7 초과 시 테이블 크기 2배 확장
1612. **이중 해싱**: 두 번째 해시 함수로 탐사 간격 결정
1623. **사전 기능 추가**:
163   - 단어 예문
164   - 발음 기호
165   - 동의어/반의어
1664. **성능 측정**: 각 연산의 실제 수행 시간 측정
1675. **멀티스레드**: 읽기 동시성 지원
168
169## 참고 자료
170
171- 해시 함수: [djb2, sdbm, FNV-1a 알고리즘](http://www.cse.yorku.ca/~oz/hash.html)
172- 충돌 해결: Cormen et al., "Introduction to Algorithms"
173- 실전 활용: Python `dict`, Java `HashMap`, C++ `unordered_map`