해시 함수
키를 버킷에 매핑합니다
해시 함수은(는) CoddyKit의 무료 C Academy 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
해시 함수란 무엇인가
해시 함수는 키를 받아 배열의 버킷을 가리키는 정수 인덱스를 생성합니다. 해시 테이블의 핵심으로, 문자열과 같은 임의의 키를 빠른 배열 위치로 변환합니다.
- 입력: 키(문자열, 정수 등)
- 출력:
[0, capacity)범위의 버킷 인덱스
좋은 해시의 특성
좋은 해시 함수는 결정적이고 빠르며, 키를 버킷 전체에 균일하게 분산합니다.
- 같은 키는 항상 같은 인덱스를 생성합니다.
- 키가 조금만 바뀌어도 인덱스가 크게 바뀝니다(눈사태 효과).
- 일반적인 데이터에서 충돌이 적습니다.
버킷으로 매핑하기
원시 해시 값을 계산한 후에는 나머지 연산자를 사용하여 테이블에 매핑합니다. index = hash % capacity
나머지 연산 결과가 음수 인덱스가 되지 않도록 unsigned 형식을 사용하세요.
#include <stdio.h>
int main(void) {
unsigned long hash = 123456789UL;
unsigned capacity = 16;
unsigned index = (unsigned)(hash % capacity);
printf("bucket = %u\n", index);
return 0;
}간단한 합 해시
가장 간단한 문자열 해시는 문자 값을 모두 더합니다. 구현하기 쉽지만 애너그램이 충돌하므로 분산 성능이 좋지 않습니다.
실행하여 서로 다른 두 문자열이 서로 가까운 값으로 해시되는 것을 확인해 보세요.
#include <stdio.h>
unsigned long sum_hash(const char *s) {
unsigned long h = 0;
while (*s) h += (unsigned char)*s++;
return h;
}
int main(void) {
printf("%lu\n", sum_hash("abc"));
printf("%lu\n", sum_hash("cba"));
return 0;
}DJB2 해시
DJB2는 Daniel J. Bernstein이 만든 고전적인 고분산 문자열 해시입니다. 5381에서 시작하며 hash * 33 + c를 사용합니다.
곱셈과 덧셈을 함께 사용하면 단순한 합보다 비트가 훨씬 잘 섞입니다.
#include <stdio.h>
unsigned long djb2(const char *s) {
unsigned long h = 5381;
int c;
while ((c = (unsigned char)*s++))
h = ((h << 5) + h) + c; /* h * 33 + c */
return h;
}
int main(void) {
printf("%lu\n", djb2("hello"));
printf("%lu\n", djb2("world"));
return 0;
}FNV-1a 해시
FNV-1a는 각 바이트에 XOR을 적용한 다음 소수를 곱합니다. 단순하고 빠르며 널리 사용됩니다.
순서는 먼저 XOR을 적용하고 그다음 곱하는 것입니다. 이것이 1a 변형입니다.
#include <stdio.h>
unsigned long fnv1a(const char *s) {
unsigned long h = 1469598103934665603UL;
while (*s) {
h ^= (unsigned char)*s++;
h *= 1099511628211UL;
}
return h;
}
int main(void) {
printf("%lu\n", fnv1a("key1"));
printf("%lu\n", fnv1a("key2"));
return 0;
}정수 해싱하기
정수 키도 섞기 과정이 필요합니다. x % capacity만 사용하면 패턴을 공유하는 키가 한곳에 몰리기 때문입니다. 곱셈 방식의 섞기(커누스)를 사용하면 비트가 분산됩니다.
#include <stdio.h>
unsigned hash_int(unsigned x, unsigned cap) {
x *= 2654435761u; /* Knuth multiplicative */
return x % cap;
}
int main(void) {
for (unsigned i = 0; i < 5; i++)
printf("%u -> %u\n", i, hash_int(i, 8));
return 0;
}2의 거듭제곱 용량
용량이 2의 거듭제곱이면 % capacity를 빠른 비트 AND 연산인 hash & (capacity - 1)로 바꿀 수 있습니다.
2의 거듭제곱에서 1을 뺀 값의 하위 비트가 완전한 마스크를 이루기 때문에만 이 방식이 작동합니다.
#include <stdio.h>
int main(void) {
unsigned long hash = 123456789UL;
unsigned capacity = 16; /* power of two */
unsigned index = (unsigned)(hash & (capacity - 1));
printf("bucket = %u\n", index);
return 0;
}나머지 연산이 느릴 수 있는 이유
% 연산자는 AND보다 느린 나눗셈 명령으로 컴파일됩니다. 반복이 매우 많은 구간에서는 이 차이가 중요합니다.
- 2의 거듭제곱 크기 테이블: AND 마스크 사용
- 소수 크기 테이블: 나머지 연산 사용(약한 해시의 분산 성능이 더 좋음)
충돌은 피할 수 없습니다
비둘기집 원리에 따르면 많은 키를 더 적은 버킷에 매핑하면 충돌이 반드시 발생합니다. 좋은 해시는 충돌을 최소화하지만 완전히 없앨 수는 없습니다.
다음 단원에서는 충돌을 해결하는 방법을 다룹니다.
분산 시연
DJB2가 여러 키를 8개 버킷에 어떻게 분산하는지 세어 보겠습니다. 좋은 해시는 값을 비교적 고르게 분산합니다.
#include <stdio.h>
unsigned long djb2(const char *s) {
unsigned long h = 5381;
int c;
while ((c = (unsigned char)*s++)) h = ((h << 5) + h) + c;
return h;
}
int main(void) {
const char *keys[] = {"apple", "banana", "cherry", "date"};
int counts[8] = {0};
for (int i = 0; i < 4; i++)
counts[djb2(keys[i]) % 8]++;
for (int i = 0; i < 8; i++)
printf("bucket %d: %d\n", i, counts[i]);
return 0;
}빠른 확인
해시 함수의 기초에 대한 이해도를 확인해 보세요.
복습
해시 함수의 역할과 키를 버킷에 매핑하는 방법을 배웠습니다.
- 좋은 해시는 결정적이고 빠르며 균일합니다.
- DJB2와 FNV-1a는 견고한 문자열 해시입니다.
% capacity로 매핑하고, 용량이 2의 거듭제곱이면& (capacity-1)을 사용합니다.- 부호 없는 형식을 사용하세요. 충돌은 피할 수 없습니다.
자주 묻는 질문
“해시 함수” 강의는 무료인가요?
네 — “해시 함수” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C Academy 강의 전체를 잠금 해제할 수 있습니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“해시 함수”에서 뭘 배우나요?
키를 버킷에 매핑합니다 브라우저에서 직접 실행하는 실습 코드로 C Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
C Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 C Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“해시 함수” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 C Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 C Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.