해싱(map,set)

해싱

해싱이란 탐색법의 일종으로 비교에 의해서 검색하는 방법이 아니라 함수식을 이용하여 바로 찾아 가는 검색 방법을 말한다.

자세한건 구글 검색 링크

이러한 해싱을 간편하게 할 수 있도록 C++에서는 map,set 자료구조를 지원한다.

Set

set 자료구조의 주요 용도는 key값의 존재 유무를 확인할때 사용한다.

#include <iostream>
#include <set>

using namespace std;

int main(void){
    set<int> s;
    s.insert(1);
    s.insert(9);
    s.insert(3);
    s.insert(4);
    s.insert(7);
    s.insert(8);
    s.insert(9);
    s.insert(1);
    set<int>::iterator it;
    for(it = s.begin(); it != s.end() ; it++){
        cout<<*it<<endl;
    }
    it = s.find(3);
    cout<<"I FOUND 3 ";
    if(it != s.end()) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;

    it = s.find(2);
    cout<<"I FOUND 2 ";
    if(it != s.end()) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

inseart() : 해쉬 테이블에 값 추가

find() : 특정 값 검색

결과

-

Map

map은 set과 유사하지만 더 나아가서 <key,value> 형식으로 저장되어 해당되는 key값에 대한 value를 찾을 수 있다.

물론 map을 이용해서 set을 대체할 수 있지만 속도면에서 map보다는 set이 빠르기 때문에 단순히 존재 유무만을 판단할때는 set을 사용하는것이 더 좋다.

#include <iostream>
#include <map>
#include <utility>
#include <string>
using namespace std;

int main(void){
    map<int,string> m;
    m.insert(make_pair(1,"KIM"));
    m.insert(make_pair(3,"YI"));
    m.insert(make_pair(5,"PARK"));
    m.insert(make_pair(6,"JI"));
    map<int,string>::iterator it;
    for(it = m.begin(); it != m.end() ; it++){
        cout<<it->first<<" "<<it->second<<endl;
    }
    cout<<"I FOUND 3 ";
    it = m.find(3);
    if(it != m.end()) cout<<m[3]<<endl;
    else cout<<"NO";

    cout<<"I FOUND 2 ";
    it = m.find(2);
    if(it != m.end()) cout<<m[2]<<endl;
    else cout<<"NO";
}

inseart() : 해쉬 테이블에 값 추가

find() : 특정 값 검색

map같은 경우 set과 마찬가지로 iterator로 접근해도 되지만 array[key]이런식으로 접근도 가능하다.

결과

간단한 예시 문제

#include <iostream>
#include <cstdio>
#include <fstream>
#include <set>
#include <string>
using namespace std;
void sol(string,int,string);
char keymap[10][3] = {{0,0,0},{0,0,0},{'A','B','C'},{'D','E','F'},{'G','H','I'},{'J','K','L'},{'M','N','O'},{'P','R','S'},{'T','U','V'},{'W','X','Y'}};
set<string> dict;
int size = 0;
set<string>::iterator it;
int main(void)
{
    ifstream readFile;
    readFile.open("dict.txt");
    if(readFile.is_open()){
        while(!readFile.eof()){
            string str;
            getline(readFile,str);
            dict.insert(str);
        }
    }
    readFile.close();
    string serial;
    cin>>serial;
    string key;
    sol(serial,0,key);
    if(size == 0) cout<<"NONE"<<endl;
}

void sol(string serial,int index,string key){
    key.capacity();
    if(key.length() == serial.length()){
        if((it = dict.find(key)) != dict.end()) {cout<<key<<endl;size++;}
        return;
    }
    int mapindex = serial.at(index) - '0';
    for(int i = 0 ; i < 3 ; i++){
        key.push_back(keymap[mapindex][i]);
        sol(serial,index+1,key);
        key.pop_back();
    }
}

참고 사이트 : https://modoocode.com/224

 

이 사이트에가면 훨씬 더 자세하고 쉽게 설명되어 있다.