[자료구조] HashMap과 TreeMap

HashMap

HashMap은 해시테이블 기반의 Map으로 데이터를 Key-Value 쌍으로 저장한다.

내부적으로 key를 해시함수를 통해 인덱스로 변환하여 bucket에 저장한다.

따라서 HashMap은 Key-Value쌍끼리의 순서를 보장하지 않고 랜덤 하게 저장된다.

 

c++에서는 다음과 같이 HashMap을 사용할 수 있다.

#include <iostream>
#include <unordered_map>

using namespace std;

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

 

 HashMap에서의 삽입, 삭제, 탐색을 할 때 시간복잡도는 모두 O(1)에 수행된다.

순서를 보장하지는 않지만 TreeMap에 비해서 속도가 빠르다는 장점이 있다.

 

삽입

m.insert({k,v});
m[k] = v;

 

삭제

m.erase(k);

 

탐색

m.find(K);
m[K];

만약 탐색을 할 때 Key-Value쌍이 저장돼있지 않은 경우는 m.end()를 반환한다.

탐색을 성공했을 경우에는 해당 값에 대한 iterator를 반환한다.

iterator를 통한 값의 접근은 다음과 같이 할 수 있다.

//찾은 key 출력
cout << (m.find(k))->first;
cout << (*m.find(k)).first;

//찾은 value 출력
cout << (m.find(k))->second;
cout << (*m.find(k)).second;

 

TreeMap

TreeMap은 red-black 트리 같은 균형 이진 탐색트리로 구현되어 있는 Map으로 Key-Value쌍을 저장한다.

대부분 HashMap과 비슷한 부분이 많지만 다른 점은 순서가 있는 자료구조라는 점이다.

key값을 기준으로 오름차순으로 순서가 정렬되어 있다는 특징이 있다.

 

c++에서는 다음과 같이 TreeMap을 사용할 수 있다.

#include <iostream>
#include <map>

using namespace std;

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

 

 TreeMap에서의 삽입, 삭제, 탐색을 할 때 시간복잡도는 트리의 높이에 비례하여 모두 O(logN)에 수행된다.

속도가 HashMap보다는 느리지만 순서가 유지된다는 장점이 있다.

 

삽입

m.insert({k,v});
m[k] = v;

 

삭제

m.erase(k);

 

탐색

m.find(K);
m[K];

만약 탐색을 할 때 Key-Value쌍이 저장돼있지 않은 경우는 m.end()를 반환한다.

탐색을 성공했을 경우에는 해당 값에 대한 iterator를 반환한다.

 

오름차순 순회

TreeMap은 iterator를 통해 key를 기준 오름차순으로 순회할 수 있다.

#include <iostream>
#include <map>
using namespace std;
int main(){
	map<int, int> m;
	m.insert({1, 4});           
	m.insert({5, 2});           
	m.insert({3, 6});

	map<int, int>::iterator it;

	// (1,4) (3,6) (5,2) 순서로 출력됨
	for(it = m.begin(); it != m.end(); it++) {
	    cout << it->first << ' ' << it->second << '\n';
	}
}

iterator를 1씩 증가시키면서 m.begin()에서 시작하여 m.end()가 나올 때까지 모든 값을 출력가능하다.

이때 주의할 점은 내부적으로 Tree 구조로 저장된 값들을 순회하면서 찾는 것이기 때문에 iterator의 값을 1씩만 증감이 가능하다.