Hash

해시(Hash)
데이터를 최대한 빠른 속도로 관리하도록 도와주는 자료구조
메모리 공간을 많이 소모하지만, 매우 빠른 속도로 데이터를 처리
빠르게 데이터에 접근할 수 있다. (데이터베이스 등의 소프트웨어에서 사용)

특정한 값을 찾고자 할 때는 그 값의 키(key)를 이용.
일반적으로 해시 함수는 모듈로(Modulo) 연산 등의 수학적 연산으로 이루어져 있으므로 O(1)만에 값에 접근

해시 테이블에서 키(Key)가 중복되는 경우 충돌(Collision)이 발생했다고 말한다.
해싱(Hashing)
해싱 알고리즘으로 나눗셈법(Division Method)이 가장 많이 활용
입력 값을 테이블의 크기로 나눈 나머지를 키(Key)로 이용하는 방식이다.

테이블의 크기는 소수(Prime Number)로 설정하는 것이 효율성이 높다.
충돌 처리
1) 충돌을 발생시키는 항목을 해시 테이블의 다른 위치에 저장: 선형 조사법, 이차 조사법 등
2) 해시 테이블의 하나의 버킷(Bucket)에 여러 개의 항목을 저장: 체이닝(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;
void init(Student** hashTable){
for(int i=0;i<TABLE_SIZE;i++){
if(hashTable[i]!=NULL)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++;
}
}
int search(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(search(hashTable, student->id)==-1){
int index=findEmpty(hashTable, student->id);
add(hashTable, student, index);
}
}
show(hashTable);
destructor(hashTable);
system("pause");
return 0;
}
선형 조사법은 충돌이 발생하기 시작하면, 유사한 값을 가지는 데이터끼리 서로 밀집되는 집중 결합 묹제가 있다.
만일 해시 테이블의 크기가 비약적으로 크다면, 충돌이 적게 발생하므로 매우 빠른 데이터 접근 속도를 가질 수 있다.
이차 조사법
선형 조사법을 약간 변형한 형태로 키 값을 선택할 때, ‘완전 제곱수’를 더해 나가는 방식
조사법의 테이블 크기 재설정
일반적으로 선형 조사법, 이차 조사법 등의 조사법에서 테이블이 가득 차게 되면 테이블의 크기를 확장해서 계속해서 해시 테이블을 유지
체이닝 기법
체이닝(Chaining)기법은 연결 리스트를 사용하서 특정한 키를 가지는 항목들을 연결하여 저장한다.
삽입과 삭제가 용이하다. 다만 동적 할당을 위한 추가적인 메모리 공간이 소모된다는 단점이 있다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.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)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;
}