std::tuple이란?

  • 기존에 다른 데이터 타입의 값 2개를 저장하기 위해 pair를 사용했지만, first와 second 두 개의 요소만 관리할 수 있었다.
  • C++11부터 STL에서 tuple을 제공하여 다수의 요소를 관리할 수 있는 tuple을 제공한다.
  • <tuple>에 정의되어 있다.

 

기본 사용법

#include <tuple>
#include <iostream>

int main() {
    // 다양한 타입의 요소들을 포함하는 튜플 생성
    std::tuple<int, double, std::string> myTuple(1, 3.14, "Hello");

    // 튜플의 요소에 접근
    std::cout << "Integer: " << std::get<0>(myTuple) << std::endl;
    std::cout << "Double: " << std::get<1>(myTuple) << std::endl;
    std::cout << "String: " << std::get<2>(myTuple) << std::endl;

    return 0;
}

 

별 특이한 점은 없지만, std::get을 사용할 수 있다.

 

std::get

std::get 템플릿 함수를 이용해서 튜플의 요소에 접근할 수 있다(인덱스를 통해 접근)

std::get<0>(myTuple);  // 첫 번째 요소
std::get<1>(myTuple);  // 두 번째 요소
std::get<2>(myTuple);  // 세 번째 요소

 

std::make_tuple

주어진 값들로 초기화된 튜플을 리턴

auto t3 = std::make_tuple(2, 2.71, "World");

 

std::tie

기존 변수들을 튜플의 요소에 바인딩해준다

int a;
double b;
std::string c;

std::tie(a, b, c) = t3;

 

std::tuple_cat()

두 개의 tuple을 합친다

auto t1{std::make_tuple(10, "Name", 'a')};
auto t2{std::make_tuple("Hello", 20, 'b')};

auto t3{std::tuple_cat(t1, t2)};   
EXPECT_TRUE(
    std::get<0>(t3) == 10 && 
    std::get<1>(t3) == "Name" && 
    std::get<2>(t3) == 'a' &&
    std::get<3>(t3) == "Hello" && 
    std::get<4>(t3) == 20 && 
    std::get<5>(t3) == 'b'
);

 

 

'Data Structure > C++ STL' 카테고리의 다른 글

[C++ STL] std::string  (0) 2024.06.30
[C++ STL] std::pair  (0) 2024.06.30
[C++ STL] 3.4 C++ 해시 테이블  (0) 2024.06.23
[C++ STL] 2.6 그래프(graph)  (0) 2024.06.21
[C++ STL] 2.5 힙(Heap)  (0) 2024.06.21

std::string이란?

  • STL에서 제공하는 문자열 처리 클래스
  • 동적 길이 문자열을 다루기 쉽게 만들어준다.
  • <string>에 정의되어 있다.

 

내부 구현?

  • 문자열의 크기에 따라 동적으로 할당하여 문자열 데이터를 저장한다
  • 짧은 문자열은 내부 버퍼에 따로 저장하여 동적 할당을 하지 않는다
  • 복사 및 연산 과정에서 기본적으로 깊은 복사를 사용한다. 포인터나 참조가 기반으로 관리되지 않는다

초기화

기본 생성자 : 빈 문자열 생성

std::string s;

 

C-스타일 문자열로부터 생성

std::string s1("Hello");
std::string s2 = "Hello";
std::string s3 = "";

 

반복자로부터 생성

std::string s(iter1, iter2);

 

특정 문자 n개로 초기화

std::string s(5, 's');// "sssss"

 

부분 문자열

std::string s1 = "abc";

std::string s2(s1, 1, 2); // s1[1]부터 2개 문자를 복사하여 생성합니다.
EXPECT_TRUE(s2 == "bc");

// std::string s3(s1, 100, 2); // (X) 예외 발생. s1[100]부터 2개 복사. out_of_range

std::string s4(s1, 0, std::string::npos); // s1[0] 부터 끝까지 복사하여 생성합니다.
EXPECT_TRUE(s4 == s1);

std::string s5(s1.begin(), s1.end()); // s1.begin()부터 s1.end() 직전 까지 복사하여 생성합니다. 즉, s1[0]부터 끝까지 복사하여 생성합니다.
EXPECT_TRUE(s5 == s1);

const char* ptr = "abc";
std::string s6("abc", 2); // ptr에서 2개 복사하여 생성합니다.
EXPECT_TRUE(s6 == "ab");

 

참조) https://tango1202.github.io/legacy-cpp-stl/legacy-cpp-stl-string/

 

#17. [레거시 C++ STL] 문자열

string과 wstring은 public Non-Virtual 소멸자이므로 상속하여 재구현 하지 마라. 수정될 필요가 없는 문자열 데이터는 const char* 나 const wchar_t*로 관리하라.(배열이나 string, wstring을 쓰면 복제된다.) string

tango1202.github.io

 

문자열 수정

append: 문자열을 끝에 추가

 
s.append(" World");

 

insert : 문자열을 지정된 위치에 삽입

s.insert(5, " C++");

 

erase : 지정된 위치의 문자열 제거

s.erase(5, 3);  // 5번 인덱스부터 3글자 제거

 

replace : 지정된 범위의 문자들을 다른 문자열로 대체

s.replace(0, 5, "Hi");  // 처음 5글자를 "Hi"로 대체

 

문자열 연산자

  • "="를 이용하여 문자열 할당
  • "+", "+="를 이용하여 문자열 합성
  • "=", "!=", "<", ">", "<=", ">="를 이용하여 대소 비교
std::string s = "abc";

EXPECT_TRUE(s == "abc");
EXPECT_TRUE(s != "def");
EXPECT_TRUE(s < "ccc");
EXPECT_TRUE(s.compare("ccc") < 0); // s < "ccc"
EXPECT_TRUE(s.compare("abc") == 0); // s == "abc"
EXPECT_TRUE(s.compare("aaa") > 0); // s > "aaa"

 

문자열 검색

find : 부분 문자열 검색. 주어진 부분 문자열의 위치를 리턴한다. 리턴받은 인덱스 이후부터 찾을 수 있다.

std::size_t pos = s.find("Hello");
if (pos != std::string::npos) { /* ... */ }

 

find_first_of(), find_last_of() : 전달한 문자들 중 일치하는 문자가 있는 첫 번째/마지막 위치를 리턴한다

std::size_t pos = s.find_first_of("aeiou");
std::size_t pos = s.find_last_of("aeiou");

 

rfind : 문자열을 역방향으로 검색

std::size_t pos = s.rfind("Hello");

 

부분 문자열 처리

substr : 부분 문자열을 복사하여 반환

replace : 부분 문자열로 대체

copy : 부분 문자열을 문자 배열에 복사

std::string s = "Hello. My name is Tango.";

std::string::size_type pos = s.find("Tango");
std::string::size_type count = std::string("Tango").size();

s.replace(pos, count, "Sam"); // Tango를 Sam으로 바꿉니다.
EXPECT_TRUE(s == "Hello. My name is Sam."); 

EXPECT_TRUE(s.substr(pos, 3) == "Sam"); // 부분 문자열을 복사하여 리턴합니다.

char arr[3]; // 문자 배열
s.copy(arr, 3, pos); // 크기가 3인 arr 배열에 pos 위치에서부터 배열 크기만큼 부분 문자열을 복사 합니다.
EXPECT_TRUE(arr[0] == 'S' && arr[1] == 'a' && arr[2] == 'm');

 

Program Example

#include <iostream>
#include <string>

int main() {
    std::string str = "Hello, World!";
    
    // 문자열 길이
    std::cout << "Length: " << str.size() << std::endl;
    
    // 부분 문자열
    std::string sub = str.substr(7, 5);  // "World"
    std::cout << "Substring: " << sub << std::endl;
    
    // 문자열 검색
    std::size_t pos = str.find("World");
    if (pos != std::string::npos) {
        std::cout << "'World' found at position: " << pos << std::endl;
    }
    
    // 문자열 대체
    str.replace(7, 5, "C++");
    std::cout << "Replaced: " << str << std::endl;
    
    // 문자열 연결
    std::string str2 = " How are you?";
    str += str2;
    std::cout << "Concatenated: " << str << std::endl;
    
    return 0;
}

 

'Data Structure > C++ STL' 카테고리의 다른 글

[C++ STL] std::tuple  (0) 2024.06.30
[C++ STL] std::pair  (0) 2024.06.30
[C++ STL] 3.4 C++ 해시 테이블  (0) 2024.06.23
[C++ STL] 2.6 그래프(graph)  (0) 2024.06.21
[C++ STL] 2.5 힙(Heap)  (0) 2024.06.21

std::pair란?

  • 두 개의 이질적인 데이터 타입의 값을 하나로 묶어서 저장하는데 사용되는 템플릿 클래스
  • 두 개의 값을 리턴해야 해야 하거나, 두 개의 값을 key와 value로 사용하는데 유용하다
  • <utility>에 정의되어 있다.

 

std::pair의 구현 방식

  • 실제 구현 코드는 아니지만, 이러한 방식으로 구현되어 있다
template <typename T1, typename T2>
struct pair {
    T1 first;
    T2 second;

    // 기본 생성자
    pair() : first(T1()), second(T2()) {}

    // 사용자 정의 생성자
    pair(const T1& a, const T2& b) : first(a), second(b) {}

    // 복사 생성자
    template <typename U1, typename U2>
    pair(const pair<U1, U2>& p) : first(p.first), second(p.second) {}

    // 이동 생성자
    template <typename U1, typename U2>
    pair(pair<U1, U2>&& p) : first(std::move(p.first)), second(std::move(p.second)) {}

    // 복사 대입 연산자
    pair& operator=(const pair& p) {
        if (this != &p) {
            first = p.first;
            second = p.second;
        }
        return *this;
    }

    // 이동 대입 연산자
    pair& operator=(pair&& p) noexcept {
        if (this != &p) {
            first = std::move(p.first);
            second = std::move(p.second);
        }
        return *this;
    }

    // 비교 연산자
    bool operator==(const pair& p) const {
        return first == p.first && second == p.second;
    }

    bool operator!=(const pair& p) const {
        return !(*this == p);
    }

    bool operator<(const pair& p) const {
        return first < p.first || (!(p.first < first) && second < p.second);
    }

    bool operator<=(const pair& p) const {
        return !(p < *this);
    }

    bool operator>(const pair& p) const {
        return p < *this;
    }

    bool operator>=(const pair& p) const {
        return !(*this < p);
    }
};

 

이거 말고 다른 기능은 없나요?

  • std::pair는 map, queue, stack과 같은 컨테이너가 아니다
    • std::map과 std::unordered_map과 같은 연관 컨테이너에서 key-value쌍을 나타내기 위해 많이 사용된다
  • 두 개의 값을 묶는 단순한 구조체로, 삽입, 삭제, 검색 등의 메서드를 제공하지 않는다.
    • 삽입, 삭제, 검색 등은 std::pair를 사용하는 컨테이너에 제공된다

 

선언 및 초기화

#include <utility>

std::pair<int, std::string> p1;  // 정수와 문자열을 쌍으로 가지는 pair
std::pair<int, std::string> p2(42, "Hello");  // 생성자 초기화
auto p3 = std::make_pair(42, "Hello");  // make_pair 함수 사용

 

멤버 변수

first와 second 멤버 변수가 존재한다

std::cout << p2.first << " " << p2.second << std::endl;  // 42 Hello

 

생성자

기본 생성자, 복사 생성자, 이동 생성자, 사용자 정의 생성자를 사용할 수 있다.

std::pair<int, std::string> p4(p2);  // 복사 생성자
std::pair<int, std::string> p5(std::move(p2));  // 이동 생성자

 

비교 연산자

위 구현 코드에서 알 수 있듯이 비교 연산 또한 지원한다

std::pair<int, std::string> p6(42, "Hello");
std::pair<int, std::string> p7(42, "World");

if (p6 == p2) { /* ... */ }  // true
if (p6 < p7) { /* ... */ }   // true

 

활용 예시

함수에서 여러 개의 값을 반환해야 하는 경우

std::pair<int, std::string> getAgeAndName() {
    return std::make_pair(30, "Alice");
}

auto result = getAgeAndName();
std::cout << "Age: " << result.first << ", Name: " << result.second << std::endl;

 

map과 같은 STL에서 key-value 쌍을 저장하는 경우

#include <map>

std::map<int, std::string> myMap;
myMap.insert(std::make_pair(1, "one"));
myMap.insert(std::make_pair(2, "two"));

for (const auto& pair : myMap) {
    std::cout << pair.first << " => " << pair.second << std::endl;
}

'Data Structure > C++ STL' 카테고리의 다른 글

[C++ STL] std::tuple  (0) 2024.06.30
[C++ STL] std::string  (0) 2024.06.30
[C++ STL] 3.4 C++ 해시 테이블  (0) 2024.06.23
[C++ STL] 2.6 그래프(graph)  (0) 2024.06.21
[C++ STL] 2.5 힙(Heap)  (0) 2024.06.21

블룸 필터(bloom filter)

블룸 필터는 해시 테이블에 비해 공간 효율이 매우 높은 방법이지만, 결정적(deterministic) 솔루션 대신 부정확한 결과를 얻을 수 있다.

  • 거짓-부정(false-negative)dl 이 없다는 것은 보장하지만, 거짓-긍정(false-positive)는 나올 수 있다.
    • 즉, 특정 원소가 존재한다는 긍정적인 답변을 받을 경우, 이 원소는 실제로 있을 수도 있고 없을 수도 있다.
    • 그러나 특정 원소가 존재하지 않는다는 부정적인 답변을 받았다면 이 원소는 확실히 없다
  • 뻐꾸기 해싱과 마찬가지로 블룸 필터도 여러 개의 해시 함수를 사용한다
    • 정확도를 위해 세 개 이상을 사용해야 한다
  • 블룸 필터는 실제 값을 저장하지는 않으며, 대신 특정 값이 있는지 없는지를 나타내는 부울 타입 배열을 사용한다
  • 원소를 삽입할 경우, 모든 해시 함수 값을 계산하고 부울 타입 배열에서 이 해시 값에 대응되는 위치의 비트 값을 1로 설정한다
  • 룩업의 경우, 모든 해시 함수 값을 계산하고 이에 대응되는 위치의 비트 값이 1로 설정되어 있는지를 검사한다
    • 만약 검사한 모든 비트가 1이면 true를 반환한다
    • 1이 아닌 비트가 하나라도 있으면 false를 반환하고, 이는 해당 원소가 없음을 의미한다

블룸 필터가 결정적이지 않은 이유

  • 특정 비트가 다수 원소에 의해 1로 설정될 수 있기 때문이다.
    • 특정 값 x와 연관된 모든 비트가 이전에 삽입된 다른 원소 값들에 의해 모두 1로 설정되어 있을 가능성이 있다는 뜻이다
      • 이러한 경우 x에 대한 룩업 함수는 true를 반환할 것이다
      • 이처럼 특정 원소가 있다고 잘못 판단하는 것을 거짓-긍정이라고 한다
      • 원소의 개수가 많아질수록 거짓-긍정이 발생할 가능성은 증가한다
      • 그러나 x와 연관된 비트 중 하나라도 1로 설정되어 있지 않다면 x가 확실하게 없다고 말할 수 있다.
        • 그러므로 거짓-부정은 발생할 수 없다
  • 부울 배열의 모든 원소가 true 또는 1로 설정될 경우, 이 배열은 포화 상태가 된다
    • 이 상태에서 룩업 함수는 항상 true를 반환하고 삽입함수는 블룸 필터 상태에 아무런 영향을 주지 못한다

Example) 블룸 필터 만들기

#include <iostream>
#include <vector>

class bloom_filter
{
    std::vector<bool> data;
    int nBits;

    int hash(int num, int key)
    {
        switch(num)
        {
            case 0: return key % nBits;
            case 1: return (key / 7) % nBits;
            case 2: return (key / 11) % nBits;
        }

        return 0;
    }

public: 
    bloom_filter(int n) : nBits(n)
    {
        data = std::vector<bool>(nBits, false);
    }

    void lookup(int key)
    {
        bool result = data[hash(0, key)] & data[hash(1, key)] & data[hash(2, key)];

        if(result)
        {
            std::cout << key << " 있을 수 있음" << std::endl;
        }
        else
        {
            std::cout << key << " 없음" << std::endl;
        }
    }

    void insert(int key)
    {
        data[hash(0, key)] = true;
        data[hash(1, key)] = true;
        data[hash(2, key)] = true;

        std::cout << key << " 을(를) 삽입 ";

        for(auto a : data)
            std::cout << a << " ";

        std::cout << std::endl;
    }
};

using namespace std;

int main()
{
    bloom_filter bf(7);

    bf.insert(100);
    bf.insert(54);
    bf.insert(82);

    bf.lookup(5);
    bf.lookup(50);
    bf.lookup(20);
    bf.lookup(54);

    return 0;
}
  • 해시 함수의 인자 num은 내부에서 어떤 해시 함수를 사용할 지 결정하는 역할을 한다
    • 이렇게 함으로써 여러 개의 해시 함수를 따로 만들지 않아도 된다
  • lookup() 함수는 필요한 모든 비트가 1로 설정되어 있는지를 검사한다
  • 위 예제를 보면, 이 프로그램에서 필요한 정보를 저장하기 위해 겨우 7비트만 사용했다.
    • 필터 크기를 좀 더 크게 설정하고 해시 함수를 보완하면 훨씬 더 나은 성능을 얻을 수 있다
  • 블룸 필터는 컨테이너에 실제 데이터를 저장하지 않기 때문에 다양한 타입의 데이터에 대해서도 저장할 수 있다
    • 해시 함수를 잘 만들었다면 하나의 블룸 필터에 정수, 문자열, 상수 등의 데이터를 섞어서 삽입할 수도 있다
  • 블룸 필터를 사용하기에 적합한 실제 상황
    • 데이터 양이 너무 많아서 해시 테이블조차도 사용하기 버겁고, 거짓-양성이 있어도 괜찮은 경우
    • ex) 새로운 이메일 주소 생성 시 중복 검사를 하는 경우
      • 기본적인 중복 검사도 매우 빈번하게 수행해야 한다
      • 사용하고 있지 않은 이메일 주소를 사용중이라고 해도 큰 문제는 없다
    • ex) 새로운 추천 광고 선택 알고리즘

C++ 해시 테이블

  • 해시 구현에서 항상 양의 정수만 취급할 수는 없다.
  • 오히려 문자열 데이터를 다루게 되는 경우가 더 많다
    • 영어 사전을 구현하려면 영어 단어를 키로 사용하고, 뜻을 값으로 사용해야 한다
  • 모듈로 함수는 문자열에는 적용할 수 없다
    • 간단한 해결책은 문자열의 모든 문자에 대한 ASCII 코드 값을 모두 더한 후에 모듈로 연산을 하는 것이다.
    • 위 방법은 충돌이 빈번하게 발생할 수 있다
  • C++은 문자열로부터 해시 값을 생성하는 용도로 std::hash<std::string>(std::string) 함수 객체를 제공한다
    • 이 함수 객체 내부에는 해시 함수 알고리즘이 구현되어 있다.
  • C++은 문자열 이외에도 모든 기본 데이터 타입에 대한 해시 값을 생성하는 기능도 제공한다
  • "체이닝을 사용하는 해시 테이블"에서 구현했던 해시 테이블 코드를 템플릿 형태로 바꾸면 모든 데이터 타입에 대해 사용할 수 있는 형태로 만들 수 있다.
  • STL은 이러한 기능을 std::unordered_setstd::unordered_set<Key, Value> 형태로 미리 구현하여 제공한다
    • std::unordered_set은 키만 저장할 수 있고, std::unordered_map은 키와 value를 함께 저장할 수 있다
    • 두 컨테이너 모두 체이닝을 사용하는 해시 테이블 형태로 구현되어 있다.
      • 해시 테이블의 각 행은 키 또는 키와 값의 쌍을 저장하는 벡터이다. 여기서 각 행을 버킷(bucket)이라고 부른다
      • 즉, key로부터 해시 값을 구하면 이에 해당하는 버킷에 접근할 수 있다
    • 기본적으로 이들 컨테이너는 최대 1의 부하율을 가진다
      • 해시 테이블 크기보다 원소 개수가 많아지게 되면 곧바로 해시 테이블을 키우고, 해시 함수를 변경하는 재해싱이 일어난다
      • 사용자가 강제로 rehash()함수를 호출하여 재해싱을 할 수도 있다
      • max_load_factor(float) 함수를 사용하여 기본값이 1로 되어 있는 부하율 최대 한계치를 변경할 수도 있다
  • std::unordered_set와 std::unordered_map 컨테이너는 검색, 삽입, 삭제 등의 보편적인 기능을 제공한다
  • 모든 원소에 차례대로 접근할 수 있도록 반복자 기능도 제공하고, 벡터나 배열 같은 다른 컨테이너로부터 바로 std::unordered_set 또는 std::unordered_map을 구성할 수 있는 생성자도 제공한다.
  • std::unordered_map은 []연산자를 이용하여 주어진 키에 해당하는 값을 받을 수도 있다.
    • 파이썬의 dictionary 처럼 작동한다

Example) STL에서 제공하는 해시 테이블

#include <iostream>
#include <unordered_map>
#include <unordered_set>

void print(const std::unordered_set<int>& container)
{
    for(const auto& element : container)
        std::cout << element << " ";

    std::cout << std::endl;
}

void print(const std::unordered_map<int, int>& container)
{
    for(const auto& element : container)
        std::cout << element.first << " -> " << element.second << ", ";

    std::cout << std::endl;
}

void find(const std::unordered_set<int>& container, const int element)
{
    if(container.find(element) == container.end())   
        std::cout << element << " 검색 실패" << std::endl;
    else
        std::cout << element << " 검색 성공" << std::endl;
}

void find(const std::unordered_map<int, int>& container, const int element)
{
    auto it = container.find(element);

    if(it == container.end())
        std::cout << element << " 검색 실패" << std::endl;
    else
        std::cout << element << "검색 성공 값 = " << it->second << std::endl;
}

int main()
{
    std::cout << "*** std::unordered_set 예제 ***" << std::endl;

    std::unordered_set<int> set1 = { 1, 2, 3, 4, 5 };

    std::cout << "set1 초깃값 : ";
    print(set1);

    set1.insert(2);
    std::cout << "2 삽입 : ";
    print(set1);

    set1.insert(10);
    set1.insert(300);
    std::cout << "10, 300 삽입 : ";
    print(set1);

    find(set1, 4);
    find(set1, 100);

    set1.erase(2);
    std::cout << "2 삭제 : ";
    print(set1);

    find(set1, 2);

    std::cout << "*** std::unordered_map 예제 ***" << std::endl;
    std::unordered_map<int, int> squareMap;

    squareMap.insert({2, 4});
    squareMap[3] = 9;
    std::cout << "2, 3의 제곱 삽입 : ";
    print(squareMap);

    squareMap[20] = 400;
    squareMap[3] = 900;
    std::cout << "20, 30의 제곱 삽입 : ";
    print(squareMap);

    find(squareMap, 10);
    find(squareMap, 20);

    std::cout << "squareMap[3] = " << squareMap[3] << std::endl;
    std::cout << "squareMap[100] = " << squareMap[100] << std::endl;
    print(squareMap);

    return 0;
}
  • 이들 컨테이너에서 저장된 원소 순서는 정해져 있지 않으며, 이 때문에 컨테이너 이름에 'unordered'가 들어간다
  • [] 연산자는 key에 해당하는 실제 값이 없을 때는 기본 값 0을 추가한 후 반환해준다
  • 현재 버킷의 개수를 알고 싶으면 bucket_count() 함수를 사용할 수 있다
  • 이 외에도 load_factor(), max_bucket_count() 등의 함수를 이용하여 컨테이너 내부에서 사용되는 설정 값을 알 수 있다
  • 또한 rehash()함수를 이용하여 수동으로 재해싱을 수행할 수 있다
  • 이들 컨테이너는 체이닝 기법을 사용하여 구현되었으므로, 버킷에서 특정 키를 찾을 때 키가 같은지를 비교해야 한다
    • 그러므로 키 타입에 대해 등호 연산이 정의되어 있어야 한다. 또는 템플릿 매개변수로 비교자를 지정할 수 있다
  • std::unordered_set와 std::unordered_map은 중복된 키를 허용하지 않는다
    • 만약 중복된 값을 저장하고 싶다면 std::unordered_multiset 또는 std::unordered_multimap을 사용해야 한다
    • 이 두 컨테이너의 삽입 함수는 주어진 키가 이미 존재하는지를 검사하지 않는다.
    • 또한 이들 컨테이너는 특정 키에 해당하는 모든 값을 얻을 수 있는 기능도 지원한다
  • STL은 C++에서 지원하는 모든 기본 데이터 타입에 대한 해시 함수를 제공한다
    • 따라서 앞서 언급했던 컨테이너에서 사용자 정의 클래스 또는 구조체를 키 타입으로 사용하려면 std 네임스페이스 안에서 해시 함수를 구현해야 한다
    • 또는 컨테이너 템플릿 매개변수로 해서 해시 함수 객체를 지정할 수도 있다
      • 해시 함수를 직접 만드는 것은 성능에 큰 영향을 주기 때문에 그다지 좋은 생각은 아니다
  • 해시 함수로 MD5, SHA-1, SHA-256 같은 복잡한 암호화 함수도 사용할 수 있다
    • 암호화 함수를 사용하면, 해시 값으로 부터 원본 데이터를 알아내는 역해싱이 매우 어렵기 때문에 보안 시스템에서 사용되기도 한다

'Data Structure > C++ STL' 카테고리의 다른 글

[C++ STL] std::string  (0) 2024.06.30
[C++ STL] std::pair  (0) 2024.06.30
[C++ STL] 2.6 그래프(graph)  (0) 2024.06.21
[C++ STL] 2.5 힙(Heap)  (0) 2024.06.21
[C++ STL] 1.8 컨테이너 어댑터(Container Adaptor)  (0) 2024.06.15

해시 테이블에서 충돌

  • 다수의 키를 저장할 수 없는 문제를 해결해보자

체이닝

  • 앞에서는 하나의 해시 값에 대해 하나의 원소만을 저장했다.
    • 따라서 특정 해시 값 위치에 이미 원소가 존재한다면 새로운 값과 예전 값 중 하나를 버릴 수밖에 없었다.

체이닝(chaining)은 두 값을 모두 저장할 수 있는 여러 방법 중 하나이다

  • 이 방법은 해시 테이블의 특정 위치에서 하나의 키를 저장하는 것이 아니라, 하나의 연결 리스트를 저장한다
  • 새로 삽입된 키에 의해 충돌이 발생하면, 리스트의 맨 뒤에 새로운 키를 추가한다
    • 따라서 다수의 원소를 원하는 만큼 저장할 수 있다
  • 벡터 대신 연결 리스트를 사용하는 이유는, 특정 위치의 원소를 빠르게 삭제하기 위함이다

Example) 체이닝을 사용하는 해시 테이블

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

using uint = unsigned int;

class hash_map
{
    std::vector<std::list<int>> data;

public:
    // 해시 맵 또는 데이터의 크기를 인자로 받는 생성자
    hash_map(size_t n)
    {
        data.resize(n);
    }

    // 삽입 함수
    void insert(uint value)
    {
        int n = data.size();
        data[value % n].push_back(value);

        std::cout << value << "을(를) 삽입했습니다." << std::endl;
    }

    // 검색 함수
    bool find(uint value)
    {
        int n = data.size();
        auto& entries = data[value % n];

        return std::find(entries.begin(), entries.end(), value) != entries.end();
    }

    // 삭제 함수
    void erase(uint value)
    {
        int n = data.size();
        auto& entries = data[value % n];
        auto iter = std::find(entries.begin(), entries.end(), value);

        if(iter != entries.end())
        {
            entries.erase(iter);

            std::cout << value << "을(를) 삭제했습니다." << std::endl;
        }
    }
};


int main()
{
    hash_map map(7);

    auto print = [&](int value) {
        if(map.find(value))
            std::cout << "해시 맵에서 " << value << "을(를) 찾았습니다.";
        else
            std::cout << "해시 맵에서 " << value << "을(를) 찾지 못했습니다.";

        std::cout << std::endl;
    };

    map.insert(2);
    map.insert(25);
    map.insert(10);

    map.insert(100);
    map.insert(55);

    print(100);
    print(2);

    map.erase(25);

    return 0;
}

 

 

  • 룩업 함수는 아무래도 이전 구현보다는 살짝 느리다.
    • 이 함수는 단순히 n 값에 영향을 받는 것이 아니라, 입력 데이터에도 영향을 받는다
  • 삽입 함수의 시간 복잡도는 O(1)이다.
    • 리스트에 노드를 추가하는 연산이 단순히 값을 설정하는 것 보다는 조금 느릴 수 있지만 심하게 느리지는 않다.
    • 체이닝을 통해 얻을 수 있는 이점에 비하면 무시할 수 있는 수준이다.
  • 룩업과 삭제는 데이터 크기와 헤시 테이블의 크기에 따라 상당히 느릴 수 있다.
    • 예를 들어 모든 키가 같은 해시 값을 가질 경우, 룩업 연산은 연결 리스트에서 선형 검색 수행과 같으므로 O(N)의 시간 복잡도를 갖는다
      • 해시 테이블이 저장할 키 개수에 비해 매우 작다면 충돌이 많이 발생하게 되고, 리스트는 평균적으로 더 길어진다
      • 반대로 너무 큰 해시 테이블을 가지고 있다면 메모리 낭비가 발생한다
        • 응용 프로그램 동작 시나리오를 고려하여 해시 테이블 크기를 적절히 조절해야 한다
  • 부하율(load factor)는 해시 테이블에서 각각의 리스트에 저장되는 키의 평균 개수를 나타내며, 다음 수식을 이용하여 구할 수 있다
    • 부하율 = 전체 키 개수 / 해시 테이블의 크기
    • 만약 키 개수가 해시 테이블의 크기와 같다면 부하율은 1이다.
      • 부하율이 1보다 작으면 리스트 당 키가 하나도 저장되지 않은 경우가 있다는 것이고, 이는 메모리 낭비가 될 수 있다
      • 부하율이 1보다 크면 리스트의 평균 길이가 1보다 크다는 의미이고, 이 경우 검색, 삭제 등의 함수가 약간 느리게 동작할 수 있다
    • 이는 매우 이상적인 상태로, 모든 연산이 O(1)에 가깝게 작동하고 모든 메모리 공간을 적절하게 활용한다
  • 부하율은 항상 O(1)의 시간 복잡도로 계산할 수 있다
  • 몇몇 해시 테이블은 부하율이 1 근방의 특정 값보다 너무 크거나 작아지면 해시 함수를 변경하도록 구현되어 있으며, 이를 재해싱(rehashing)이라고 한다.
    • 즉, 해시 함수를 수정하여 부하율이 1에 가까운 값이 되도록 만드는 것이다.
    • 변경된 해시 함수에 의한 값의 분포와 부하율을 고려하여 해시 테이블의 크기도 변경할 수 있다.
  • 부하율이 해시 테이블의 성능을 결정하는 유일한 지표는 아니다
    • ex) 크기가 7인 해시 테이블에 일곱 개의 원소가 저장되어 있는데, 모든 원소가 같은 해시 값을 가져서 하나의 버킷에 있다.
      • 여기서 버킷이란 해시 테이블의 한 셀 또는 한 셀에 연결되어 있는 하나의 연결 리스트를 나타낸다
    • 검색 연산이 항상 O(1)이 아닌 O(N)의 시간 복잡도를 갖지만, 부하율은 1로 계산되버린다
    • 위 경우 해시 함수가 문제이다.
      • 해시 함수는 서로 다른 키가 가급적이면 겹치지 않고 골고루 분포되도록 해시 값을 만들어야 한다.
    • 기본적으로 버킷의 최대 크기와 최소 크기의 차이가 너무 크면 좋지 않다.
      • 위 예시에서는 차이가 7이다
    • 만약 해시 함수가 전체 일곱 개의 원소에 대해 서로 다른 해시 값을 반환한다면 검색 함수의 시간 복잡도는 O(1)이다.
      • 이 때 최대, 최소 버킷 크기 차이는 0이다
    • 이렇게 만드는 작업은 해시 테이블 구현에서 수행되지 않고, 해시 함수 자체에서 잘 고려해야 한다.
      • 해시 테이블은 해시 함수 구현에 종속적이지 않기 때문이다

열린 주소 지정(open addressing)

충돌을 해결하는 다른 방법으로 열린 주소 지정(open addressing)이 있다.

  • 이 방법은 체이닝처럼 해시 테이블에 추가적인 리스트를 붙여서 데이터를 저장하는 방식이 아니라, 모든 원소를 해시 테이블 내부에 저장하는 방식이다
    • 따라서 해시 테이블의 크기가 반드시 데이터 개수보다 커야 한다
  • 열린 주소 지정 방법의 핵심은 특정 해시 값에 해당하는 위치가 이미 사용되고 있다면, 테이블의 다른 비어 있는 위치를 탐색하는 것이다

선형 탐색(linear probing)

  • 가장 간단한 탐색 방법으로, 특정 해시 값에서 충돌이 발생하면 해당 위치에서 하나씩 다음 셀 위치로 이동하면서 셀이 비어 있는지를 확인하고, 비어 있는 셀을 찾으면 원소를 삽입한다.
    • 즉 hash(x)에 해당하는 셀이 이미 채워져 있다면 hash(x + 1) 위치의 셀을 확인한다.
      • hash(x + 1) 도 사용중이라면 hash(x + 2) 셀을 검사한다

 

  • 해시 테이블이 가득 차서 포화된 경우 재해싱 없이 새 원소를 삽입할 수 없다
  • 위 예시에서 보면 해시 테이블의 서로 인접한 군집 형태로 값이 채워졌다
  • 만약 원소 검색을 할 경우, 해시 함수에서 반환된 위치가 큰 군집의 시작 위치를 가리킨다면 클러스터의 맨 마지막 위치까지 선형 검색을 해야 한다
    • 이 경우 검색 속도가 크게 느려질 수 있다
    • 즉, 데이터가 특정 위치에 군집화(clustering)되는 경우에 문제가 발생하게 된다
      • 특정 해시 값이 너무 자주 발생해서 데이터가 몇 개의 그룹으로 뭉치는 형태로 저장된다는 의미이다

이차함수 탐색(quadratic probing)

  • 군집화 문제를 해결하기 위해 선형 방정식이 아닌 이차 방정식을 사용하여 탐색을 수행할 수 있다.
    • 이를 이차함수 탐색 이라고 한다
  • hash(x) 위치가 이미 사용중이라면, hash(x + 1^2)으로 이동하고, 그 다음은 hash(x + 2^2)의로 이동한다.
    • 이처럼 이동 폭을 이차함수 형태로 증가시키면 데이터 군집이 나타날 확률은 상대적으로 줄어든다
  • 선형 탐색 및 이차함수 탐색은 모두 원소 위치가 기존에 삽입되어 있는 다른 원소들에 의해 영향을 받는다
    • 이 때 기존에 저장되어 있던 원소는 새로 삽입하는 원소와 서로 다른 해시 값을 가질 수 있다

뻐꾸기 해싱(cuckoo hashing)

뻐꾸기 해싱(cuckoo hashing)은 완벽한 해싱 기법 중 하나이다. 앞서 언급했던 방법들은 최악의 상황에서는 O(1)의 시간 복잡도를 보장하지 않지만, 뻐꾸기 해싱은 구현만 제대로 한다면 O(1)을 만족한다

  • 뻐꾸기 해싱은 크기가 같은 두 개의 해시 테이블을 사용하고, 각각의 해시 테이블은 서로 다른 해시 함수를 가진다
  • 모든 원소는 두 해시 테이블 중 하나에 있을 수 있으며, 그 위치는 해당 해시 테이블의 해시 함수에 의해 결정된다

이전 해싱 기법과 다른점

  1. 원소가 두 해시 테이블 중 어디든 저장될 수 있다
  2. 원소가 나중에 다른 위치로 이동할 수 있다
  • 앞서 언급한 해싱 방법에서는 재해싱을 수행하지 않는 한 원소가 최초 삽입된 위치에서 다른 위치로 이동할 수 없다
    • 그러나 뻐구기 해싱 방법에서는 모든 원소가 두 개의 저장 가능한 위치를 가지며, 상황에 따라 이동할 수 있다
    • 상황에 따라 저장 가능한 위치 개수를 증가시킬 수도 있다
  • 룩업의 경우 특정 원소가 존재하는지 알기 위해 저장 가능한 위치 두 군데만 확인해보면 되므로, 룩업 연산의 시간 복잡도는 항상 O(1)이다.
  • 삽입 연산은 좀 더 오래걸릴 수 있다
    • ex) A라는 원소를 삽입하는 경우, A를 삽입할 해당 위치가 비어있다면 그대로 A를 삽입하면 된다
    • 이미 다른 원소 B가 저장되어 있다면, 해당 위치에 A를 저장하고 B를 두 번째 해시 테이블로 옮긴다
    • 만약 B가 이동할 위치에 이미 다른 원소 C가 저장되어 있다면 해당 위치에 B를 저장하고 C를 첫 번째 해시 테이블로 옮긴다
    • 이러한 작업을 완전히 비어 있는 셀이 나타날 때 까지 재귀적으로 반복한다

  • 위와 같은 과정에서 만약 순환이 발생한다면 무한 루프에 빠질 수 있다
  • 순환이 발생했다면 새로운 해시 함수를 이용하여 재해싱을 수행해야 한다
    • 재해싱 하고도 순환이 발생하여, 여러번 재해싱을 수행해야 할 수도 있다.

  • 적절한 해시 함수를 사용하면 높은 확률로 O(1)의 성능을 갖는 해시 테이블을 구성할 수 있다
  • 뻐구기 해싱도 전체 해시 테이블 크기 이상의 원소를 저장할 수는 없다
    • 높은 성능을 보장하려면 부하율이 0.5보다 작게끔 설정해야 한다
    • 즉, 전체 원소 개수가 해시 테이블 크기의 절반보다 작아야 한다

Example) 뻐구기 해싱

#include <iostream>
#include <vector>

using namespace std;

class hash_map
{
    // 두 개의 해시 테이블과 각 테이블의 크기
    std::vector<int> data1;
    std::vector<int> data2;
    int size;

    // 해시 함수 정의
    int hash1(int key) const
    {
        return key % size;
    }

    int hash2(int key) const
    {
        return (key / size) % size;
    }

public:

    // 해시 테이블을 모두 -1로 초기화
    hash_map(int n) : size(n)
    {
        data1 = std::vector<int>(size, -1);
        data2 = std::vector<int>(size, -1);
    }

    // 룩업 함수
    // 양쪽 해시 테이블에서 키를 검색하고 해당 위치에 나타내는 반복자 바노한
    std::vector<int>::iterator lookup(int key)
    {
        auto hash_value1 = hash1(key);

        if(data1[hash_value1] == key)
        {
            std::cout << "1번 테이블에서 " << key << "을(를) 찾았습니다." << std::endl;

            return data1.begin() + hash_value1;
        }

        auto hash_value2 = hash2(key);

        if(data2[hash_value2] == key)
        {
            std::cout << "2번 테이블에서 " << key << "을(를) 찾았습니다." << std::endl;

            return data2.begin() + hash_value2;
        }

        return data2.end();
    }

    void erase(int key)
    {
        auto position = lookup(key);

        if(position != data2.end())
        {
            *position = -1;
            std::cout << key << "에 해당하는 원소를 삭제했습니다." << std::endl;
        }
        else 
        {
            std::cout << key << "키를 찾지 못했습니다." << std::endl;
        }
    }

    // 삽입 함수
    void insert(int key)
    {
        insert_impl(key, 0, 1);
    }

    // 삽입 구현 함수
    // key : 키, cnt : 재귀 호출 횟수, table : 키를 삽입할 테이블 번호
    void insert_impl(int key, int cnt, int table)
    {
        if(cnt >= size)
        {
            std::cout << key << " 삽입 시 순환 발생! 재해싱이 필요합니다!" << std::endl;
            return;
        }

        if(table == 1)
        {
            int hash = hash1(key);
            if(data1[hash] == -1) 
            {
                std::cout << table << "번 테이블에 " << key << " 삽입" << std::endl;
                data1[hash] = key;
            }
            else
            {
                int old = data1[hash];
                data1[hash] = key;

                std::cout << table << "번 테이블에 " << key <<  "삽입 : 기존의 " << old << " 이동 -> ";
                insert_impl(old, cnt + 1, 2);
            }
        }

        else
        {
            int hash = hash2(key);
            if(data2[hash] == -1) 
            {
                std::cout << table << "번 테이블에 " << key << " 삽입" << std::endl;
                data2[hash] = key;
            }
            else
            {
                int old = data2[hash];
                data2[hash] = key;

                std::cout << table << "번 테이블에 " << key <<  "삽입 : 기존의 " << old << " 이동 -> ";
                insert_impl(old, cnt + 1, 1);
            }
        }
    }

    void print()
    {
        std::cout << "Index : ";
        for(int i = 0; i < size; i++)
            std::cout << i << '\t';
        std::cout << std::endl;

        std::cout <<"Data1 : ";
        for(auto i : data1)
            std::cout << i << '\t';
        std::cout << std::endl;

        std::cout <<"Data2 : ";
        for(auto i : data2)
            std::cout << i << '\t';
        std::cout << std::endl;
    }
};

int main()
{
    hash_map map(7);
    map.print();

    std::cout << std::endl;

    map.insert(10);
    map.insert(20);
    map.insert(30);
    std::cout << std::endl;

    map.insert(104);
    map.insert(2);
    map.insert(70);
    map.insert(9);
    map.insert(90);
    map.insert(2);
    map.insert(7);
    std::cout << std::endl;

    map.print();
    std::cout << std::endl;


    // 순환 발생
    map.insert(14);

    return 0;
}

 

  • 룩업 함수는 양쪽 해시 테이블에서 키를 검색하고, 해당 위치를 나타내는 반복자를 반환한다
    • 삭제 함수에서 이 반복자를 사용한다
    • 원소를 찾지 못하면 data2 테이블의 마짐가을 가리키는 반복자가 반환된다
      • O(1)의 시간 복잡도를 갖는다
  • 삭제 함수의 경우 룩업 함수가 반환한 값을 조사하여 실제 삭제 작업을 수행하거나, 단순히 문자열만 출력한다
    • O(1)
  • 삽입은 재귀적으로 동작해야 하기 때문에 삽입 구현 함수를 따로 만든다
    • 삽입 함수에서는 순환 여부를 검색해야 한다
    • 그러나 방문한 위치의 모든 값을 기억하는 것은 부담이 클 수 있다
    • 그러므로 여기서 단순히 재귀 호출 횟수가 몇 회 이상이 되면 순환으로 간주하여 구현한다
    • 이 때 최대 재귀 호출 횟수는 해시 테이블의 크기와 같게 설정하였다
  • 원소 삽엡에서만 어느 정도 시간을 필요로 하므로, 위 구현 코드는 원소 삽입보다 룩업 연산이 훨씬 많은 application에서 적합하다

+ Recent posts