해시(선형 조사법)

 

 

 

 

 

해시?

: 특정한 값을 찾고자 할 때는 그 값의 키(Key)로 접근 가능. 일반적으로 해시 함수는 연산으로 이루어져 있다.

 

1) 데이터를 최대한 빠른 속도로 관리하도록 도와주는 자료 구조.

2) 메모리 공간이 많이 소모되지만 매우 빠른 속도로 데이터를 처리할 수 있습니다.

3) 빠르게 데이터에 접근할 수 있다는 점에서 데이터베이스 등의 소프트웨어에서 활용됩니다.

 

 

 

 

해시함수의 동작 과정

 

데이터                                                                                                        키                  값

101 / A                                         해시 함수                                                  1                   A

203 / B                                        (n mod 100) -> 100으로 나눈 나머지값             2                   C    

202 / C                                                                                                       3                   B 

304 / D                                                                                                       4                   D

 

 

 

 

해시 충돌

                                        해시 함수                       키         값

101 / A                             (n mod 100)                     1          A

201 / B                                                                  1    (충돌 발생)      B  

 

 

 

 

해시 충돌을 처리하는 방법

 

선형 조사법

 

                                        해시 함수                       키                      값

101 / A                             (n mod 100)                     1                        A

201 / B                                                                  1 (충돌 발생)         B  

                                       (->다음칸을 확인후 비어있으면 다음칸에 저장 ->비어있지 않다면 그 다음칸 확인 반복 )

 

 

                                        해시 함수                       키                      값

101 / A                             (n mod 100)                     1                        A

201 / B                                                                  2                        B  

 

 

단점

-충돌이 발생하기 시작하면, 유사한 값을 가지는 데이터끼리 서로 밀집되는 집중 결합 문제가 발생한다.

 

 

 

 

 

 

https://github.com/leejunhyeob/MyProject   

파일명:LinearProbingHash.c

leejunhyeob/MyProject

선형 조사법 C언어 소스

 

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#define TABLE_SIZE 10001
#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++;
}
}

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;
}