해시 테이블(hash table) - 13장(1)

해시 테이블

탐색에 있어 매우 빠른 결과를 보여주는 자료구조이다. -> 탐색의 시간 복잡도는 O(1).

즉 내가 찾고자 하는 대상을 한번에 찾아내는 방식. 

C++에서도 STL 컨테이너에서 제공하는 해시테이블이 존재한다.

-> std::unordered_map(Key-Value), std::unordered_set(Key)

참고로 앞서 배운 이진 탐색 트리의 컨테이너는 std::map(Key-Value)

 

테이블(Table)

 

위 그림이 테이블.

자료구조 관점에서 위 그림 처럼 저장되는 데이터가 키(key)와 값(value)이 하나의 쌍을 이뤄야 테이블이라 한다.

 

그렇기에 테이블에 저장되는 모든 데이터들은 이를 구분하는 '키'가 있어야 데이터를 구분하는 기준이 된다.

그렇기에 테이블은 키와 관련해 다음과 같은 조건이 존재한다.

 

키(key)가 존재하지 않는 '값'은 저장할 수 없다. 그리고 모든 키는 중복되지 않는다.

(물론 key 그 자체가 value가 될수는 있다.)

 

테이블 자료구조에 대한 좋은 예는 바로 사전(Dictionary). 사전에 적힌 단어(key)와 그에 적힌 설명(value)의 쌍이

매우 많이 담겨있기 때문이다.

 

이제 배열을 기반으로 하는 간단한 테이블을 만들어본다.

typedef struct _empInfo
{
	int empNum; // 직원번호 key
	int age;    // value
}EmpInfo;

int main()
{
	EmpInfo empInfoArr[100]; // 직원들의 정보를 담기위해 선언된 배열
	EmpInfo a,b; 
	int eNum;

	cout << "사번과 나이 입력: ";
	cin >> a.empNum >> a.age;
	empInfoArr[a.empNum] = a; // empNum은 키값.

	cout << "직원 사번 입력 : ";
	cin >> eNum;

	b = empInfoArr[eNum]; // 단번에 탐색
	cout << "사번 : " << b.empNum << " 나이 : " << b.age;

	return 0;
}

결과

매우 간단한 테이블이지만 해시 테이블의 탐색의 이론은 위와 같다.

즉 직원 번호(key)를 인덱스값으로 하여 값(value)을 탐색한 것.

 

이렇게 테이블에서 키의 값은 저장위치(인덱스)와 관련이 있다. 그렇기에 단번에 탐색이 가능한 것.

 

그렇다면 직원 번호 범위가 100000 ~ 999999이면 무식하게 그정도 크기의 배열을 만들어야 할까?

이것이 저장이 조금 까다로운 이유. 이것을 해결하기 위해 그냥 테이블이 아닌 해시 테이블이라 불린다.

 

 

테이블에 의미를 부여하는 해시 함수와 충돌문제

앞선 예제에서 보인 테이블과 관련한 문제점은 두가지.

1. 직원 번호의 범위가 배열의 인덱스 값으로 사용하기에 적당하지가 않다. 

2. 직원 번호의 범위를 수용할 수 있는 매우 큰 배열을 만들어야 한다. -> 공간낭비.

 

이 두가지 문제를 동시에 해결해주는 것이 바로 해시 함수이다.

 

이제 앞선 예제를 그대로 사용하면서 다음과 같은 가정을 추가한다.

"직원의 번호는 입사 년도 네자리와 입사순서 네자리로 구성된다"

ex) 2012년에 세번째로 입사한 직원의 번호는 20120003.

 

typedef struct _empInfo
{
	int empNum; // 직원번호
	int age;
}EmpInfo;

int GetHashValue(int empNum) // 간단한 형태의 해시함수
{
	return empNum % 100; // % 100연산을 통해 얻은 해시(hash)값을 리턴 0 ~ 99까지의 값을 리턴
}


int main()
{
	EmpInfo empInfoArr[100]; // 직원들의 정보를 담기위해 선언된 배열
	EmpInfo emp1 = {20120003, 42};
	EmpInfo emp2 = {20130012, 33};
	EmpInfo emp3 = {20170049, 27};
	EmpInfo r1, r2, r3;

	// 해시함수를 통해 얻어온 해시값으로 인덱스에 저장.
	empInfoArr[GetHashValue(emp1.empNum)] = emp1;
	empInfoArr[GetHashValue(emp2.empNum)] = emp2;
	empInfoArr[GetHashValue(emp3.empNum)] = emp3;
	
	// 직원의 번호를 통해 인덱스에 접근해 탐색.
	r1 = empInfoArr[GetHashValue(20120003)];
	r2 = empInfoArr[GetHashValue(20130012)];
	r3 = empInfoArr[GetHashValue(20170049)];

	// 탐색 결과 확인
	cout << "사번 " << r1.empNum << " 나이 " << r1.age << endl;
	cout << "사번 " << r2.empNum << " 나이 " << r2.age << endl;
	cout << "사번 " << r3.empNum << " 나이 " << r3.age << endl;

	return 0;
}

이제 앞서말했던 직원의 번호의 길이에 관계 없이 해시함수를 통해서 직원의 번호를 받아 두 자리의 수를 해시값으로

얻어온다.

 

이 해시함수를 통해 우리는 배열의 인덱스에 접근해 값을 저장했고

직원의 번호를 해시함수를 통해 배열의 인덱스에 접근해 값을 얻어올 수 있다.

 

다만 위 예제의 문제점을 생각해보자.

배열의 길이는 100이다. 직원의 수가 100명을 넘어선다면?

이렇게 다른 데이터이지만 같은 해시값을 얻어오는 충돌 문제가 발생한다.

 

그렇기에 해시 테이블에서는 이 충돌을 어떻게 잘 해결하는지에 따라 좋은 해시 테이블이 될 가능성이 높다.

 

 

어느 정도 갖춰진 테이블과 해시의 구현 예

위 예제만으로는 모든것을 설명하기에는 어렵다. 그렇기에 좀 더 보완된 모습을 갖춰본다.

 

Person.h

#pragma once
class Person
{
public:
	Person();
	Person(int ssn, const char* name, const char* addr);
	~Person();
	int GetSSN() const;
	void ShowPerInfo() const;
private:
	enum { STR_LEN = 50 };
	int  m_ssn; // 주민등록번호
	char* m_name; // 이름
	char* m_addr; // 주소

};

Person.cpp

#include <iostream>
#include <cstring>
#include "Person.h"

Person::Person() : m_ssn(0), m_name(nullptr), m_addr(nullptr)
{

}

Person::Person(int ssn, const char* name, const char* addr) : m_ssn(ssn) 
{
	m_name = new char[STR_LEN];
	m_addr = new char[STR_LEN];
	strcpy_s(m_name, STR_LEN, name);
	strcpy_s(m_addr, STR_LEN, addr);
}

Person::~Person()
{
	delete[] m_name;
	delete[] m_addr;
}

int Person::GetSSN() const
{
	return m_ssn;
}

void Person::ShowPerInfo() const
{
	std::cout << "-------------------------------------------" << std::endl;
	std::cout << "이름 : " << m_name << "주민 : " << m_ssn << "주소 : " << m_addr << std::endl;
	std::cout << "-------------------------------------------" << std::endl;
}

 GetSSN. 주민등록번호를 얻어오는 것을 보아 이것을 '키'로 결장했다는것을 알 수 있다.

 

그리고 다음은 Slot.(보통 해시 테이블에서 데이터를 저장하는 공간. 이것을 버킷 혹은 슬롯이라 함)

 

Slot.h

#pragma once

class Person;

enum class SloatStatus
{
	EMPTY = 0, // 이 슬롯은 빈 상태
	DELETED,   // 이 슬롯은 삭제된 상태
	INUSE      // 이 슬롯은 사용중인 상태!(데이터가 저장돼있음)
};

struct Slot
{
	SloatStatus status;
	int			m_key;
	Person*		m_value;
};

 

이어서 테이블

 

Table.h

#pragma once

class Slot;
class Person;
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 }; 
	Slot*	  tbl;
	HashFunc* hf;
};

 

Table.cpp

#include "Table.h"
#include "Slot.h"
#include "Person.h"

Table::Table(HashFunc f) : hf(f)
{
	tbl = new Slot[MAX];
	for (int i = 0; i < MAX; ++i)
		tbl->status = SloatStatus::EMPTY; // 빈 상태로 초기화.
}
Table::~Table()
{
	delete[] tbl;
}

void Table::TBLInsert(int key, Person* value)
{
	int hashValue = hf(key); // 해시함수를 통해 해시값얻어오기.
	tbl[hashValue].m_key = key;
	tbl[hashValue].m_value = value;
	tbl[hashValue].status = SloatStatus::INUSE; // 사용중
}

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

	if (tbl[hashValue].status != SloatStatus::INUSE)
	{
		return nullptr;
	}
	else
	{
		tbl[hashValue].status = SloatStatus::DELETED;
		return tbl[hashValue].m_value;
	}
}

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

	if (tbl[hashValue].status != SloatStatus::INUSE) // 없다.
		return nullptr;
	else
		return tbl[hashValue].m_value;
}

 

main.cpp

#include "Table.h"
#include "Person.h"

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


int main()
{
	Table myTbl(MyHashFunc);
	Person* s1;
	Person* d1;
	Person* n1 = new Person(20120003,"Lee","Seoul");
	Person* n2 = new Person(20130012, "Kim", "Jeju");
	Person* n3 = new Person(20170049, "HAN", "Kanwon");

	// 삽입
	myTbl.TBLInsert(n1->GetSSN(), n1);
	myTbl.TBLInsert(n2->GetSSN(), n2);
	myTbl.TBLInsert(n3->GetSSN(), n3);

	// 탐색
	s1 = myTbl.TBLSearch(20120003);
	if (s1 != nullptr)
		s1->ShowPerInfo();
	s1 = myTbl.TBLSearch(20130012);
	if (s1 != nullptr)
		s1->ShowPerInfo();
	s1 = myTbl.TBLSearch(20170049);
	if (s1 != nullptr)
		s1->ShowPerInfo();

	/// 삭제
	d1 = myTbl.TBLDelete(20120003);
	if (d1 != nullptr)
		delete d1;

	d1 = myTbl.TBLDelete(20130012);
	if (d1 != nullptr)
		delete d1;
	
	d1 = myTbl.TBLDelete(20170049);
	if (d1 != nullptr)
		delete d1;

	return 0;
}

 

실행결과는

소멸자에서 멤버 delete 잊지 말자.

 

이렇게 좀 더 나은 예제의 완성.

다만 여전히 해시 함수는 key % 100이라는 단순하고 좋지않은 해시함수를 사용하고 있다.

즉 충돌에 대한 해결책은 구현한 상태가 아닌 것.

 

좋은 해시 함수의 조건

조건을 설명하기전에 좋은 해시 함수와 좋지 않은 해시 함수의 결과를 먼저 본다.

검은 영역은 데이터가 채워진 슬롯을 의미하고 반대로 흰 영역은 빈 슬롯을 의미한다.

위 그림을 보면 데이터가 테이블의 전체 영역에 고루 분포되어 있음을 알 수 있다.

이렇듯 고루 분포된다는 것은 그만큼 '충돌'이 발생할 확률이 낮다는 것을 의미한다.

 

충돌의 해결책이 마련되어 있다하더라도 충돌이 덜 발생해야 데이터의 저장, 삭제 및 탐색의 효율을 높일 수 있다.

때문에 좋은 해시 함수는 '충돌을 덜 일으키는 해시 함수' 라고 말할 수 있겠다.

 

그 다음 좋지 못한 해시 함수의 결과를 본다.

보면 검은 영역이 몰린 상황.

이는 해시 함수가 특정 영역에 데이터가 몰리도록 해시 값을 생성한 결과.

때문에 충돌이 발생할 확률이 그만큼 높은 상황이다.

 

좋은 해시 함수를 디자인하는 방법에 정답은 없다고 한다. 하지만 일반적으로 다음의 사항을 고려해

해시 함수를 정의하라고 조언한다.

 

"좋은 해시함수는 키의 일부분만을 참조하여 해시값을 만들지 않고, 키 전체를 참조하여 해시 값을 만들어 낸다"

 

아무래도 적은 수의 데이터를 조합하여(일부분) 해시 값을 생성하는 것보다는 많은 수의 데이터를 조합하여(전체)

해시 값을 생성했을 때, 보다 다양한 값의 생성을 기대할 수 있을 것이다. 

 

자릿수 선택 방법과 자릿수 폴딩 방법

좋은 해시 함수의 디자인 방법은 키의 특성에 따라 달라진다.

때문에 해시 함수의 디자인에 있어서 절대적인 방법은 존재하지 않는다.

 

다만, 위에서 설명한 키 전체를 참조하는 방법과 관련하여 다양한 방법이 소개 되고 있는데 그 중 하나는 다음과 같다.

 

"여덟 자리의 수로 이뤄진 키에서 다양한 해시 값 생성에 도움을 주는 네 자리의 수를 뽑아 해시값을 생성"

 

그리고 이와 유사한 방법으로 '비트 추출 방법'이라는 것이 있다.

이는 탐색 키의 비트 열에서 일부를 추출 및 조합하는 방법이다.

 

이어서 '자릿수 폴딩'방법이라는 것도 존재한다.

폴딩은 '접는다'란 뜻이며 다음 그림과 같이

6자리의 수를 세등분을 해 접게되면

27,34,19라는 수가 겹치게 된다.

이렇게 겹친 두 자릿수 숫자를 모두 더하면 결과는 80.

이를 해시값이라하면 이는 여섯 자리의 숫자를 모두 반영(Key값 전체를 반영)하여 얻은 결과라 할 수 있다.

 

이외에도 키를 제곱하여 그 중 일부를 추출하거나, 폴딩의 과정에서 덧셈 대신 XOR연산을 한다거나 하는등

다양한 방법들이 소개 되고 있는데, 해시 함수를 디자인할 때에는 이러한 방법들보다 키의 특성과 저장공간의 크기를

고려하는것이 우선이다.