강의 보고 공부한 것을 정리하는 목적으로 작성된 글이므로 틀린 점이 있을 수 있음에 양해 부탁드립니다. (피드백 환영입니다)

이번 시간에는 hash_map!을 배워볼 것이다!

hash_map

map과 사용법은 비슷하지만 개념적으로 다른 부분이 있기 때문에 그 부분을 알아야 한다.

예전에는 hash_map을 표준으로 사용하였지만 지금은 unordered-map을 사용한다.

unordered_map<int, int> um;

도움되는 잡소리

그럼 이 hash_map은 무엇을 하는 컨테이너일까?
이것을 비교할 때 살을 내주고 뼈를 취한다!라는 말과 어울린다.

여기서 hash_map은 메모리를 팔아서 (CPU)성능을 얻겠다! 이런 말이다.

이것을 아파트 우편함에 비유를 해본다면,
아파트 호수별로 우편함이 있을 것이다.
만약 내가 203호에 산다면 203호 우편함에 있는것만 들고 가면된다.
이걸 시간복잡도로 생각해보면 상수일 것이다. O(1)

hash_map은 이러한 개념이다.

이것을 게임에도 비유를 해본다면,
유저가 1~999까지 있을 때
관리하는 통은 1에서 999까지 만들어보자
그러면 1번 유저는 1칸에 있을 것이고 999유저는 999칸에 있을 것이다.
우리가 메모리가 무한이라면 이렇게 하는것은 효율적인 방법이 일 수 있다.

하지만 당연히 메모리가 무한이 아니기 때문에 막 사용할 수 없을 것이다.

하지만 변하지 않은 사실은 키를 알면 빠르게 찾을 수 있다.
그래서 중요한것은 키를 어떻게 설정하는 것인데..
키랑 바구니를 1대1로 맵핑하는 것이 이상적이지만 너무 데이터가 많아지면 불가능해 질 것이다.

그래서 hash_map에서는 hash 기법은 암호학쪽에서 많이 사용된다.
옛날에 2000년대 보안이 좋지 않았을 때에는 id랑 password를 그냥 데이터베이스에다가 다 때려박아넣었었는데 그렇게 된다면 데이터베이스를 털리게 되면 다 털리게 되기 때문에 문제가 있었다.

하지만 나중에 password를 그냥 저장하는 것이 아닌 hash값을 취해서 저장하게 만들어진다.

hash알고리즘은 여러가지가 있는데
만약 내가 12345라는 password에 hash알고리즘을 적용시키면 1ofkqpofkopkfljqi2e1i02이런식으로 변한다. (거의 겹칠 확율이 없음)

그러면 저 이상한 값을 데이터베이스에 넣어서 탈취를 당하면 똑같은거 아닌가?
할 수 있지만 절대로 원래 password를 알 수 없다.
이 구조가 단방향으로 되어 있기때문에 저 이상한 값만 안다면 password를 알 수 없지만 원래 password를 알고 hash알고리즘을 알면 똑같은 값이 나온다.

그러면 이제 hash_map이라는 것을 보면,
어떤 데이터가 있다고 가정하였을 때, 어떤 데이터를 해쉬를 취해서 키값을 생성해내는 것이다. (1대1로 만들면 좋지만 힘들다면 우리만의 공식을 만들어 내는 것이다)

예를 들어본다면,
유저아이디칸을 10000개를 사용할껀데 유저아이디를 대상으로 % 10000 = 키라고 생각을 해보자 그러면 104033244000002라는 아이디가 있으면 위 공식을 사용하며 2가 나오기에 2칸을 사용해준다. 이런식인 것이다.

그래서 결국 제일 중요한 것은 메모리를 팔아서 성능을 얻는다..이것이다.

우리가 unorderd_map을 사용하면 hash기법도 정해줄 수 있다.
즉, hash기법을 사용해서 관리를 하게 된다.

그럼 이것의 시간복잡도는 얼마일까?

시간 복잡도

메모리는 힘들어하겠지만 O(1)일 것이다.

그래서 hash_map은 하나의 통에 hash기법을 사용하여 최대한 안겹치도록 넣어주는 것이 핵심인 컨테이너이다.. 이게 사실 끝이다.

그래서 map이랑 hash_map을 알아보았는데.. 생각보다 비슷하다.
그리고 사용할 때도 뭐 또이또이 일 것 같다.

어차피 map도 너무 양이 많아진다면 레드블랙트리도 시간을 조금 더 걸리게 될 수도 있을 것 같다.

그럼 이제 hash_map의

추가
찾기
삭제
순회

를 알아보자. (map과 비슷함)

추가

unordered_map<int, int> um;

//um.insert(pair<int, int>());
um.insert(make_pair(10, 100)); // key 10, value 100
um[20] = 200;

맵이랑 동일하다..

찾기

auto findlt = um.find(10);
if(findIt != um.end())
{
	cout << "찾음" << endl;
}
else
{
	cout << "없음" << endl;
}

삭제

um.erase(10);
//um.erase(findIt);

순회

for(auto It = um.begin(); it != um.end(); it++)
{
	int Key = It->first;
    int value = It->second;
}

음..그냥 아예 똑같다.

그래서 unordered_map을 사용하다가 map으로 바꿔도 아무런 문제가 없을 것이다.

마무리

그래서 여기서 우리가 중요하게 생각해야 할 것은 무슨 컨테이너를 선택할지가 중요한 것이다. 나머지 구현은 비슷해서 조금씩만 바꾸면 된다.

그리고 hash_map에서는 hash기법랑 통(burket)이라는 용어를 알고있으면 된다.

또 면접에서 hash_map에 관련된 것을 물어본다면 위에서 말했던 것을 설명하면 된다.

하나 더 알아야 하는 것은 map과 hash_map의 차이는

map은 레드블랙트리 알고리즘을 사용해서 컨테이너가 만들어주고
hash_map은 hash기법을 사용하여서 통에 넣어주는 컨테이너라고 볼 수 있다.

우리가 여기까지 했으면 대부분의 컨테이너의 핵심내용을 다 알았기 때문에 우리가 c++을 하다가 c#을 가더라도 vector는 list고 unordered_map은 dictionary이기 때문에 이제 실습을 하면 된다.