[DATASTRUCTURE] Hash Table

ALGORITHM/ALGORITHM STUDY

[DATASTRUCTURE] Hash Table

l_j_yeon 2017. 3. 30. 19:23

[ 충돌(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

저작자표시 비영리 변경금지 (새창열림)