해시(Hash)
- 데이터를 최대한 빠른 속도로 관리하도록 도와주는 자료 구조
- 해시를 사용하면 메모리 공간이 많이 소모되지만 매우 빠른 속도로 데이터를 처리할 수 있음
- 빠르게 데이터에 접근할 수 있다는 점에서 데이터베이스 등의 소프트웨어에서 활용
해시 함수 동작 과정
- 특정한 값을 찾고자 할 때는 그 값의 키로 접근할 수 있음
- 일반적으로 해시 함수는 모듈로 연산 등의 수학적 연산으로 이루어져 있으므로 O(1)만에 값에 접근할 수 있음
* 특정한 값이 들어왔을 때 그 값에 10을 나눈 나머지 값이 키가 될 수 있도록 했다고 가정
입력 데이터 > 해시 함수(n mod 10) > 키(Key) | 값(Value)
78 / khon 2 | khon01
12 / khon01 4 | khon03
55 / khon02 5 | khon02
64 / khon03 8 | khon
해시의 충돌
- 해시 함수의 입력 값으로는 어떠한 값이나 모두 들어갈 수 있지만 해시 함수를 거쳐 생성되는 키의 경우의 수는 한정적이기 때문에 키 중복이 발생할 수 있음
- 해시 테이블에서 키가 중복되는 경우 충돌(Collision)이 발생했다고 표현
- 동일한 데이터 값이 들어갈 경우 충돌
생일의 역설
- 무작위의 사람 57명을 한 곳에 모아 놓으면, 2명의 생일이 같을 확률이 99%
- 이를 해싱 과정과 비교하자면 '365로 나눈 나머지'를 키로 이용하는 해시 함수의 경우 입력 데이터가 57개만 되어도 사실상 충돌이 무조건 발생한다고 판단해야 하는 것
해싱(Hashing)
- 해싱 알고리즘은 나눗셈 법이 가장 많이 활용됨
- 입력 값을 테이블의 크기로 나눈 나머지를 키로 이용하는 방식
- 테이블의 크기는 소수로 설정하는 것이 효율성이 높음
충돌을 처리하는 방법
- 아무리 잘 만들어진 해시 함수라고 해도 충돌이 발생할 수밖에 없음
- 충돌을 처리하는 방법은 다음과 같이 두 가지 유형으로 분류할 수 있음
1. 충돌을 발생시키는 항목을 해시 테이블의 다른 위치에 저장 : 선형 조사법, 이차 조사법 등
2. 해시 테이블의 하나의 버킷에 여러 개의 항목을 저장 : 체이닝 등
선형 조사법
- 데이터가 충돌할 경우 그다음 데이터 비어있다면 그곳에 데이터를 넣음
// 선형 조사법 구조체 정의
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TABLE_SIZE 10007
#define INPUT_SIZE 5000
typedef struct {
int id;
char name[20];
} Student;
// 해시 테이블 초기화
void init(Student** hashTable) {
for (int i = 0; i < TABLE_SIZE; i++) {
hashTable[i] = NULL;
}
}
// 해시 테이블 메모리 반환
void destructor(Student** hashTable) {
for (int i = 0; i < TABLE_SIZE; i++) {
if (hashTable[i] != NULL) {
free(hashTable[i]);
}
}
}
// 해시 테이블 내 빈 공간을 선형 탐색으로 찾음
int findEmpty(Student** hashTable, int id) {
int i = id % TABLE_SIZE;
while (1) {
if (hashTable[i % TABLE_SIZE] == NULL) {
return i % TABLE_SIZE;
}
i++;
}
}
// 특정한 ID 값에 매칭되는 데이터를 해시 테이블 내에서 찾음
int searh(Student** hashTable, int id) {
int i = id % TABLE_SIZE;
while (1) {
if (hashTable[i % TABLE_SIZE] == NULL) return -1;
else if (hashTable[i % TABLE_SIZE]->id == id) return i;
i++;
}
}
// 특정한 키 인덱스에 데이터를 삽입
void add(Student** hashTable, Student* input, int key) {
hashTable[key] = input;
}
// 해시 테이블에서 특정한 키의 데이터를 반환
Student* getValue(Student** hashTable, int key) {
return hashTable[key];
}
// 선형 조사법 데이터 출력 함수
// 해시 테이블에 존재하는 모든 데이터를 출력
void show(Student** hashTable) {
for (int i = 0; i < TABLE_SIZE; i++) {
if (hashTable[i] != NULL) {
printf("키: [%d] 이름: [%s]\n", i, hashTable[i]->name);
}
}
}
int main(void) {
Student **hashTable;
hashTable = (Student**)malloc(sizeof(Student) * TABLE_SIZE);
init(hashTable);
for (int i = 0; i < INPUT_SIZE; i++) {
Student* student = (Student*)malloc(sizeof(Student));
student->id = rand() % 1000000;
sprintf(student->name, "사람%d", student->id);
if (searh(hashTable, student->id) == -1) { // 중복되는 ID는 존재하지 않도록 함
int index = findEmpty(hashTable, student->id);
add(hashTable, student, index);
}
}
show(hashTable);
destructor(hashTable);
system("pause");
return 0;
}
선형 조사법의 단점
- 충돌이 발생하기 시작하면 유사한 값을 가지는 데이터끼리 서로 밀집되는 집중 결함 문제가 존재
- 메모리를 많이 소모한다면 충돌이 적게 발생하므로 매우 바른 데이터 접근 속도를 가질 수 있음
- 일반적인 경우 해시 테이블의 크기는 한정적이므로 충돌이 최대한 적게 발생하도록 해야 함
이차 조사법
- 선형 조사법을 약간 변형한 형태로 키 값을 선택할 때 완전 제곱수를 더해 나가는 방식
- 데이터를 입력하다가 충돌이 발생할 경우 1만큼 떨어진 공간에서 확인을 하고 그 자리에 숫자가 차 있다면 2의 제곱만큼 넘어서 자리를 확인
- 기존에 발생했던 데이터가 밀집되는 현상이 줄어들기 때문에 해시 충돌이 적게 발생한다는 특징이 있음
조사법의 테이블 크기 재설정
- 일반적으로 선형 조사법, 이차 조사법 등의 조사법에서 테이블이 가득 차게 되면 테이블의 크기를 확장하여 계속해서 해시 테이블을 유지할 수 있도록 함
체이닝(Chaining)
- 연결 리스트를 활용해 특정한 키를 가지는 항목들을 연결하여 저장함
- 연결 리스트를 사용한다는 점에서 삽입과 삭제가 용이함
- 테이블 크기 재설정 문제는 동적 할당을 통해 해결할 수 있음
- 동적 할당을 위한 추가적인 메모리 공간이 소모된다는 단점이 있음
- 충돌이 발생하더라도 무시하고 키 값에 해당하는 연결 리스트에 계속해서 데이터를 넣음
// 체이닝 구조체 정의
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TABLE_SIZE 10007
#define INPUT_SIZE 5000
typedef struct {
int id;
char name[20];
} Student;
typedef struct {
Student* data;
struct Bucket* next;
} Bucket;
// 해시 테이블 초기화
void init(Bucket** hashTable) {
for (int i = 0; i < TABLE_SIZE; i++) {
hashTable[i] = NULL;
}
}
// 해시 테이블 메모리 반환
void destructor(Bucket** hashTable) {
for (int i = 0; i < TABLE_SIZE; i++) {
if (hashTable[i] != NULL) {
free(hashTable[i]);
}
}
}
// 체이닝 데이터 탐색 함수
int isExist(Bucket** hashTable, int id) {
int i = id % TABLE_SIZE;
if (hashTable[i] == NULL) return 0;
else {
Bucket *cur = hashTable[i];
while (cur != NULL) {
if (cur->data->id == id) return 1;
cur = cur->next;
}
}
return 0;
}
// 체이닝 데이터 삽입 함수
// 특정한 키 인덱스에 데이터를 삽입
void add(Bucket** hashTable, Student* input) {
int i = input->id % TABLE_SIZE;
if (hashTable[i] == NULL) {
hashTable[i] = (Bucket*)malloc(sizeof(Bucket));
hashTable[i]->data = input;
hashTable[i]->next = NULL;
}
else {
Bucket *cur = (Bucket*)malloc(sizeof(Bucket));
cur->data = input;
cur->next = hashTable[i];
hashTable[i] = cur;
}
}
// 체이닝 데이터 출력 함수
// 해시 테이블에 존재하는 모든 데이터를 출력
void show(Bucket** hashTable) {
for (int i = 0; i < TABLE_SIZE; i++) {
if (hashTable[i] != NULL) {
Bucket *cur = hashTable[i];
while (cur != NULL) {
printf("키: [%d] 이름: [%s]\n", i, cur->data->name);
cur = cur->next;
}
}
}
}
int main(void) {
Bucket **hashTable;
hashTable = (Bucket**)malloc(sizeof(Bucket) * TABLE_SIZE);
init(hashTable);
for (int i = 0; i < INPUT_SIZE; i++) {
Student* student = (Student*)malloc(sizeof(Student));
student->id = rand() % 1000000;
sprintf(student->name, "사람%d", student->id);
if (!isExist(hashTable, student->id)) { // 중복되는 ID는 존재하지 않도록 함
add(hashTable, student);
}
}
show(hashTable);
destructor(hashTable);
system("pause");
return 0;
}
