[Data Structures] 챕터11. 해슁(Hashing)

보간탐색

---

• 인덱스와 값의 크기는 비례하다고 가정
• 작은 값은 작은 인덱스부터 탐색한다. 큰 값은 큰 인덱스부터 탐색한다

첫 값부터 마지막 값 사이의 길이 : 첫 값부터 x값까지 길이  = 인덱스 길이 : Position 길이

(arr[high] - arr[low]) : (x - arr[low]) = (high - low) : (pos - low) 

 

이 때 버림을 활용하여 index 값이 

int InterpolationSearch(int arr[], int low, int high, int x)
{
    rec_count++;

    if (low <= high && x >= arr[low] && x <= arr[high])
    {
        int pos = (low + high) / 2; // 이진 탐색 (중간)

        // (arr[high] - arr[low]) : (x - arr[low]) = (high - low) : (pos - low) 
        float tofloor = (high - low) * (x - arr[low]) / (arr[high] - arr[low]);
        pos = int(tofloor) + low;

        if (arr[pos] == x)
            return pos;

        if (arr[pos] < x)
            return InterpolationSearch(arr, pos + 1, high, x);

        if (arr[pos] > x)
            return InterpolationSearch(arr, low, pos - 1, x);
    }

    return -1;
}

 

색인 순차 탐색

---

• 원 배열을 각 m개로 나누고 나누어진 배열의 첫 값을 인덱스 배열에 등록한다. 인덱스 배열의 개수는 n/m이다.
• 인덱스 배열을 참고하여 값을 찾으면 인덱스 배열에 있는 n/m개를 순회하고 나누어진 배열의 원소 m개를 탐색한다.
• 값 8을 찾기 위해 인덱스 요약 표를 보자.  인덱스 0부터 3 사이가 8의 자리이다. 해당 범위만 탐색하면 효율적이다

시간복잡도

• 시간복잡도 : O( m + n/m )
• 이 때 이진탐색( https://hoplite.tistory.com/163 )을 활용하면 시간복잡도는 O ( log(m) + n/m )
• 위는 인덱스 배열의 개수를 n/m이라 가정. 인덱스 배열의 개수를 m이라고 가정하면 위의 식은 변형되어야 한다

 

구현하기

#include <iostream>

using namespace std;

int SequentialSearch(int arr[], int start, int stop, int x)
{
    for (int i = start; i < stop; i++)
    {
        if (arr[i] == x)
            return i;
    }

    return -1;
}

int main()
{
    int arr[] = { 1, 2, 8, 13, 22, 45, 55, 75, 88 };
    int n = sizeof(arr) / sizeof(arr[0]);

    int keys[] = { 1, 13, 55 };
    int kn = sizeof(keys) / sizeof(keys[0]);

    int indices[] = { 0, 3, 6, n }; // 마지막에 n 하나 더 추가

    /* 풀이 */

    return 0;
}

 

내풀이

int main()
{
    
    for (int x : {1, 2, 8, 13, 22, 45, 55, 75, 88, 99, -1, 47, 101, 1000, 7, 10, 50, 60 })
    {
        if (x < arr[0] || x > arr[n - 1])
            cout << x << " was not found" << endl;
        else
        {
            int found = -1;
            for (int i = 1; i < kn; ++i)
            {
                if (keys[i - 1] <= x && x < keys[i])
                    found = SequentialSearch(arr,indices[i - 1], indices[i], x);
            }

            if (keys[kn - 1] <= x)
                found = SequentialSearch(arr, indices[kn - 1], n, x);

            if (found != -1)
                cout << x << " was found at " << found << endl;
            else
                cout << x << " was not found" << endl;
        }
    }
    
}

 

추천풀이

int main()
{
    ...
    for (int x : {1, 2, 8, 13, 22, 45, 55, 75, 88, 99, -1, 47, 101, 1000, 7, 10, 50, 60 })
    {
        if (x < arr[0] || x > arr[n - 1])
            cout << x << " was not found" << endl;
        else
        {
            // 인덱스 테이블에서 검색할 범위 결정
            int kIdx = 0;
            while (kIdx < kn - 1 && keys[kIdx + 1] <= x)
                kIdx++;

            // 색인 표의 범위에 따라서 선형 탐색
            // indices[kIdx] 이상 indices[kIdx+1] 미만에 대해 검색
            // 이때 indices 배열 마지막에 추가로 n을 저장해뒀기 때문에 kIdx+1 사용 가능
            int found = SequentialSearch(arr, indices[kIdx], indices[kIdx + 1], x);
            if (found >= 0)
                cout << x << " was found at " << found << endl;
            else
                cout << x << " was not found" << endl;
        }
    }
    ...
}

 

해쉬 테이블

---

• key 값과 value 값을 함께 저장한다.
• 각 값은 key 값을 index로 배열에 저장한다.
• key 값의 범위가 아주 넓고 삽입되는 아이템의 개수가 적을 때 모든 경우의 수를 담는 배열을 만드는 건 비효율적이다
• 이 때 key 값을 정해진 배열 범위로 변환하는 함수를 Hash Function이라 한다 예) 나머지 연산자

충돌 : 빈 공간이 남아있지만 중복된 Hash 값 때문에 예전 값을 잊어버리는 경우 / 덮어쓸 수 없는 경우

 

팁

size_t = unsigned long long : 부호가 없는 64비트 정수

키값이 비슷하더라도 변환된 해쉬값은 아주 달라지는 것이 일반적이다

예) Hash Calculator Online — String & File Hash Generator (pelock.com)

1. • "apple"의   md2 해쉬값 8015C9542CAC74759F9F7196394CC25D
   • "apple1"의 md2 해쉬값 BC3BFE69BCDC1DD4EA055ADF80D3BAA6 <- "1" 차이로 크게 달라짐

 

Hash로 저장하기

아래 구현에서 동일한 Hash값이 만들어지는 서로 다른 두 Item이 삽입되면 이전에 저장된 값을 잊어버린다

void Insert(const Item& item)
{
    size_t index = HashFunc(item.key); // 키를 인덱스로 사용
    table_[index] = item;
}

V Get(const K& key)
{
    size_t index = HashFunc(key);
    return table_[index].value;
}

// 정수 -> 해쉬값
size_t HashFunc(const int& key)
{
    return key % capacity_;
}

 

충돌 처리하기(중복된 Hash 값 처리하기)

1. 개방 주소법(Open Addressing)

• 개방 주소법은 빈공간을 찾아 값을 저장한다
• 선형조사법이라고도 한다 (한 칸씩 이동하여 값을 확인)

Insert

void Insert(const Item& item)
{
    size_t index = HashFunc(item.key); // 키를 인덱스로 사용
	
    // int()의 초기값은 0
    while (table_[index].key != 0)
        ++index;

    table_[index] = item;
}

 

Get

내구현

V Get(const K& key)
{
    size_t index = HashFunc(key);
    while (index < capacity_ && table_[index].key != key)
        ++index;

    return index < capacity_ ? table_[index].value : 0;
}

 

추천구현

• (index + i) % capacity에서 i 값이 0부터 capacity -1까지 순회함을 확인하자
• index 값 temp는 처음 얻은 HashFunc 값에서 바로 직전 값까지 한바퀴를 순회한다

V Get(const K& key)
{
    size_t index = HashFunc(key);
    for (int i = 0; i < capacity_; i++)
    {
        size_t temp = (index + i) % capacity_; // index를 덮어쓰는 것이 아니라 임시 변수 만들기 
        if (table_[temp].key == key)
            return table_[temp].value;
    }
    return 0; // 정수 int()의 초기값은 0
}

 

숫자가 아닌 자료형을 Key 값으로 사용하기(String)

HashFunc

// 문자열을 정수 인덱스(해쉬값)로 변환
// Horner's method
size_t HashFunc(const string& s)
{
    int g = 31;

    size_t index = 0;
    for (int i = 0; i < s.size(); ++i)
        //index += int(s.at(i)); // 1) AB와 BA가 같은 Hash 값을 가진다
        index = g * index + int(s.at(i)); 
        // 2) g * (g * int('A') + int('B')) + int('C')
        // 따라서 AB와 BA가 달라진다.

    return index % capacity_;
}

 

Insert

key값을 K의 기본 생성자와 비교하여 비어있는 값을 확인한다. K가 문자열일 때 K()는 비어있는 문자열이다.

void Insert(const Item& item)
{
    size_t index = HashFunc(item.key); // 키를 인덱스로 사용

    if (table_[index].key != K())
        cout << "Collision!" << endl;

    // key가 int 자료형일 때 0이면 비어있는 것으로 가정
    // key가 문자열 자료형일 때 길이가 0이면 비어있는 것으로 가정
    //while (table_[index].key != K()) 
    //    index = (index + i) % capacity_; // infinite loop
    //table_[index % capacity_] = item;

    for (int i = 0; i < capacity_; ++i)
    {
        index = (index + i) % capacity_;
        if (table_[index].key == K())
        {
            table_[index] = item;
            return;
        }
    }

    std::cout << "Failed to insert\n"
}

 

Get

내구현

V Get(const K& key)
{
    size_t index = HashFunc(key);
    while (index < capacity_ && table_[index].key != key)
        ++index;

    return index < capacity_ ? table_[index].value : V(); // 빈 생성자를 호출하여 반환
}

 

추천구현

V Get(const K& key)
{
    size_t index = HashFunc(key);
    for (int i = 0; i < capacity_; i++)
    {
        size_t temp = (index + i) % capacity; 
        if (table_[temp].key == key)
            return table_[temp].value;
    }
    return V();
}

 

2. Chainning

• 연결리스트를 사용한다.
• 위에서 구현한 Item* table_ 대신에 LinkedList<Item>* table_을 사용하자

 

다양한 해쉬함수

폴딩 함수

큰 숫자를 해쉬값으로 변환할 때 자리수에 따라 접을 수도 있습니다

123456789를 123 + 456 + 789 로 3자리씩 더한다

 

Quadratic probing(이차 조사법)

선형 조사법은 충돌이 많은 경우 배열 일부에 몰려 저장된다. 이를 해결하기위해 Quadratic Probing 를 사용할 수 있다

size_t temp = (index + i*i) % capacity;

참고 https://www.codingeek.com/data-structure/complete-guide-open-addressing-classification-eliminate-collisions/