[DATASTRUCTURE] Hash Table

[ 충돌(collision) ]

- 두 개 이상의 키가 동일한 위치로 해싱되는 경우

- 대표적인 두 가지 충돌 해결 방법: chaining과 open addressing

출처 : http://blog.naver.com/kts1801/220956548474

Linear Probing의 단점

- 해시테이블에서 할당도니 공간이 연속해서 나타나는 뭉치가 있으면 이것이 점점 커지는 현상이 발생할 수 있는데, 이것을 집적화(Clustering)라고 부른다.

- 클러스터링이 생기면 데이터 삽입 시 비어 있는 공간을 찾는 시간이 길어진다. 즉, 평균 탐색 시간을 증가시켜 성능을 저하시킴.

출처 : http://blog.naver.com/kts1801/220956548474

[출처] [해싱] - 충돌(Collision), 연쇄법(Chaing), 선형 탐사법(Linear Probing)|작성자 moo

+) 인하대학교 심정섭 교수님 자료구조 강의 자료

   아래의 문제는 심정섭 교수님 자료구조 과제를 구현한 코드입니다. (2016)

table.h

#pragma once #include <iostream> #include <fstream> #include <string> using namespace std; #define DELETED -1 #define NULL 0 #define SEARCH_FOR_DELETE -1 #define SEARCH_FOR_INSERT -2 #define SEARCH -3 #define STUDENT_UNAVAILABLE -1 #define STUDENT_AVAILABLE -2 #define IS_STUDENT_AVAILABLE Original[Key].Student_ID==Student_ID #define IS_STUDENT_ID_NULL Original[Key].Student_ID == NULL #define IS_STUDENT_DELETE_FLAG_NULL Original[Key].Delete_Flag == NULL #define IS_COMMAND_FLAG_SEARCH Command_Flag == SEARCH #define IS_COMMAND_FLAG_DELETE Command_Flag == SEARCH_FOR_DELETE #define IS_COMMAND_FLAG_INSERT Command_Flag == SEARCH_FOR_INSERT #define IS_CANT_INSERT Insert_Flag < 0 #define IS_CANT_DELETE Search_Flag ==STUDENT_UNAVAILABLE typedef struct Student { int Student_ID; string Student_Name; string Student_Major; int Student_Grade; int Delete_Flag; }Student_Def; Student_Def* Student_Table; Student_Def* Insert_Student_Table; // Insert시 Struct입력 받는 Struct Student_Def*Student_Insert = new Student_Def; fstream fcin_input,fcin_command; int Hash_Key_1, Hash_Key_2,Key_1,Key_2,Command_Flag=0,Probe; void Insert_Struct(Student_Def*Original, Student_Def*Insert); void Constructor(); void Initialize_Struct(Student_Def*Temp, int count); void Command(); int Hash_Table_Key_1(int Data); int Hash_Table_Key_2(int Data); int Mod(int Data); void Insert(Student_Def*Original, Student_Def*Insert); int Search(Student_Def*Original, int Student_ID,int Command_Flag); void Delete(Student_Def*Original, int Student_ID);

function.h

#pragma once #include "table.h" /***** 첫번 째 KEY를 계산하는 함수 *****/ // 매개변수 : 학생의 ID // 반환 값 : Key_1 /***************************************/ int Hash_Table_Key_1(int Data) { return Data%Hash_Key_1; } /***** 첫번 째 KEY를 계산하는 함수 *****/ // 매개변수 : 학생의 ID // 반환 값 : Key_2 /***************************************/ int Hash_Table_Key_2(int Data) { return Hash_Key_2 - Data%Hash_Key_2; } /***** MOD연산을 하는 함수 *****/ // 매개변수 : Key // 반환 값 : Hash_Table의 개수로 나누어진 Key의 나머지 /***************************************/ int Mod(int Data) { return Data%Hash_Key_1; } /***** 초깃값 설정 함수 *****/ void Constructor() { fcin_input.open("input.txt"); int i = 0; fcin_input >> Hash_Key_1 >> Hash_Key_2; Student_Table = new Student_Def[Hash_Key_1]; // 기본 Struct Insert_Student_Table = new Student_Def[Hash_Key_1]; // 들어온 값을 저장하는 Struct Initialize_Struct(Student_Table, Hash_Key_1); // Struct 초기화 Initialize_Struct(Insert_Student_Table, Hash_Key_1); // Struct 초기화 while (!fcin_input.eof()) // File이 끝날 때 까지 { fcin_input >> Insert_Student_Table[i].Student_ID >> Insert_Student_Table[i].Student_Name >> Insert_Student_Table[i].Student_Major >> Insert_Student_Table[i].Student_Grade; i++; } // Insert_Hash_Table을 규칙에 맞게 Student_Table에 넣는 함수 for (int j = 0; j < i; j++) Insert_Struct(Student_Table, &Insert_Student_Table[j]); } /***** Insert_Hash_Table을 규칙에 맞게 Student_Table에 넣는 함수 *****/ void Insert_Struct(Student_Def*Original, Student_Def*Insert) { int Student_ID, Key; Student_ID = Insert->Student_ID; Key_1 = Hash_Table_Key_1(Student_ID); Key_2 = Hash_Table_Key_2(Student_ID); Key = Key_1; while (1) { // Hash_Table에서 값이 없다면 삽입 if (Original[Key].Student_ID == NULL) { Original[Key].Student_ID = Insert->Student_ID; Original[Key].Student_Name = Insert->Student_Name; Original[Key].Student_Major = Insert->Student_Major; Original[Key].Student_Grade = Insert->Student_Grade; Original[Key].Delete_Flag = NULL; break; } // Hash_Table에서 값이 있다면 다음 Key값으로 else { Key += Key_2; Key = Mod(Key); continue; } } } /***** Struct 초기화 함수 *****/ void Initialize_Struct(Student_Def*Temp, int count) { for (int i = 0; i < count; i++) { Student_Table[i].Student_ID = NULL; Student_Table[i].Delete_Flag = NULL; } } /***** Command 실행함수 *****/ void Command() { char Command; int Student_ID; fcin_command.open("command.txt"); while (!fcin_command.eof()) { fcin_command >> Command; switch (Command) { case 's' | 'S': fcin_command >> Student_ID; Search(Student_Table, Student_ID, SEARCH); break; case 'i' | 'I': Initialize_Struct(Student_Insert, 1); fcin_command >> Student_Insert->Student_ID >> Student_Insert->Student_Name >> Student_Insert->Student_Major >> Student_Insert->Student_Grade; Insert(Student_Table, Student_Insert); break; case 'd' | 'D': fcin_command >> Student_ID; Delete(Student_Table, Student_ID); break; } } } /*********************** Struct Insert 함수 ***********************************/ // 매개변수 : Student_Table(원래의 Table), Insert_Table(삽입해야할 테이블), Key값 /********************************************************************************/ void Change_Student_Table(Student_Def*Original, Student_Def*Insert, int Key) { Original[Key].Student_ID = Insert->Student_ID; Original[Key].Student_Name = Insert->Student_Name; Original[Key].Student_Major = Insert->Student_Major; Original[Key].Student_Grade = Insert->Student_Grade; Original[Key].Delete_Flag = NULL; } /*********************************************** Search 함수 *****************************************************/ // 매개변수 : Student_Table(원래의 Table), Insert_Table(삽입해야할 테이블), 무엇을 위해 Search하는지에 관련된 Flag /******************************************************************************************************************/ int Search(Student_Def*Original, int Student_ID, int Command_Flag) { Key_1 = Hash_Table_Key_1(Student_ID); Key_2 = Hash_Table_Key_2(Student_ID); int Key = Key_1; Probe = 0; while (1) { Probe++; // 학생 ID가 0이면 if (IS_STUDENT_ID_NULL) { // DELETE된 적이 없으면 if (IS_STUDENT_DELETE_FLAG_NULL) { // SEARCH : 값이 없음 if (IS_COMMAND_FLAG_SEARCH) { cout << "없음 " << Probe << endl; break; } // DELETE : 삭제 할 수 없음 if (IS_COMMAND_FLAG_DELETE) { return STUDENT_UNAVAILABLE; } // INSERT : 삽입 가능 if (IS_COMMAND_FLAG_INSERT) { return Key; } } // DELETE된 적이 있으면 else { Key += Key_2; Key = Mod(Key); continue; } } else { // Student_ID가 맞을 때 if (IS_STUDENT_AVAILABLE) { // SEARCH : 찾음 if (IS_COMMAND_FLAG_SEARCH) { cout << Student_Table[Key].Student_ID << " " << Student_Table[Key].Student_Name << " " << Student_Table[Key].Student_Major << " " << Student_Table[Key].Student_Grade << " " << Probe << endl; break; } // DELETE : 삭제가능 if (IS_COMMAND_FLAG_DELETE) { return Key; } // INSERT : 삽입 불가능 if (IS_COMMAND_FLAG_INSERT) { return STUDENT_UNAVAILABLE; } } // Student_ID가 맞지 않을 때 else { Key += Key_2; Key = Mod(Key); continue; } } } } /************************* DELETE 함수 **************************/ // 매개변수 : Student_Table(원래의 Table), 삭제해야하는 Student_ID /******************************************************************/ void Delete(Student_Def*Original, int Student_ID) { int Search_Flag = Search(Original, Student_ID, SEARCH_FOR_DELETE); // 삭제할 수 없음 if (IS_CANT_DELETE) { cout << "삭제할 수 없음 " << Probe << endl; } // 삭제 가능 else { Original[Search_Flag].Delete_Flag = DELETED; Original[Search_Flag].Student_ID = NULL; cout << Probe << endl; } } /************************* INSERT 함수 **************************/ // 매개변수 : Student_Table(원래의 Table), 삽입해야하는 Student 정보 /******************************************************************/ void Insert(Student_Def*Original, Student_Def*Insert) { int Student_ID = Insert->Student_ID; int Insert_Flag = Search(Original, Student_ID, SEARCH_FOR_INSERT); // 삽입할 수 없음 if (IS_CANT_INSERT) { cout << "추가할 수 없음 " << Probe << endl; } // 삽입 가능 else { Change_Student_Table(Original, Insert, Insert_Flag); cout << Probe << endl; } }

Hash_Table.h

#include "function.h" int main() { Constructor(); Command(); system("pause"); }