[코드트리] Hash Map

SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다.

 

* 참고 : python과 c++, java 등 언어별로 설명이 다른 부분이 존재합니다! 필자는 c++을 사용하고 있습니다.

 

xxilliant 제작

unordered_map STL

C++에서는 unordered_map이라는 STL을 이용할 수 있습니다.

unordered_map은 HashMap 자료구조로 되어있으며, HashMap의 경우 해싱을 기반으로 데이터들을 관리해주는 자료구조 입니다. HashMap은 (key, value) 쌍 형태로 들어가 있어, key와 그에 따른 value 값을 동시에 저장하는 형태입니다.

따라서 HashMap의 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도가 전부 O(1)입니다.

 

unordered_map은 map보다 속도가 빠르지만, 값 자체에만 관심이 있지 그 순서에는 전혀 관심이 없는 자료구조입니다.

 

#include <unordered_map> 헤더와, unordered_map<K, V> name; 형태의 선언이 필요합니다.

(K는 key, V는 value 입니다.)

unordered_map은 원래 std::unordered_map이지만

using namespace std; 를 미리 선언한 상태라고 가정하고 코드를 작성하였습니다.

 

정수를 관리할 unordered_map은 다음과 같이 선언해 볼 수 있습니다.

 

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    unordered_map<int, int> m;
    return 0;
}

 

unordered_map을 이용할 때 자주 사용되는 것은 다음 3가지 입니다. unordered_map<int, int> m;로 선언되어 사용될 때를 예로 설명해보겠습니다.

1. m.insert({K, V}) 혹은 m[K] = V

hashmap에 쌍(K, V)를 추가합니다. 마치 배열에 값을 넣듯이 m[K] = V 방식으로도 가능하며, 더 많이 쓰이는 방식입니다.

1. m.erase(K)

현재 hashmap에 들어있는 데이터 중 key가 K인 쌍을 찾아 제거합니다.

1. m.find(K) 혹은 m[K]

현재 hashmap에 key가 K인 쌍이 있는지를 확인합니다. m.find(K) 이용시 만약 있다면 해당 iterator를 반환하며, 없다면 m.end()값을 반환합니다. 따라서 값이 있다면 m.find(K) != m.end(), 없다면 m.find(K) == m.end()를 만족할 것입니다. 이때, 원소는 pair 타입이기 때문에 다음과 같이 값에 접근할 수 있습니다.

cout << (m.find(K))->first << endl;     // key가 K인 원소의 key 조회
cout << (m.find(K))->second << endl;    // key가 K인 원소의 value 조회
cout << (*m.find(K)).first << endl;     // key가 K인 원소의 key 조회
cout << (*m.find(K)).second << endl;    // key가 K인 원소의 value 조회

 

단, 값만 조회하고 싶은 경우라면 배열에서 인덱스를 이용해 값에 접근하듯이 m[K] 형태로도 이용 가능합니다.

cout << m[K] << endl;                   // key가 K인 원소의 value 조회

 

 

Side Note

만약 key가 문자열이라면, 마치 배열 index가 문자열이 된 것 처럼 사용할 수 있게 됩니다!

unordered_map<string, int> 타입으로 선언하면 사용이 가능합니다.

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    unordered_map<string, int> m;
    m["banana"] = 6;
    m["helloworld"] = 2;
    m["apple"] = 5;

    cout << m["banana"] << endl; // key가 banana인 쌍의 value 출력 (6)
}

 

출처 코드트리