해시(Hash)
해시는 데이터를 최대한 빠른 속도로 관리할 수 있도록 도와주는 자료구조이다.
해시를 사용하면 메모리공간이 많이 소모되지만 매우 빠른 속도로 데이터를 처리할 수 있다.
빠르게 데이터에 접근할 수 있다는 점에서 데이터베이스 등의 소프트웨어에서 활용된다.
동작과정
입력데이터를
78/AA
12/BB
55/CC
64/DD
라고 입력하고 해시함수를 (n mod 10)으로 입력값 n을 10으로 나눈 나머지값을 키(key)로 갖게 한다면
인덱스 8의 값으로 AA가 들어가고 2에는 BB, 5에는 CC, 4에는 DD가 값(value)로 들어가게 된다.
이런식으로 해시함수를 이용하게 되면 기존의 값들이 특정한 값으로 매칭이 되어서 차곡차곡 쌓이게 되는
형태다.
특정한 값(value)을 찾을때는 키(key)로 접근할 수 있는데 배열에서의 index를 의미하는것과 같다.
일반적으로 해시함수는 모듈로(modulo)연산등의 수학적 연산으로 이루어져 있으므로 O(1)만에
값에 접근할 수 있다.
해싱(Hashing)
해싱 알고리즘은 나눗셈법(Division Method)이 가장 많이 활용된다. 입력값을 테이블의 크기로 나눈 나머지를
키로 이용하는 방식이다. 테이블의 크기는 소수(Prime Number)로 설정하는 것이 효율성이 높다.
해시의 충돌(Collision)
해시함수의 입력값으로는 어떠한 값이나 모두 들어갈 수 있지만, 해시함수를 거쳐 생성되는 키의 경우의수는
한정적이기 때문에 키 중복이 발생할 수 있다.
해시테이블에서 키가 중복되는 경우를 충돌(Collision)이라고 표현한다.
입력데이터가 77/AA, 17/BB라고 하고 해시함수를 (n mod 10)이라고 했을 때 두 데이터 모두 7이라는
키값을 갖게 된다. 이러한 문제가 발생하는 것이 충돌이다.
아무리 잘 만들어진 해시함수라도 충돌이 발생할 수 밖에 없다. 충돌을 처리하는 방법은 다음과 같이
두가지유형으로 분류할 수 있다.
1. 충돌을 발생시키는 항목을 해시테이블의 다른 위치에 저장 : 선형조사법, 이차조사법 등
2. 해시테이블의 하나의 버킷(Bucket)에 여러개의 항목을 저장 : 체이닝(Chaning) 등
선형조사법
입력데이터가 1/AA, 5/BB, 10012/CC, 20019/DD일 때 해시함수로 (n mod 10007)처리한다고 하면
1과 5는 일단 값이 들어간다. 10012를 10007로 나눈 나머지값은 5가 되는데 이미 5라는 키값은 존재한다.
그럼 중복이 되기때문에 다음 인덱스로 들어간다. 그럼 1에는 AA, 5에는 BB, 6에는 CC가 들어가게 된다.
마지막 데이터인 20019역시 나머지값이 5이므로 CC가 들어갈때와 동일하게 중복이 된다.
그럼 5에서 중복이기때문에 6으로 가지만 6역시 키값이 존재하므로 7에 값이 들어간다.
이렇게 차례로 하나씩 탐색하는것 즉, 선형적으로 탐색한다고 해서 선형조사법이라고 한다.
선형조사법 예제코드
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h> //time을 사용하는 이유는 무작위 데이터를 5000개 삽입할 것이기 때문
#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;
//각 테이블의 포인터값을 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 search(Student** hashTable, int id){
int i = id % TABLE_SIZE;
while(1){
if(hashTable[i % TABLE_SIZE] == NULL) return -1;
//해당 인덱스가 비어있다면 -1을 리턴
else if(hashTable[i % TABLE_SIZE]->id == id) return i;
//해당 인덱스의 id가 id와 같다면 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;
//랜덤으로 만들어진 숫자를 1000000으로 나눈 나머지값
//10007을 넘기지 않기 위함이다.
sprintf(student->name, "사람%d", student->id);
//학생의 이름은 사람+학생번호로 만들어준다.
if(search(hashTable, student->id) == -1){
//중복되는 ID는 존재하지 않도록
//해당 학생 번호에 해당하는 key값을 테이블에서 매칭하도록 찾아야 한다.
int index = findEmpty(hashTable, student->id);
add(hashTable, student, index);
}
}
show(hashTable);
destructor(hashTable);
system("pause");
return 0;
}실행해보면 많은 데이터가 삽입되었지만 중복된 키값은 없다는 것을 확인할 수 있다.
그리고 설정한것처럼 10007이 넘는 키값은 존재하지 않는다.
선형조사법의 단점
선형조사법은 충돌이 발생하기 시작하면 유사한 값을 갖는 데이터끼리 서로 밀집되는 집중결합문제가 존재한다.
예를들어 데이터 5라는 키에 들어가야되는 값이 3개 존재했다면 5, 6, 7에 순차적으로 들어가 밀집되는 문제다.
선형조사법이라고 해도 해시테이블의 크기가 비약적으로 크다면, 다시말해 메모리를 많이 소모한다면 충돌이 적게
발생하므로 매우 빠른 데이터 접근속도를 가질 수 있다.
하지만 일반적인 경우, 해시테이블의 크기는 한정적이므로 충돌이 최대한 적게 발생하도록 해야한다.
이차조사법
선형조사법의 단점을 보완하기 위한 조사법이다.
선형조사법을 약간 변형한 형태로 키값을 선택할 때 완전제곱수를 더해 나가는 방식이다.
아까와 같은 1, 5, 10012, 20019라는 데이터와 (n mod 10007)이라는 해시 함수를 사용한다면
10012부터 충돌이 되는데 처음 중복시에는 다음 인덱스만 체크해서 넣어준다.
그 다음 20019에서 또 충돌이 발생했을 때는 2의 제곱인 4만큼의 공간을 넘어가서 입력하는 방식이다.
조사법 테이블 크기 재설정
일반적으로 선형조사법, 이차조사법 등의 조사법에서 테이블이 가득차게 되면 테이블의 크기를 확장하여 계속해서
해시테이블을 유지할 수 있도록 한다.
체이닝(Chaning)
체이닝 기법은 연결리스트를 활용해 특정한 키를 갖는 항목들을 연결하여 젖앟나다.
연결리스트를 사용한다는 점에서 삽입과 삭제가 용이하다. 또한 테이블 크기 재설정 문제는 '동적할당'을 통해서
손쉽게 해결할 수 잇다. 다만 동적할당을 위한 추가적인 메모리공간이 소모된다는 단점이 있다.
연결리스트를 사용한다는 것은 5/BB, 10012/CC, 20019/DD의 데이터가 (n mod 10007)의 해시함수를 통했을 때
키값이 5로 중복되는데 이것을 5라는 하나의 키에 BB, CC, DD 형태의 연결리스트로 만들어 해결하는 것이다.
체이닝 예제코드
#define _CRT_SECURE_NO_WARINGS
#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;
//학생구조체가 연결리스트 형태로 들어갈 수 있도록 각각의 bucket을 설정
//즉, 하나의 키에 해당하는 데이터가 여러개 들어갈 수 있다는 것
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; //해당 테이블이 NULL이라면
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)) {//중복체크
add(hashTable, student);
//중복이 되지 않는 경우만 삽입
}
}
show(hashTable);
destructor(hashTable);
system("pause");
return 0;
}선형기법과 다르게 동일한 키값에 다른 데이터가 들어가있는것을 확인할 수 있다.
체이닝 기법을 활용해 동일한 키값에 연결리스트로 들어갔다는 것을 확인할 수 있는 것이다.
레퍼런스
패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직
'자료구조' 카테고리의 다른 글
| 프림(Prim) 알고리즘 (0) | 2021.01.19 |
|---|---|
| 최소신장트리(Minimum Spanning Tree, MST) (0) | 2021.01.19 |
| AVL트리 (0) | 2021.01.17 |
| 이진탐색트리(Binary Search Tree) (0) | 2021.01.16 |
| 너비우선탐색(BFS) (0) | 2021.01.15 |
