[C++/STL] 자료구조 - 해시

해시란?

임의의 길이의 데이터를 특정 길이의 데이터로 대응시키는 자료구조를 뜻한다.

예를들어 어떤 학생의 학번과 이름을 컴퓨터에게 기억하게 하고 싶은데 만약 학번이 너무 길다면 학번의 일부분만을 이용해 Key를 만들어 학생의 이름을 저장한다.

 

그리고 STL에서는 해시 자료구조들을 지원하고 있다.

---

1. unodered_set

unodered_set<자료형> : unodered_set은 선언부에서 입력된 자료형을 Key로 가지는 해시 자료구조이다. 특징으로는 중복을 허용하지 않는다.

 

#include <unordered_set>
#include <iostream>

using namespace std;

void unordered_set_func()
{
	unordered_set<int> unset;
	unset.insert(10);
	unset.insert(100);
	unset.insert(-10);

	unset.erase(-10);

	if (unset.find(-10) != unset.end())
		cout << "find -10" << endl;
	else
		cout << "not find -10" << endl;

	if (unset.find(10) != unset.end())
		cout << "find 10" << endl;
	else
		cout << "not find 10" << endl;

	for(auto a : unset)
		cout << a << endl;
}

2. unordered_multiset

unordered_multiset<자료형> : 위에서 설명한 unodered_set과 마찬가지로 선언부에서 입력된 자료형을 Key로 가지는 해시 자료구조이다. 하지만 unodered_set과 다르게 중복을 허용한다. 그래서 단순히 erase 함수에 Key를 입력하면 중복된 모든 Key가 제거된다. 하나의 Key만을 제거하고 싶다면, erase 함수에 Key의 iterator를 입력해야한다.

 

#include <unordered_set>
#include <iostream>

using namespace std;

void unordered_multiset_func()
{
	unordered_multiset<int> unmultiset;
	unmultiset.insert(10);
	unmultiset.insert(10);
	unmultiset.insert(10);
	unmultiset.insert(100);
	unmultiset.insert(-10);

	unmultiset.erase(unmultiset.find(10));

	if (unmultiset.find(10) != unmultiset.end())
		cout << "find 10" << endl;
	else
		cout << "not find 10" << endl;

	cout << "size : " << unmultiset.size() << endl;

	unmultiset.erase(10);

	if (unmultiset.find(10) != unmultiset.end())
		cout << "find 10" << endl;
	else
		cout << "not find 10" << endl;

	cout << "size : " << unmultiset.size() << endl;

	for (auto a : unmultiset)
		cout << a << endl;
}

3. unordered_map

unordered_map<Key 자료형, Value 자료형> : unordered_map은 Key에 대한 자료형 그리고 Value에 대한 자료형 두개를 갖는다. 그러므로 Key값을 통해 Value를 찾아낼 수 있다.

 

#include <unordered_map>
#include <string>
#include <iostream>

using namespace std;

void unordered_map_func()
{
	unordered_map<string, int> unmap;
	unmap.insert({ "A",1 });
	unmap.insert({ "B",10 });
	unmap.insert({ "C",100 });
	unmap.insert({ "D",1000 });
	unmap.insert({ "E",-1 });

	cout << unmap["A"] << endl;
	
	unmap.insert({ "A",99 });

	if(unmap.find("A") != unmap.end())
		cout << unmap["A"] << endl;
	else
		cout << "not find" << endl;

	unmap.erase("A");

	if (unmap.find("A") != unmap.end())
		cout << unmap["A"] << endl;
	else
		cout << "not find" << endl;

	for (auto a : unmap)
		cout << a.first << " : " << a.second << endl;
}