[기초] 해시 구현하기 (unordered) / C++

해시 값 추가, 삭제, 변경하기

C++에서 해시를 구현하는 방법은 여러가지가 있지만, 가장 일반적인 방법은 STL의 unordered_map을 사용하는 것입니다.

 

1. 헤더파일 

#include <unordered_map>

unordered_map은 해시 테이블로 구현되어 있어서, 키와 값을 저장하고 검색하는 데 빠른 속도를 가지고 있습니다.

2. 해시 선언

unordered_map<string, int> mymap;

<key type, value type>

3. 값 추가

• hash[key] = values;

 

4. 값 삭제

• hash.erase(key);

 

5. 값 변경

• hash[key] = diff_values;

 

6. 값 찾기

• hash[key];
• hash.find(key) : 해당 키값이 해시맵안에 있으면 해당 값 반환, 없으면 해시맵의 가장 마지막에 있는 키반환
  • find 로 찾은 키에 대해 value 반환하기: 
    • auto it = hash.find(key)
    • cout << it -> second << endl;

 

아래는 unordered_map을 사용하여 해시를 구현하는 간단한 예제입니다.

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

using namespace std;

int main() {
    // unordered_map 생성
    unordered_map<string, int> mymap;

    // 값 추가
    mymap["apple"] = 1;
    mymap["banana"] = 2;
    mymap["cherry"] = 3;

    // 값 검색
    cout << "apple: " << mymap["apple"] << endl;
    cout << "banana: " << mymap["banana"] << endl;
    cout << "cherry: " << mymap["cherry"] << endl;

    // 값 수정
    mymap["banana"] = 4;
    cout << "banana: " << mymap["banana"] << endl;

    // 값 삭제
    mymap.erase("cherry");

    // 모든 값 출력
    for (auto it = mymap.begin(); it != mymap.end(); it++) {
        cout << it->first << ": " << it->second << endl;
    }

    return 0;
}

 

키값이 있는지 확인하기 (find 함수)

 

find() 함수는 해당 키값이 해시 테이블에 존재하면 해당 iterator를 반환하고, 존재하지 않으면 해시 테이블의 끝(end())을 반환합니다.

 

예시 코드

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    unordered_map<int, string> hash_map = {{1, "one"}, {2, "two"}, {3, "three"}};

    auto it = hash_map.find(2);
    if (it != hash_map.end()) {
        cout << "Key 2 exists, and its value is " << it->second << endl;
    } else {
        cout << "Key 2 does not exist" << endl;
    }
}

 

 * auto it 이란?

auto it는 자동 타입 추론을 이용하여 변수의 타입을 자동으로 결정하는 C++11 이후의 문법입니다

 

* it->second

it가 가리키는 해시 맵의 value에 접근하는 것입니다. 

 

it는 pair 타입의 객체를 가리키고 있으며, pair 객체의 첫 번째 요소는 key, 두 번째 요소는 value를 가리키게 됩니다. 따라서 it->second는 it가 가리키는 key에 해당하는 값, 즉 value를 반환합니다.