데이터의 추가, 삭제, 수정, 검색 - 해시 테이블 응용

삼성 B형 전체 링크

참고
- 해시 테이블 Hash Table
- 해시 테이블 추가, 삭제, 수정, 검색
- 해시 응용 - 2차원 배열 탐색
- 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용)
- 해시 테이블 성능 비교

해시 테이블의 기본을 응용하여, 추가/삭제/수정에 대해 알아보자.

---

어떤 게임의 DB에 아래와 같은 데이터가 있다고 가정해보자.
이 게임은 ID가 중복으로 있을 수 있다.

운영자는 이 DB를 관리해야하는데, 다음과 같은 기능이 필요하다.

1) 새로운 DB를 추가.
2) 현재 DB 중 특정 DB 삭제. (ID가 xxx인 DB 삭제, JOB이 wizard인 DB 삭제 등)
3) 현재 DB 중 특정 DB 수정. (JOB이 yyy인 DB에서 SERVER를 nova로 변경 등)
4) 현재 DB 검색해서 결과 return. (JOB이 archer인 DB가 몇 개인지 return)

이제 이러한 상황을 삼성 B형에서 나온 문제라고 가정하자.
거의 100% 확률로 해시 테이블을 사용해서 풀어야 한다.
왜냐하면 ID, JOB, SERVER 모두 string이므로, hasing하기 좋고, O(1)만에 해당 DB로 접근해야 성능이 보장된다.

이제 1) ~ 4)의 함수가 어떻게 구성되어있는지 알아보자.

 1) void addDB(char *id, char *job, char *server)
 id, job, server를 받아서 DB에 저장.

 2) int deleteDB(int key, char *str)
 id = 0, job = 1, server = 2에 대한 key가 주어진다.
 key : str을 가진 모든 DB를 지우고 개수를 return한다.

 3) int updateDB(int key, char *str, int ukey, char *ustr)
 id = 0, job = 1, server = 2에 대한 key와 update key가 주어진다.
 key : str을 가진 모든 DB를 ukey : ustr로 변경하면 된다.
 변경된 DB의 개수를 return 한다.

 4) int searchDB(int key, char *str)
 id = 0, job = 1, server = 2에 대한 key가 주어진다.
 key : str을 가진 모든 DB의 개수를 return한다.

---

이제 4개의 함수를 구현하기 위해 hash table을 설계해보자.
여기서 data의 총 갯수는 50,000 정도라고 가정하자.

모든 key에 대해 4가지 함수가 효율적으로 사용되려면, hash table을 3개 만들어야 한다.
id에 대해서도 빠른 접근이 필요하고, job, server에 대해서도 빠른 접근이 필요하기 때문이다.
따라서 id에 대한 hash table과 job, server에 대한 hash table 3개를 만들어서, 각 key에 대해서 바로 접근하자.

그런데 hash table에 id, job, server를 모두 복사하는 것은 굉장히 비효율적이다.
이때, 사용할 수 있는 것이 포인터이다.

DB에 대한 자료는 순서대로 저장하고, hash table은 그 DB를 가르키기만 하면 된다.
(회사에 있는 사람 문제 참고)

따라서, 메모리 풀을 이용하여 아래와 같이 선언할 수 있다.

#define MAX_DATA (79943) /* N = 50000의 약 1.5 ~ 2배 사이의 prime number */

typedef struct st
{
	char data[3][25]; /* id = 0, job = 1, server = 2 */
}DB;

DB POOL[50010]; /* DB에 대한 memory pool */
int pcnt;

typedef struct st2
{
	DB *db; /* hash에 직접 복사하지말고 DB만 가르킨다 */
	struct st2 *next;
}HASH;

HASH hash[5][MAX_DATA];
HASH MEMORY[250500]; /* hash table에 대한 memory pool */
int hcnt;

DB의 init은 메모리 풀의 index를 초기화 하고, Hash의 head를 모두 0으로 만들어주면 된다.

void InitDB()
{
	hcnt = cnt = 0;

	for (register int i = 0; i < 5; i++)
		for (register int k = 0; k < MAX_DATA; k++)
			hash[i][k].next = 0;
}

그리고 data가 문자열이기 때문에 문자열 비교 함수와 복사 함수는 외워두자.

void mystrcpy(char *a, char *b)
{
	while (*a++ = *b++);
}

int mystrcmp(const char *a, const char *b)
{
	while (*a && *a == *b) ++a, ++b;
	return *a - *b;
}

그리고 참조 코드에서 hashing 함수를 이용하자.

typedef unsigned long long int ll;

ll hash(char *str)
{
	unsigned long hash = 5381;
	int c;

	while (c = *str++)
	{
		hash = (((hash << 5) + hash) + c) % MAX_DATA;
	}

	return hash % MAX_DATA;
}

---

이제 본격적으로 4가지 함수를 구현해보자.

addDB에는 id, job, server가 넘어온다.
DB에 순서대로 저장하면 된다.

void addDB(char *id, char *job, char *server)
{
	DATA *db = &POOL[pcnt++];
	mstrcpy(db->data[0], name);
	mstrcpy(db->data[1], number);
	mstrcpy(db->data[2], birthday);
    
    ...
}

이제 hash table을 저장해보자.
총 3개의 hashing이 필요하고, 각 테이블마다 DB를 가르키도록 해야 한다.

void addDB(char *id, char *job, char *server)
{
	... /* DB 저장 */
    
    HASH *hashTable[5];
    ll h[3];
    
    h[0] = hash(id);
	h[1] = hash(job);
	h[2] = hash(server);
    
    /* id에 대한 hashTable */
    hashTable[0] = &MEMORY[hcnt++]; 
	hashTable[0]->db = db;

	/* job에 대한 hashTable */
	hashTable[1] = &MEMORY[hcnt++];
	hashTable[1]->db = db;

	/* server에 대한 hashTable */
	hashTable[2] = &MEMORY[hcnt++];
	hashTable[2]->db = db;
    
    for (register int i = 0; i < 3; i++)
	{
		hashTable[i]->next = Hash[i][h[i]].next;
		Hash[i][h[i]].next = hashTable[i];
	}
}

add를 구현하면 위의 코드에 의해 3개의 hashTable이 만들어진다.

hash table [0] = ID에 대한 hash table이다.

만약 harry, ron이 1로 충돌이 일어나고, potter = 5, weasley = 6이 된다고 가정하자.
Linked List 구현에 의해 순서가 거꾸로 저장된다.
그림에는 편의상 index를 저장하게 했지만, 실제로는 DB[index]의 주소가 저장된다.
harry, ron이 id인 0, 2, 5, 6 DB가 hash table[1]에 모두 저장되고,
각 hash table의 DB* db가 원래의 DB를 가르키고 있게 된다.

마찬가지로 JOB과 SERVER에 대한 hash table이다.

DB는 1개지만, 3개의 hash table이 DB[index]를 가르키고 있다.

---

이제 DB를 삭제해보자.
먼저 ID = harry인 DB를 삭제한다고 가정하자.
그러면 int deleteDB는 2를 return해야하고 DB[0]과 DB[5]를 삭제해야 한다.
보통 실제 DB는 놔두고 hash table의 연결을 끊으면 된다. (삭제 예시는 링크 참고)

그러나 문제는 다른 hash table에서도 연결을 끊어야 한다는 것이다.
ID = harry라면, hash table[0]은 harry를 hashing하여 접근하고, id = harry인지 확인하여 삭제하면 된다.
하지만 job table과 server table은 불가능하기 때문에, 전체 table을 뒤져서 id가 harry인 것을 찾아야 한다.

이렇게 되면 hash table로 O(1)만에 data를 찾은 의미가 없다.

하지만 이 문제는 더 간단한 방법으로 해결할 수 있다.
hash table 3개 모두 같은 DB를 가르키고 있다는 것을 주목하자.
즉, 이 DB 중 어떤 DB가 삭제되었다면, "나는 현재 삭제된 상태다" 라는 것을 표시할 flag만 하나 있으면 된다.

DB의 구성을 아래처럼 바꿀 수 있다.

typedef struct st
{
	char data[5][25];
	int deleteFlag;
}DB;

이렇게 해두면, id table에서 deleteFlag = 1이라고 변경해두면, 다른 두 table에서 접근할 때, flag를 확인만 하면 된다.

구현 코드를 참고하자.

int Delete(int key, char *str)
{
	register int cnt;
	ll h = hash(str);
    
	HASH *p;
	DB *tmp;
	cnt = 0;

	p = &Hash[key][h];
	while (p->next)
	{
		tmp = p->next->db;
		if (!mstrcmp(tmp->data[key], str) && !tmp->deleteFlag) /* 삭제되었는지 체크 */
		{
			tmp->deleteFlag = 1; /* 다른 두 table을 위한 삭제 */
			p->next = p->next->next; /* 현재 table의 물리적인 삭제, link를 끊음 */

			cnt++;
		}
		else
			p = p->next;
	}

	return cnt;
}

flag = 1은 다른 table에서도 삭제 효과를 내기 위한 방법이다.
flag에서 삭제된 table을 지나치도록 if문을 만들면 된다.

그리고 p->next = p->next-next는 현재 table에서 실제로 다음 검색에 linked list에 검색되지 않도록
물리적으로 삭제하는 코드이다.

이 코드가 빠져도, 성능에 큰 영향은 없다.(고 생각된다.) 어짜피 다른 두 table을 물리적으로 link를 끊지 않기 때문이다.

---

data의 수정은 더 까다롭다.
이유는 hash값이 변경되기 때문이다.

key가 potter인 DB의 job을 모두 thief로 바꾼다고 가정하자.
그러면 DB[1], DB[4]가 바뀌어야 한다.

DB[1]의 경우는 [potter, warrior, windia]를 [potter, thief, windia]로 바뀌게 된다.
이 경우, id table과 server table은 hash를 유지하지만 job table은 warrior의 hash(3)와 thief의 hash(6)가 달라진다.
따라서, job key로 job을 변경하면, job의 hash table이 의미가 없어진다.

하지만, 수정만큼 간단한 구현 방법은 없다. 왜냐하면, 이미 모두 구현했기 때문이다.
그냥 해당 데이터를 삭제하고, 새로 추가하면 된다.

즉, 기존의 [potter, warrior, windia]의 deleteFlag = 1로 설정해두고,
[potter, thief, windia]를 add 함수로 다시 추가하면 data의 수정이 완성된다.

int updateDB(int key, char *str, int ukey, char *ustr)
{
	register int cnt;
	ll h = hash(str);
    
	cnt = 0;

	for (register HASH *p = Hash[key][h].next; p; p = p->next)
	{
		if (!mstrcmp(p->db->data[key], str) && !p->db->deleteFlag)
		{
			p->db->deleteFlag = 1; /* 현재 db는 삭제 */

			DB db; /* 새로운 db 추가 */

			for (register int i = 0; i < 5; i++) /* 값 복사 */
			{
				if (i == ukey) continue;
				mstrcpy(db.data[i], p->db->data[i]);
			}

			mstrcpy(db.data[ukey], ustr); /* 수정된 key 복사 */

			Add(db.data[0], db.data[1], db.data[2]); /* data 추가 */
			cnt++;
		}
	}

	return cnt;
}

update에 의해서 Add가 추가로 일어나기 때문에 DB의 POOL도 추가되어야 한다.
update도 50,000회 일어난다면, POOL은 총 100,000 이상이 필요하다.

typedef struct st
{
	char data[3][25]; /* id = 0, job = 1, server = 2 */
}DB;

DB POOL[50010 + 50010]; /* DB에 대한 memory pool -> update에 대한 메모리 추가 */
int pcnt;

---

search는 지금까지 hash table의 기본이다. 코드만 참고하자.

int searchDB(int key, char *str)
{
	register int cnt;
	ll h = hash(str);
	cnt = 0;
	
    /* 같으면 counting */
	for (register HASH *p = Hash[key][h].next; p; p = p->next)
		if (!mstrcmp(p->db->data[key], str) && !p->db->deleteFlag) cnt++;

	return cnt;
}