해시 테이블, 충돌 문제의 해결책

Notice

Recent Posts

Recent Comments

Link

« 2024/09 »
일	월	화	수	목	금	토
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

Tags more

Archives

Today

Total

관리 메뉴

bdfgdfg

해시 테이블, 충돌 문제의 해결책 - 13장(2) 본문

CS/자료구조 알고리즘

해시 테이블, 충돌 문제의 해결책 - 13장(2)

marmelo12 2021. 7. 11. 02:15

충돌 문제의 해결책

일반적으로 충돌의 해결책이란 것이 상식적인 선에서 벗어나지 않는다고 한다.

예를 들어 충돌이 발생하면 충돌이 발생한 그 자리를 대신해 빈 자리를 찾아야 한다.

다만 그 빈 자리를 찾는 방법에 따라서 해결책이 구분될 뿐.

1. 선형 조사법과 이차 조사법

선형 조사법

- 충돌이 발생했을 때 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장하는 것이 바로 '선형 조사법'

예를 들어 밑의 그림과 같이 key % 7의 해시값을 구하는 해시 함수가 있다.

1. 키가 9인 데이터는 해시 값이 2(9 % 7 -> 2)이므로 인덱스 2에 저장이 된다.

2. 이어서 키가 2인 데이터가 등장. 2 % 7 -> 2이므로 인덱스 2에 저장이 할려하지만 이미 9가 저장이 되었기에 충돌!

3. 이렇듯 충돌이 발생했을 때 인덱스 값이 3인 바로 옆자리를 살펴보고 비어있다면 저장.

만약 옆자리가 비어있지 않다면 계속해서 그 옆자리, 또 비어있지않다면 그그 옆자리..

정리하면 k의 키에서 충돌 발생시 선형 조사법의 빈자리를 찾는 순서는 다음과 같이 전개가 된다.

f(k) + 1 -> f(k) + 2 -> f(k) + 3 -> f(k) + 4...

이러한 선형 조사법은 충돌의 횟수가 증가함에 따라 '클러스터(cluster) 현상'.

쉽게 말해 특정 영역에 데이터가 집중적으로 몰리는 현상이 발생한다는 단점이 있다.

그리고 이러한 클러스터 현상은 충돌의 확률을 높이는 직접적인 원인이 된다.

그럼 선형 조사법의 단점은 어떻게 극복할까?

좀 멀리서 빈 공간을 찾는다? 이런 단순한 개념을 적용한게 이차 조사법

이차 조사법의 조사 순서는 다음과 같이 전개가 된다.

f(k) + 1² -> f(k) + 2² -> f(k) + 3² -> f(k) + 4² ................

하지만 이 이차 조사법에도 나름의 문제가 존재한다. 이는 다음 해결책인 '이중 해시'에서 설명.

그리고 앞서 Slot의 상태 정보(SlotStatus)를 별도로 관리해야 하는 이유를 언급해보면.

위 그림에서 키가 9인 데이터를 삭제해 본다.

그러면 다음의 상태가 된다.

0,1,4,5,6,7,8,9는 EMPTY상태. - 슬롯에 데이터가 저장된바 없음.

2는 DELETED 상태. - 슬롯에는 데이터가 저장된적 있으나 현재는 비워진 상태.

3은 INUSE 상태. - 슬롯에는 현재 유효한 데이터가 저장 돼있음.

위의 그림에서 주목할 것은 데이터가 삭제된 후. EMPTY상태가 아닌 DELETED로 두어 EMPTY와 구분한 것이다.

왜 이렇게 했을까? 이것은 충돌과 관련된 문제이기 때문이다.

현재 9와 2라는 Key가 들어갔고. Key % 7에서 둘다 해시값이 2가 나와 3은 그 오른쪽에 저장한 상태.

만약 내가 2라는 Key가 존재하는지 테이블에서 탐색해볼때. 탐색한 그 슬롯이 EMPTY상태라면 데이터가 존재하지 않는다고 판단하여 종료가 되겠지. 실제로 그 옆자리에 2라는 키값이 저장이 되었는데도 불구하고.

그렇기에 EMPTY와 DELETED를 구분한 것.

DELETED상태라면 충돌이 발생했음을 의심할 수 있고, 선형 조사법에 근거한 탐색의 과정을 진행한다.

따라서 다음 두 가지 사실을 추가로 정리해야한다.

1. 선형,이차 조사법과 같은 충돌의 해결책을 적용하기 위해서는 슬롯의 상태에 DELETED를 포함시켜야한다.

2. 선형,이차 조사법을 적용하였다면, 탐색의 과정에서도 이를 근거로 충돌을 의심하는 탐색의 과정을 포함시켜야 한다.

이중 해시

앞서 이차 조사법의 문제점으로 지적되는 사항은 다음과 같다.

"해시 값이 같으면, 충돌 발생시 빈 슬롯을 찾기 위해서 접근하는 위치가 늘 동일하다"

이렇듯 해시 값이 같을 경우 빈 슬롯을 찾아서 접근하는 위치가 동일하기에 선형 조사법보다는 낫지만,

접근이 진행되는 슬롯을 중심으로 클러스터 현상이 발생할 확률은 여전히 높을 수밖에 없다.

이중 해시는 이 이차 조사법의 멀리서 빈 공간을 찾는 규칙(제곱)을 불규칙하게 구성하는 것.

이중 해시는 두 개의 해시 함수를 사용하기 때문에 붙여진 이름.

두개의 해시 함수를 설명해보면

1차 해시 함수 : 키를 근거로 저장위치를 결정하기 위한 것

2차 해시 함수 : 충돌 발생시 몇칸 뒤를 살필지 결정하기 위한 것

이제 이중 해시의 두 해시 함수를 정의해보고 배열을 저장소로 하는 테이블이 존재한다고 가정한다.

1차 해시 함수 : hashfunc1(k) = k % 15.

이렇게 이중 해시의 1차 해시 함수가 결정되면 다음 식을 근거로 이중 해시의 2차 해시함수를 결정.

2차 해시 함수 : hashfunc2(k) = 1 + (k % c)

1차 해시함수의 경우. 배열의 길이를 넘어서지 않기위해(%15를 한 이유) % 15로 해시값을 구한다.

이 때 충돌이 발생한다면 2차 해시 함수를 사용.

hashfunc2(k) = 1 + (k % c).

참고로 저기 c에서는 1차 해시값의 최대값을 고려하여(15보다 작은) 소수중 하나의 값을 택한다.

소수를 택하는 이유는 소수를 선택했을 때 클러스터 현상의 발생확률이 현저히 낮아진다는 통계가 존재한다고 한다.

그리고 1을 더하는 이유는 2차 해시값이 0이 나오는 것을 막기 위함.

충돌 발생 이후에 다른 자리를 살피는데 0이 되면 안되므로.

이제 이중 해시 함수의 활용의 예를 보자. 앞서 정의한 1차 해시 함수에 세 개의 키를 적용해본다.

1. Key 3 -> 3 % 15 = 3

2. Key 18 -> 18 % 15 = 3

3. Key 33 -> 33 % 15 = 3

세개다 해시 값이 3이 나온다.

Key3은 먼저 들어왔으므로 그대로 인덱스 3에 위치. 다만 그 뒤의 Key 18과 33은 충돌이 일어나기에

2차 해시 함수를 사용한다.

위 그림과 같이 1차 해시값이 같더라도 2차 해시값은 다르게 나온다.

이런식으로 이중 해시는 충돌이 일어날 경우 2차 해시 값의 크기만큼(불규칙하게) 건너 뛰면서

빈슬롯을 찾게 되므로, 키가 다르면 건너 뛰는 길이도 달라진다.

따라서 클러스터 현상의 발생 확률을 현저히 낮출 수 있다.

실제로도 이중 해시는 이상적인 충돌 해결책이다.

체이닝

이 체이닝 충돌 해결책은 앞서 소개한 방법들과 해결방식이 근본적으로 다르다.

앞서 소개한 유형의 방법들을 가리켜 '열린 어드레싱 방법'이라 하는데 이는 충돌이 발생하면

다른 자리에 대신 저장한다는 의미가 담겨 있다.

반면 이 체이닝 방법을 가리켜 '닫힌 어드레싱 방법'이라 한다.

그리고 여기에는 무슨 일이 있어도 자신의 자리에 저장을 한다는 의미가 담겨 있다.

즉 충돌을 해도 무조건 그 자리에 저장한다는 것이다.

그것이 가능한 이유는 자리를 여러 개 마련하는 것.

(링크드 리스트 배열, 혹은 벡터배열-인접 리스트 방식)

다만 위의 그림은 이 여러개의 공간이 고정되어 있다.

이는 닫힌 어드레싱 방법중에서는 흔히 거론되는 방법이 아니다.

충돌이 발생하지 않을 경우 메모리 낭비가 심하고, 또 충돌의 최대 횟수를 결정해야 하는 부담도 존재하기 때문이다.

따라서 '체이닝'은 연결 리스트를 이용해 슬롯을 연결하는 방법이 닫힌 어드레싱 방법을 대표한다.

이렇게 슬롯을 생성하여 연결 리스트의 모델로 연결해나가는 방식으로 충돌 문제를 해결하는것이

'체이닝' 방법.

위 방법은 좋은 해시 함수를 잘 정의하고 충돌의 확률이 높지 않다면 연결된 슬롯의 길이는 부담되지 않아

탐색을 위해 해당 인덱스의 모든 슬롯을 찾는 연산은 부담 스럽지 않을 것이다.

체이닝의 구현

앞서 구현한 Person,Slot,Table의 헤더와 cpp파일을 확장하여 구현한다.

다만 구현하기전 앞서 Slot의 상태를 기억해야 했던 이유가 사라지기에(선형,이차,이중 조사법을 위한 녀석들)

내부 코드의 수정이 필요하다.

먼저 Slot의 헤더.

#pragma once

class Person;

class Slot
{
public:
	Slot();
	~Slot() = default; // Slot의 소멸은 연결 리스트에서.
	Slot(int key, Person* value) : m_key(key), m_value(value)
	{

	}
	int			m_key;
	Person*		m_value;
};

그다음 Table의 헤더

#pragma once

class Slot;
class Person;
class LinkedList; // 추가.

typedef int (HashFunc)(int Key); // 함수포인터 


class Table
{
public:
	Table() = delete;
	Table(HashFunc f);
	~Table();
	void TBLInsert(int key, Person* value); // 삽입
	Person* TBLDelete(int key); //삭제
	Person* TBLSearch(int key); // 탐색
private:
	enum { MAX = 100 }; 
	LinkedList*	  tbl; // 변경 연결리스트.
	HashFunc* hf;
};

그리고 연결 리스트와 Slot의 관계를 이어주기 위해.

class Slot;

class Node // Slot*형 데이터를 담는 노드.
{
public:
	Node();
	Node(Slot* data);
	~Node() = default;
	Slot* GetData() const;
	void SetData(Slot* item);
	Node* GetNextNode() const;
	Node* GetPrevNode() const;
	void SetPrevNode(Node* prev);
	void SetNextNode(Node* next);
private:
	Slot* m_data;
	Node* m_prev;
	Node* m_next;
};

위와 같이 데이터의 자료형을 Slot*로 바꿔준다. (물론 cpp파일도 고쳐줘야한다.)

즉. 노드의 안에서 다른 메모리에 생성된 슬롯을 가리키는 형태의 그림. 포인터 변수를 가진다.

물론 Slot*가 아닌 Slot 그 자체를 담을 수 있지만, 구분을 하기 쉽게 내부에 저장하지 않는다.

이제 변경된 Table의 cpp.

#include <iostream>
#include "Table.h"
#include "Slot.h"
#include "LinkedList.h"
#include "Person.h"


Table::Table(HashFunc f) : hf(f)
{
	tbl = new LinkedList[MAX];
}
Table::~Table()
{
	std::cout << "Table 소멸자 호출~" << std::endl;
	delete[] tbl;
}

void Table::TBLInsert(int key, Person* value)
{
	int hashValue = hf(key); // 해시함수를 통해 해시값얻어오기.
	Slot* ns = new Slot(key,value);
	
	if (TBLSearch(key) != nullptr) // 키 중복.
	{
		return;
	}
	else
		tbl[hashValue].push_front(ns);
}

Person* Table::TBLDelete(int key)
{
	int hashValue = hf(key);
	Slot* cSlot;
	Person* delPerson;

	if (tbl[hashValue].LFirst())
	{
		cSlot = tbl[hashValue].iterator()->GetData();
		if (cSlot->m_key == key)
		{
			delPerson = cSlot->m_value;
			tbl[hashValue].pop_cur(); // 노드 메모리 해제.
			delete cSlot; // cSlot 메모리 해제.
			return delPerson; // 사람 개체는 호출한 대상에게 반환(메모리 해제는 맡김)
		}
		else
		{
			while (tbl[hashValue].LNext())
			{
				cSlot = tbl[hashValue].iterator()->GetData();
				if (cSlot->m_key == key)
				{
					delPerson = cSlot->m_value;
					tbl[hashValue].pop_cur(); // 노드 메모리 해제.
					delete cSlot;  // cSlot 메모리 해제.
					return delPerson;  // 사람 개체는 호출한 대상에게 반환(메모리 해제는 맡김)
				}
			}
		}
	}
	return nullptr; 
}

Person* Table::TBLSearch(int key)
{
	int hashValue = hf(key);
	Slot* cSlot;

	if (tbl[hashValue].LFirst())
	{
		cSlot = tbl[hashValue].iterator()->GetData();
		if (cSlot->m_key == key)
			return cSlot->m_value;
		else
		{
			while (tbl[hashValue].LNext())
			{
				cSlot = tbl[hashValue].iterator()->GetData();
				if (cSlot->m_key == key)
					return cSlot->m_value;
			}
		}
	}

	return nullptr; // 존재하지않음.
}

그리고 pop_cur() -> 노드 삭제부분

Slot* LinkedList::pop_cur()
{
	if (this->m_size <= 0)
		return nullptr;

	Node* prevNode = this->m_cur->GetPrevNode();
	Node* nextNode = this->m_cur->GetNextNode();
	Node* delNode = this->m_cur;
	Slot* data = delNode->GetData();

	prevNode->SetNextNode(delNode->GetNextNode());
	nextNode->SetPrevNode(delNode->GetPrevNode());
	--this->m_size;
	delete delNode;
	return data;
}

해시 테이블의 기능은 어렵지 않다.

다만 소멸자에서 꼭 메모리 해제는 잊으면 안된다. 위 그림에서 테이블의 소멸자에서 링크드 리스트를 해제하는 모습.

밑은 링크드 리스트 소멸자

LinkedList::~LinkedList()
{
	for (int i = 0; i < m_size; ++i)
		pop_front();
	
	delete m_head; // 더미노드삭제
}

void LinkedList::pop_front() // 지워지지 않은 노드들.
{
	if (this->m_size <= 0)
		return;
	Node* popNode = this->m_head->GetNextNode();
	Node* popNextNode = popNode->GetNextNode();
	popNextNode->SetPrevNode(this->m_head); // 두번째 노드의 이전은 사라짐.
	this->m_head->SetNextNode(popNextNode);
	Slot* data = popNode->GetData();
	--(this->m_size);
	if (data != nullptr)
	{
		if (data->m_value != nullptr)
		{
			delete data->m_value;
			delete data;
		}
		else
			delete data;
	}
	delete popNode;
}

테이블에서 링크드 리스트를 100개를 담으므로 100번의 소멸자가 호출된다.

그리고 더미노드도 삭제.

main.cpp



int MyHashFunc(int k)
{
	return k % 100; 
}


int main()
{
	Table myTbl(MyHashFunc);
	Person* np;
	Person* sp;
	Person* rp;

	np = new Person(900254, "Lee", "Seoul");
	myTbl.TBLInsert(np->GetSSN(), np);

	np = new Person(900139, "Kim", "Jeju");
	myTbl.TBLInsert(np->GetSSN(), np);

	np = new Person(900827, "HAN", "Kangwon");
	myTbl.TBLInsert(np->GetSSN(), np);

	np = new Person(900345, "kim", "Kang"); // TBLDelete 진행 안함. -> 노드,슬롯, Person 메모리 해제안됨. 이것은 링크드리스트 소멸자에서 해제.
	myTbl.TBLInsert(np->GetSSN(), np);

	sp = myTbl.TBLSearch(900254);
	if (sp != nullptr)
		sp->ShowPerInfo();

	sp = myTbl.TBLSearch(900139);
	if (sp != nullptr)
		sp->ShowPerInfo();

	sp = myTbl.TBLSearch(900827);
	if (sp != nullptr)
		sp->ShowPerInfo();


	rp = myTbl.TBLDelete(900254);
	if (rp != nullptr)
		delete rp;

	rp = myTbl.TBLDelete(900139);
	if (rp != nullptr)
		delete rp;

	rp = myTbl.TBLDelete(900827);
	if (rp != nullptr)
		delete rp;



	return 0;
}

실행결과.

Person 개체의 메모리해제는 main.cpp에서. (해시테이블에서 데이터를 제거할 때. -> TBLDelete)

만약 삭제가 안되었다면 링크드리스트의 소멸자에서 남아있는 노드의 수를 확인하고 노드,슬롯,사람 메모리를 해제.

TBLDelete를 진행하면서 키가 존재한다면 현재 슬롯의 주소를 담고있는 노드를 대상으로 슬롯 메모리해제 + 노드 메모리 해제. 사람 개체는 호출한 대상이 제거.

'CS > 자료구조 알고리즘' 카테고리의 다른 글

깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) - 14장 (2) (0)	2021.07.12
그래프(Graph)의 이해와 종류 - 14장 (1) (0)	2021.07.11
해시 테이블(hash table) - 13장(1) (0)	2021.07.10
보완된(균형 잡힌)이진 탐색 트리의 구현 - 12장(2) (0)	2021.07.09
이진 탐색 트리 - 11장 (0)	2021.07.07

'CS/자료구조 알고리즘' Related Articles

Comments