해시맵 C++

 데이터 검색시 시간 복잡도가 상수라고 알려진 해시맵

---

Index

• 해시함수
• 해시맵
  • 해시맵 구현
• 해시충돌
  • 공간 확장
  • 체이닝(chaining)
  • 재배치

Script from F.R.I.D.A.Y

---

 데이터를 저장하는 하나의 방법으로 <key, value>의 쌍을 이룬다. 특정 key를 기반으로 value를 저장했을때, 저장한 value를 찾기 위해서는 key를 기반으로 검색한다.

 

 해시맵을 알기 위해서는 해시함수를 필연적으로 알아야한다.

 

해시함수copy^

 어떤 정보를 수학적인 연산처리에 의해 고유한 값을 만들어내는 함수다. 즉, A라는 값을 해시함수에 넣었을 때 1이란 값이 나오고 B라는 값을 해시함수에 넣었을 때 2란 값이 나오는 방식이다.

 

 위 예시에서 순차적으로 값을 내어주었기 때문에 혼동할 수 있는데, 해시함수는 아래의 조건을 만족해야 안정적인 함수이다.

• 눈사태효과를 가진다.^[1]
• 입력에는 하나의 출력만 존재한다.^[2] 즉, 여러 입력이 하나의 출력으로 귀결되지 않는다.

 

 해시 함수는 굉장히 다양한 곳에서 사용되는데, 보안분야^[3]에서 이용하거나 파일의 무결성을 확인하는 용도로 사용하곤 한다.

 

---

해시맵copy^

 해시맵은 <해시함수>의 특성을 이용해 만든 자료구조이다. <key, value>에서 고유한 key 값을 가지므로, key에 맞는 메모리 공간에 value를 입력하고 읽어들이는데 유용하다. 즉, 해시맵의 핵심은 해시함수라는 점이다.

 

해시맵 구현copy^

 다음은 실제 해시맵의 작동 방식을 보기 위해 작성한 예제 코드이다.

해시맵 예제 코드

#include <stdio.h>

class hashMap {
    int* list;
    size_t capacity;

public:
    int GetHashValue(const char* key) {
        int value = 0;
        for (int i = 0; key[i]; ++i) {
            value += key[i];
        }
        return value % capacity;
    }

    void Input(const char* key, int value) {
        int index = GetHashValue(key);

        printf("---입력---\n");
        printf("  key: %s\n", key);
        printf("value: %d\n", value);
        printf("index: %d\n", index);
        printf("\n");

        list[index] = value;
    }

    int Output(const char* key) {
        int index = GetHashValue(key);
        int value = list[index];
        printf("---출력---\n");
        printf("  key: %s\n", key);
        printf("value: %d\n", value);
        printf("index: %d\n", index);
        printf("\n");
        return value;
    }

    void Print() {
        printf("해시맵 출력:\n\n");
        for (size_t i = 0; i < capacity; ++i) {
            printf("%3d: %3d%c", i, list[i], (i + 1) % 5 ? '\t' : '\n');
        }
        printf("\n\n");
    }

public:
    hashMap() : hashMap{10} {
    }

    hashMap(size_t capacity) : capacity{capacity}, list{nullptr} {
        list = new int[capacity] {};
    }

    ~hashMap() {
        if (list) {
            delete[] list;
            list = nullptr;
        }
    }

};

int main() {
    hashMap hmap{};

    hmap.Print();

    hmap.Input("Hello world", 432);
    hmap.Input("world", 5);
    hmap.Input("programming", 1);

    hmap.Print();

    hmap.Output("world");

}

 참고: C++의 표준 입출력 라이브러리는 iostream이지만 예제이기도 하고 편의상 C 표준 입출력 라이브러리인 stdio.h를 사용했다.

해시맵 예제 코드

 코드를 보면 내부 데이터는 배열로 관리가 되지만, 각 인덱스 요소에 접근할 때는 GetHashValue 메서드를 통해 이루어짐을 볼 수 있다. 

 

 

해시충돌copy^

 좋은 해시함수는 입력과 출력의 값이 1:1 대응하도록 구성한다. 그러나 1:1로 대응시켜 메모리를 처리하려면 상당한 양의 메모리 소비가 발생할 수밖에 없다.

 

 예컨데 <해시맵 구현>에서 보인 코드에서 키값으로 world를 준 공간은 다른 키값으로도 접근이 가능하다. 예제에서 제공한 해시함수의 경우 전달받은 모든 문자열을 더한 값을 해시맵 공간(capacity)로 나눈 나머지로 출력을 하고 있다. 즉, 키값으로 world로 준 것과 world 문자열을 reverse한 dlrow로 준 것이나 동일한 공간을 가리킨다는 점이다. 때문에 적절한 해시함수를 구현하는 것이 해시맵의 중점이다.

 

 이런 식으로 동일 공간을 가리키게 되면 주로 알려진 대응책으로는 몇가지가 있다.

 

# 해시충돌을 관리하기 위해서는 key값이 저장되어야 한다.

 

공간 확장copy^

 예제에서 제공하는 해시함수를 이용한경우 이 방식은 사용할 수 없다. 해시함수가 어떻게 되던 동일한 공간을 가리키기 때문이다.

 

 그러나 예제의 해시함수를 사용하지 않고 더 나은 해시함수를 사용한다면 이야기가 달라진다. world와 dlrow의 고유값이 다르다면, 예컨데 해시맵 공간의 크기와 world 키의 고유값은 20이고 dlrow는 40이라면 공간을 두 배 늘리는 것으로 다른 공간을 가리키도록 구현할 수 있다.

 

왜 예제의 해시함수로는 이 방식을 사용할 수 없는가

 예제의 해시함수는 첫 문자부터 마지막문자의 값을 모두 더한 합을 해시맵의 capacity값으로 나눈 나머지를 반환하도록 구현되어 있다.

1. 첫 문자부터 마지막 문자까지의 합을 구한다. 이 값을 plainValue라 가정한다.
2. plainValue의 값을 capacity로 나눈 나머지를 반환한다. 반환되는 값을 adjustValue라 가정한다.

이 경우 실제 메모리 접근에 영향을 주는 값은 plainValue이다. 그러나 예제로 제공하는 해시함수를 사용하면 world나, 이를 뒤집은 dlrow나 동일한 plainValue를 가지게 되므로 공간확장을 통해 충돌을 제어하는 방식은 유용하지 않다.

왜 예제의 해시함수로는 이 방식을 사용할 수 없는가

 이 방식의 최대 단점은 해시함수의 의존도가 상당히 높다는 점이다. 만일 해시충돌이 자주 일어나는 해시함수를 사용하는 경우, 해시충돌을 공간 확장으로 방어할수는 없다. 때문에 이 방식은 가급적 다른 방식을 사용하면서 보조하는 수준으로 생각해야한다.

 

체이닝(chaining)copy^

 충돌이 일어났을 때 연결리스트(Linked List)를 이용하는 방식이다. 때문에 내부적으로 연결리스트 형식으로 값을 보관해야한다.

 

 이미지로 보게 되면 아래와 같다.

 충돌이 일어나면 동일 인덱스 상에 연결리스트를 구성해서 관리하는 방식이다. 이 방식으로 충돌 제어를 하게 되면 고정된 해시맵에서 무한정 데이터 첨삭이 가능하다.

 

 다만, 인덱스에 접근한 이후에는 연결리스트에서의 탐색으로 진행하므로 연결리스트 관리도 함께 해주는편이 성능 향상에 좋다.

 

재배치copy^

 해시맵에 데이터를 넣을 때 처음 접근하는 인덱스에 이미 데이터가 존재해 충돌이 일어나게 되면, 연산을 거쳐 새로운 위치에 집어넣는 방식이다. 해당 방식은 공간의 크기는 조절하지 않으므로 만일 해시맵이 모두 찼다면 구현에 따라서 오류를 일으킬 수 있다. 때문에 <공간 확장>옵션과 함께 사용해야한다.

 

 "world"키를 기반으로 설명하면, 해당 키값을 예제 코드로 연산하게 되면^[4] 2번 인덱스를 가리킨다. 그 다음 "dlrow" 키를 연산하면 동일하게 2번 인덱스를 가리키는데, 이미 해당 공간은 "world"가 가지고 있으므로 충돌이 일어난다.

 

 이 때 충돌이 일어나면 해당 인덱스에서 3을 더하는 것으로 충돌을 무마시킨다. 때문에 "dlrow"는 5번 인덱스를 가지게 된다.