맵, 해시 맵

C++에서는 <map> 자료구조를 제공한다. 

map 자료구조는 key와 value 값을 하나의 데이터 묶음으로 저장하여

key 값을 통해 value값을 찾을 수 있도록 하는 자료구조이다.

이와 유사하게 C#에서는 <dictionary> 자료구조를 제공하는데, 

더 엄밀하게 말하면 dictionary  자료구조는 map이 아닌 hash map가 동일한 자료구조이다.

 

hash map 자료구조는 C++에서 unordered_map으로 제공되고 있다.

 

그럼 map과 hash map의 차이점은 무엇일까?

- map은 데이터가 red black tree로 구성되어 있다.

따라서 데이터의 삽입과 삭제에 걸리는 시간 복잡도는 O(logN)이다.

 

- hash map은 hash table로 구성된 map 자료구조로,

'메모리를 내주고 속도를 취하는' 방법으로 구현되어 있다.

 

 

예를 들어 아파트의 우편함을 생각해보자. 

아파트는 각 호수별로 우편함이 따로 존재한다. 

따라서 우편물을 찾을 때 자신의 호수에 해당하는 우편함만 탐색하면 된다.

 

이와 같이 서로 다른 key 값을 갖는 데이터의 개수만큼 메모리를 확보하며,

key값이 테이블의 인덱스가 되는 구조를'테이블'이라 한다.

테이블을 활용하면 키 값에 해당하는 데이터에 단번에 접근하기 때문에 시간 복잡도는 O(1)을 갖는다. 

 

그런데.. 데이터가 수 억..수십 억.. 처럼 큰 key값을 갖는 경우, 메모리가 감당할 수 없어지면 어떡하지??

그래서 테이블 구조에 '해시'를 적용하게 된다.

 

해시가 뭐냐면.. 보안 과목이나 보안 이슈에서 쉽게 확인할 수 있는 단어인데,

 

아이디와 패스워드를 저장하는 테이블이 있다고 해보자.

그 테이블에 패스워드 항목을 사용자가 입력한 대로 작성해 놓으면 

데이터가 해킹 당했을 때, 패스워드가 털리는 위험이 있다...!

 

따라서 보안 엔지니어는 패스워드를 파라미터로 갖는 함수를 설계하고 

그 함수는 무작위의 값을 출력하도록 한다. 이러한 함수를 해시 함수라 하고,

해시 함수의 알고리즘은 다양하다! 

 

해시 함수의 특징은 역함수가 존재하지 않는다는 것이고, 따라서 해시 함수 결과값을 알아도

해시 함수의 파라미터로 전달해 주는 원래의 값을 도출할 수 없다는 특징이 있다. 

(요즘 사이트에서는 해시 함수를 적용하기 때문에 비밀번호 찾기를 들어갔을 때, 

등록된 비밀번호를 알려주는 것이 아니라 새 비밀번호를 설정하도록 해주는 경우가 있다.

이게 해시 함수의 특징 때문이다.)

 

 

만약 해시 함수가 아래의 알고리즘을 갖는다고 가정해보자.

(역함수가 가능한 함수이지만 간단하게 예를 들기 위해 사용.)

int hash(int pw)
{
    return pw%1000;
}

이를 이용하면 123456789와 같은 큰 key 값을 갖는 데이터라도 hash(123456789)를 통해 789의 key값을 도출하게 되며,

메모리의 활용도를 높일 수 있다는 장점이 있다.

 

 

그러나 key 값이 위의 해시 함수를 통해 해시 값을 얻는 경우,

123456789의 key값은 789라는 key값과 동일한 해시 값을 얻게 된다. ->동일한 메모리에 접근하는 충돌 발생

 

이러한 충돌 문제를 해결하기 위해서는 충돌이 발생한 자리를 대신해

다른 빈자리를 찾아나서야 한다. 

 

빈자리를 찾아나서는 방법으로는

1) 선형 조사법 : 충돌이 발생한 메모리 위치에서 +1(빈자리를 찾을 때까지 +1) 위치에 저장.

2) 이차 조사법 : 충돌이 발생한 메모리 위치에서 +n^2(n=1,2,3....빈자리를 찾을 때까지 수 상승) 위치에 저장.

 

데이터의 수가 많아질 경우 2가지의 조사법으로는 한계가 있다!

이럴 때 '체이닝'을 활용한다! => 2차원 배열을 활용하는 방법

배열 내에 배열을 생성하여, 동일한 index에 접근할 경우 해당 index의 배열에 데이터를 추가해주는 방법.

struct User
{
    int id =0;
    string name;
}

const int id = 123456789;
int key = hash(id);

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

users[key].pusy_back(User{id, "j"});

해시 맵은 충돌이 발생하지 않는 한, O(1)의 탐색 시간을 갖는다.

(충돌이 발생한다면 해당 index 값의 배열을 탐색하는 시간이 추가되겠지...)

해시 함수를 이용하여 해시 값을 도출하는 경우, 그 결과값이 거의 충돌이 발생하지 않는다. (=동일한 값을 갖지 않는다.)

 

따라서 해시 맵은굉장히 빠른 탐색 시간을 갖는다고 볼 수 있다.