해시 (Hash)

해시(Hash)란?

- hash table이라는 저장공간 내에 key들이 어떤 위치에 있을지를 정해서, hash table 안에 값들을 저장하는 구조를 말합니다.

해시는 key value 쌍으로 이루어져 있으며, 배열과 달리 key value가 int형이 아니어도 됩니다.

만약 key value가 int형이라면 선형배열(linear array)을 이용해도 되지만,

int가 아닌 string같은 다른 자료형일 경우 해시를 이용하면 좋습니다.

* 사상, 매핑(mapping)

- 위의 그림에서 "leo"는 2번째 칸에, "kiki"는 7번째 칸에, "eden"은 3번째 칸에 사상 또는 매핑(mapping) 되었다고 표현합니다.

* hash function

- hash table 안에 key들이 어떤 위치에 있을 지를 정해줍니다. 가급적이면 서로 다른 칸에 들어가도록 작동됩니다.

* hash bucket

- hash table 내 각각의 칸을 말합니다. hash function은 hash bucket의 총 개수에 맞게 구성되어야 합니다.

* hash collision

- 두 개 이상의 key가 같은 bucket에 사상되는 경우를 말합니다.

C++ 자체에는 key value 쌍을 이루는 데이터타입이 존재하지 않습니다.

그러므로 STL(Standard Template Library)를 이용해야 합니다.

C++ 컨테이너 중에서 key value 쌍을 나타내는 건 map과 unordered_map이 있습니다.

- map : binary serach tree로 구성되어 있어 key에 의한 접근 시간은 O(logN)입니다.

- unordered_map : hash table로 구성되어 있고 key에 의한 접근 시간은 O(1)입니다.

* unordered_map 사용방법

#include <unordered_map>

std::unordered_map<string, int> d;

cout << d["leo"] << endl;

=> 존재하지 않는 키에 대한 value는 value의 데이터 타입에 대한 기본값을 반환합니다. (string : "", int : 0)

d["leo"] = 3;

=> 특정 key에 대한 value 업데이트가 가능합니다.

* unordered_map의 순회

unordered_map<string, int> d;

for(auto& i : d){

cout << i.first << " - " << i.second << endl;

}

=> i.first로 key를 나타내고, i.second로 value를 나타냅니다.

(참고)

auto란?

- 컴파일러가 알맞은 반복자를 이용해서 원소를 표현하는데, 알맞은 데이터 타입을 추론하여 적용합니다.

왜 auto에 &를 붙였을까??

- &를 붙이지 않는다면 값을 복사하게 됩니다. 복사하는 과정에서 오버헤드가 발생하게 됩니다.

그래서 &를 붙여 값을 참조함으로써, 복사작업으로 인한 오버헤드를 줄일 수 있어 좀 더 최적화된 코드라 할 수 있습니다.