[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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

#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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259

#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

?

1 2 3 4 5 6 7

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