Hash Table

Hash Table

• 해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조중 하나로 빠르게 데이터를 검색할 수 있는 자료구조 이다.

• Map과 비슷하지만 Map은 레드 블랙트리로 이루어져 있는 반면 HashMap은 배열과 비슷한 버킷으로 이루어져 있다.

• 메모리를 내주고 속도를 취하는 자료구조이며 평균 탐색 시간복잡도가 O(1)로 매우 빠르다.

• 해시 함수를 통하여 고유한 인덱스를 각각의 데이터에게 할당한다.

• 대표적인 해시함수는 다음과 같다.

  • Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.( 주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.

  • Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.

  • Multiplication Method: 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k)=(kAmod1) × m

  • Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

출처: https://mangkyu.tistory.com/102 [MangKyu's Diary]

• 하지만 해시함수를 통해 만들어낸 key라 할지라도 충돌할 위험이 없지 않기 때문에 충돌에 대비한 방법을 마련해야한다.
• 대표적으로 분리 연결법(Separeate Chaining)과 개방 주소법(Open Addressing)이 있다.

분리 연결법

• 분리 연결법의 경우 key의 충돌이 일어날 경우 해당 key의 버킷을 연결리스트처럼 데이터를 연결하여 추가하는 방법이다.

개방 주소법

• 개방 주소법의 경우 key의 충돌이 일어날 경우 빈 버킷을 찾아서 그 곳에 저장하는 방법이다.
  • Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
  • Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.
  • Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다

출처: https://mangkyu.tistory.com/102 [MangKyu's Diary]

// 오늘의 주제 : Hash Table
// Q) map vs hash_map (C++ 표준 unordered_map)

// map : Red - Black Tree
// - 추가/탐색/삭제 O(logN)

// hash_map (unordered_map)
// - 추가/탐색/삭제 O(1)

// 살을 내주고 뼈를 취한다!
// 메모리를 내주고 속도를 취한다!


// 0(1)
void TestTable()
{
	struct User
	{
		int userId = 0;	// 1 ~ 999
		string username;
	};

	vector<User> users;
	users.resize(1000);

	// 777번 유저 정보 세팅
	users[777] = User{ 777,"Lee" };

	// 777번의 유저는?
	string name = users[777].username;
	cout << name << endl;

	// 테이블
	// 키를 알면, 데이터를 단번에 찾을 수 있다.

	// 문제의 상황
	// int32 max (대략 3억)
	// 메모리를 내주고 속도를 취한다고 하긴 하지만
	// 메모리를 너무 많이 내주면 문제가 생기기 마련이다
	// 따라서 "해쉬" 와 "테이블"을 동시에 사용하여 문제를 해결


}

// 보안
// id: Lee + pw: qwer1234

// DB [Lee][qwer1234]
// -> 비밀번호가 해시값으로 변경 -> 해시값을 사용하면 홈페이지 제공측에서도 
// 해쉬 값을 비밀번호로 복구를 할 수 없다.

void TestHash()
{
	struct User
	{
		int userId = 0;	// 1 ~ int32_max
		string username;
	};

	vector<User> users;
	users.resize(1000);

	const int userId = 123456789;
	int key = (userId % 1000); // hash < 고유번호

	// 123456789번 유저 정보 세팅
	users[key] = User{ userId,"Lee" };

	// 123456789번의 유저는?
	User& user = users[key];
	if (user.userId == userId)
	{
		string name = users[key].username;
		cout << name << endl;
	}

	// 충돌 문제
	// 123456789 와 789 유저는 같은 key를 가지게 된다.
	// 해결법: 충돌이 발생한 자리를 대신해서 다른 빈자리를 찾는다.
	// - 선형 조사법 (linear probing)
	// hash(key) +1 -> hash(key) +2 : 차있을 경우 한칸씩 뒤로 이동해 빈칸을 찾아본다
	// - 이차 조사법 (quadratic probing)
	// hash(key) +1² -> hash(key) +2² 선형조사의 문제를 해결하기 위해 key를 좀더 분산시켜서 빈칸을 찾는다.

	// 체이닝: 누가 있다? -> 연결리스트 혹은 동적배열을 사용하여 그 자리에 새로운 공간을 연결하여 넣어버림
}

void TestHashTableChaining()
{
	struct User
	{
		int userId = 0;	// 1 ~ int32_max
		string username;
	};

	vector<vector<User>> users;
	users.resize(1000);
	
	int userId = 123456789;
	int key = (userId % 1000); // hash < 고유번호

	// 123456789번 유저 정보 세팅
	users[key].push_back(User{ userId,"Lee" });
	users[789].push_back(User{ 789,"Faker" });

	vector<User>& bucket = users[key];
	for (User& user : bucket)
	{
		if (user.userId == userId)
		{
			string name = user.username;
			cout << name << endl;
		}
	}
}