해시(Hash) 함수와 충돌(Collision) 해결 전략: 효율적인 데이터 관리

안녕하세요, 스터디 3주차입니다. 이번 시간에는 해시(Hash)와 해시 충돌(Collision)에 대해 탐구를 해보려고 합니다.
프로그래밍에서 해시가 어떻게 사용되는지, 그리고 충돌 문제를 어떻게 해결하는지 예시와 함께 알아보겠습니다.
또한 문제도 풀어보면서 해시를 같이 경험하면 좋겠습니다. 😄

 

1. 해시(Hash)란?

 

해시(Hash)는 해시 함수를 사용하여 입력 값을 고정된 크기의 어떠한 해시 값으로 변환하여 매핑하는 것을 말합니다. 이 과정에서 원본 데이터의 크기나 형식과 상관없이 해시 값은 일정한 크기를 가지게 되며, 주로 빠른 데이터 검색, 암호화, 무결성 검증 등 다양한 분야에서 활용됩니다.

 

해시의 핵심은 효율적인 데이터 관리입니다. 일반적으로 데이터베이스, 캐시 시스템, 검색 엔진, 컴파일러 등에서 데이터의 중복성을 줄이고 검색 속도를 높이기 위해 해시가 사용됩니다. 해시를 사용하면 빠르게 특정 데이터를 찾을 수 있는 이유는 해시 테이블이라는 자료 구조 덕분입니다. 해시 테이블은 해시 함수에 의해 생성된 해시 값을 인덱스로 사용하여  키(Key)와 값(Value)을 저장하고 키(Key)로 검색할 수 있습니다. 이 과정을 통해 평균적으로 O(1)의 시간 복잡도로 데이터를 처리할 수 있습니다.

---

2. 해시함수

해시함수

 

해시 함수는 임의의 길이의 데이터를 고정된 길이의 해시 값으로 변환하는 수학적 함수입니다. 좋은 해시 함수는 주어진 데이터에 대해 고유하고 예측 불가능한 해시 값을 생성해야 하며, 서로 다른 입력이 동일한 해시 값을 갖는 경우를 최소화해야 합니다.

---

2.1. 나눗셈법

나눗셈법

나눗셈법(Division Method)은 해시 값을 계산하는 가장 간단한 방법 중 하나입니다. 주어진 키를 특정 정수로 나누고, 나머지를 해시 값으로 사용하는 방식입니다.

공식

H(X) = X mod M

• X는 키 값, M은 소수, mod는 모듈러연산(나눈 나머지)
• 여기서 M은 테이블의 크기(보통 소수)입니다. 이 방법은 구현이 간단하지만, 테이블 크기에 따라 충돌이 발생할 수 있습니다. 소수를 선택하는 이유는 키의 고른 분포를 보장하기 위함입니다. 예를 들어, M이 2의 제곱수라면 짝수 키들이 동일한 해시 값을 가질 가능성이 커집니다.

예시

int hashFunction(int key, int tableSize) {
    return key % tableSize;
}

 

장점

• 구현이 매우 간단하고 빠릅니다.

단점

• 해시테이블의 크기가 커지면 더 큰 소수가 필요합니다. (소수를 찾는게 어려움)
• 키의 패턴에 따라 충돌이 발생할 수 있으며, 해시 테이블의 크기를 적절히 설정하지 않으면 불균형하게 분포될 수 있습니다.

---

2.2. 곱셈법

곱셈법

곱셈법(Multiplication Method)은 나눗셈법과 다르게, 소수를 활용하지 않고, 키에 특정 상수(황금비)를 곱하여 해시 값을 생성하는 방법입니다. 이 방식은 나눗셈법에 비해 해시 값이 더 균등하게 분포되는 경향이 있습니다.

공식

H(X) = ((X * A) mod 1) * M

• X는 키 값, A는 황금비, M은 최대 테이블 사이즈 (소수)
• 황금비는 a/b = a / (a+b) -> 대략 1.6180339887... (소수점 부분이 A로 활용됩니다.)

예시

int hashFunction(int key, int tableSize) {
    double A = 0.6180339887; // 상수 값
    double temp = key * A;
    double fractionalPart = temp - int(temp); // 소수점 부분만 추출
    return int(tableSize * fractionalPart);
}

장점

• 키의 고유한 패턴에 의존하지 않기 때문에 나눗셈법에 비해 더 균일한 해시 값 분포를 가집니다.

단점

• 계산이 조금 더 복잡하고, 해시 값이 항상 최적의 분포를 보장하지는 않습니다.

---

2.3. 문자열 해싱

문자열 해싱은 키(Key) 값이 문자열로 주어질때, 문자열의 아스키 코드 값을 활용하여 해시 값으로 변환하는 방법입니다.

공식

H(S) = (S[0] + S[1] * P + S[2] * P^2 + ... + S[N-1]*P^(N-1)) mod M

• 문자열은 아스키코드로 매칭해서 사용
• P는 홀수이면서 메르센 소수를 사용, M은 최대 버킷 갯수
• P는  문자열 길이가 길어질 수록 계속 제곱 [ P ^ (문자열갯수 - 1)] 해나가기 때문에 OverFlow가 발생할 수 있음
• 변형식을 사용할 수 있음 - (A+B) % C = ((A%C) + (B%C))
• H(S) = (S[0] % M + S[1] * P % M + S[2] * P^2 % M + ... + S[N-1]*P^N-1) mod M

예시

const int M = 1000003; // 해시 테이블의 크기
const int a = 1000;    // 상수 값

int hashFunction(const string &s) {
    int hashValue = 0;
    for (char c : s) {
        hashValue = (hashValue * a + c) % M;
    }
    return hashValue;
}

장점

• 문자열의 패턴을 효율적으로 검색할 수 있습니다.
• 특히 긴 문자열에서 해시 충돌을 줄이기 위해 사용됩니다.

단점

• 긴 문자열에서 해시 값을 계산하는 데 시간이 걸릴 수 있습니다.
• 적절한 상수와 모듈러 값을 선택하지 않으면 충돌이 발생할 수 있습니다.

---

 

3. 해시 충돌 (Hash Collision)

해시 충돌이란 서로 다른 두 개의 입력 값이 동일한 해시 값을 갖는 상황을 말합니다. 이는 해시 함수가 다양한 입력을 고정된 크기의 해시 값으로 매핑하기 때문에 불가피하게 발생할 수 있습니다. 해시 충돌을 해결하기 위해 다양한 방법이 있으며, 이를 잘 처리하지 않으면 해시 테이블의 효율성이 크게 감소할 수 있습니다.

---

3.1. 체이닝 (Chaining)

체이닝 방식

 

체이닝은 해시 충돌을 해결하기 위한 가장 기본적인 방법입니다. 충돌이 발생한 경우, 동일한 해시 값을 갖는 여러 개의 항목을 연결 리스트(Linked list)로 저장합니다. 실제 표준라이브러리에서는 좀 더 효율적인 처리를 위해 레드블랙트리 (균형 이진트리)로 처리됩니다.

예시

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

using namespace std;

class HashTable {
    int BUCKET; // 해시 테이블의 크기
    vector<list<int>> table; // 연결 리스트로 이루어진 해시 테이블

public:
    HashTable(int b) : BUCKET(b), table(b) {}

    // 키 값을 해시 테이블에 삽입
    void insertItem(int key) {
        int index = key % BUCKET; // 해시 함수
        table[index].push_back(key);
    }

    // 키 값을 해시 테이블에서 삭제
    void deleteItem(int key) {
        int index = key % BUCKET;
        table[index].remove(key);
    }

    // 해시 테이블 출력
    void displayHash() {
        for (int i = 0; i < BUCKET; i++) {
            cout << i;
            for (auto x : table[i]) {
                cout << " --> " << x;
            }
            cout << endl;
        }
    }
};

int main() {
    // 예제 사용
    int n = 7;
    int keys[] = {15, 11, 27, 8, 12, 18, 14};
    
    HashTable hashTable(n);
    
    for (int key : keys) {
        hashTable.insertItem(key);
    }

    hashTable.displayHash();
    
    return 0;
}

장점

• 충돌이 발생할 때마다 간단히 항목을 추가할 수 있음
• 해시 테이블의 크기를 변경하지 않고도 쉽게 확장 가능

단점

• 연결 리스트에 많은 항목이 쌓이면 탐색 시간(O(n))이 길어질 수 있음
• 추가적인 메모리 공간이 필요

---

3.2. 개방 주소법 - 선형 탐사 (Open Addressing - Linear Probing)

개방주소법

 

개방 주소법은 충돌이 발생할 경우, 해시 테이블 내에서 빈 공간을 찾아 데이터를 삽입하는 방법입니다. 선형 탐사는 충돌 발생 시 테이블 내에서 순차적으로 다음 빈 공간을 탐색하는 방식입니다.

공식

H(X, I) = (H(X) + I ) mod M

• X는 키 값, M은 최대 버킷 갯수 (소수)
• I : 충돌시 이동할 버킷 수 (임의의 수)

예시

#include <iostream>
#include <vector>

using namespace std;

class HashTable {
    vector<int> table;
    int size;
    int EMPTY;

public:
    HashTable(int s) : size(s), table(s, EMPTY), EMPTY(-1) {}

    // 키 값을 해시 테이블에 삽입
    void insertItem(int key) {
        int index = key % size;
        int originalIndex = index;

        // 충돌 시 선형 탐사
        while (table[index] != EMPTY) {
            index = (index + 1) % size;
            if (index == originalIndex) {
                cout << "테이블이 가득 찼습니다!" << endl;
                return;
            }
        }
        table[index] = key;
    }

    // 키 값을 해시 테이블에서 삭제
    void deleteItem(int key) {
        int index = key % size;

        // 선형 탐사로 삭제할 항목 탐색
        while (table[index] != EMPTY) {
            if (table[index] == key) {
                table[index] = EMPTY;
                return;
            }
            index = (index + 1) % size;
        }
    }

    // 해시 테이블 출력
    void displayHash() {
        for (int i = 0; i < size; i++) {
            if (table[i] == EMPTY) {
                cout << i << " --> " << "EMPTY" << endl;
            } else {
                cout << i << " --> " << table[i] << endl;
            }
        }
    }
};

int main() {
    // 예제 사용
    int keys[] = {50, 700, 76, 85, 92, 73, 101};
    int n = 11; // 해시 테이블 크기

    HashTable hashTable(n);

    for (int key : keys) {
        hashTable.insertItem(key);
    }

    hashTable.displayHash();

    return 0;
}

장점

• 모든 데이터가 동일한 배열에 저장되어 있어 연결 리스트를 사용하는 체이닝보다 메모리 관리가 효율적입니다.
• 해시 테이블의 메모리 사용량이 적습니다.

단점

• 해시 충돌이 연속적으로 발생하면 탐색 시간이 길어질 수 있습니다.
• 해시 테이블이 꽉 차면 데이터를 더 이상 저장할 수 없습니다.
• 클러스터링(Clustering) 문제: 충돌이 많을 경우 인접한 공간이 점점 채워져 성능 저하 발생

---

 

3.3. 개방 주소법 - 이중 해싱 (Open Addressing - Double Hashing)

이중 해싱은 두 개의 해시 함수를 사용하는 방법으로, 충돌이 발생할 경우 두 번째 해시 함수로부터 다음 빈 공간의 인덱스를 계산하여 저장하는 방식입니다. 이는 선형 탐사의 클러스터링 문제를 완화시킬 수 있습니다.

공식

H(X, I) =(H1(X) + I * H2(X)) mod M

• H1 : 첫 번째 해시 함수, H2 : 두 번째 해시 함수
• X는 키 값, M은 최대 버킷 갯수 (소수)
  • • 클러스터링(Clustering) 문제를 줄이기 위해 M을 제곱수나 소수로 함
• I : 충돌시 이동할 버킷 수 (임의의 수)

예시

#include <iostream>
#include <vector>

using namespace std;

class HashTable {
    vector<int> table;
    int size;
    int EMPTY;

    // 첫 번째 해시 함수
    int hash1(int key) {
        return key % size;
    }

    // 두 번째 해시 함수
    int hash2(int key) {
        return 1 + (key % (size - 1));
    }

public:
    HashTable(int s) : size(s), table(s, EMPTY), EMPTY(-1) {}

    // 키 값을 해시 테이블에 삽입
    void insertItem(int key) {
        int index = hash1(key);
        int stepSize = hash2(key);
        int originalIndex = index;

        // 충돌 시 이중 해싱
        while (table[index] != EMPTY) {
            index = (index + stepSize) % size;
            if (index == originalIndex) {
                cout << "테이블이 가득 찼습니다!" << endl;
                return;
            }
        }
        table[index] = key;
    }

    // 키 값을 해시 테이블에서 삭제
    void deleteItem(int key) {
        int index = hash1(key);
        int stepSize = hash2(key);

        // 이중 해싱으로 삭제할 항목 탐색
        while (table[index] != EMPTY) {
            if (table[index] == key) {
                table[index] = EMPTY;
                return;
            }
            index = (index + stepSize) % size;
        }
    }

    // 해시 테이블 출력
    void displayHash() {
        for (int i = 0; i < size; i++) {
            if (table[i] == EMPTY) {
                cout << i << " --> " << "EMPTY" << endl;
            } else {
                cout << i << " --> " << table[i] << endl;
            }
        }
    }
};

int main() {
    // 예제 사용
    int keys[] = {50, 700, 76, 85, 92, 73, 101};
    int n = 11; // 해시 테이블 크기

    HashTable hashTable(n);

    for (int key : keys) {
        hashTable.insertItem(key);
    }

    hashTable.displayHash();

    return 0;
}

장점

• 이중 해싱은 선형 탐사와 비교하여 더 나은 분포를 제공
• 충돌이 발생할 가능성이 낮아지고, 클러스터링 문제를 줄여줍니다.

단점

• 두 개의 해시 함수를 사용하므로 구현이 더 복잡
• 해시 테이블의 크기가 소수로 설정되어야 효율적

 

4. 그럼 언제 해시를 사용해서 문제를 해결해야 할까?

해시를 사용하면 많은 장점이 있지만, 모든 상황에서 최적의 선택은 아닙니다. 아래는 해시를 사용하여 문제를 해결할 수 있는 대표적인 경우입니다.

• 빠른 데이터 검색과 삽입
  • 해시는 평균적으로 O(1)의 시간 복잡도로 데이터를 검색하고 삽입할 수 있기 때문에, 데이터베이스 시스템이나 검색 엔진에서 대량의 데이터를 빠르게 관리하는 데 유리합니다. 예를 들어, 웹 브라우저의 캐시 시스템은 해시를 사용하여 자주 방문하는 웹 페이지를 효율적으로 저장하고 검색합니다.
• 중복검사
  • 해시를 사용하면 데이터의 중복성을 빠르게 검사할 수 있습니다. 예를 들어, 배열이나 리스트에서 중복 항목을 제거할 때 해시 테이블을 사용하여 각 요소를 해시 값으로 변환하고 중복 항목을 걸러낼 수 있습니다.
• 암호화 및 데이터 무결성 검증
  • 해시는 암호화 알고리즘에서 데이터의 무결성을 검증하는 데 사용됩니다. 파일의 체크섬이나 디지털 서명은 해시 값을 사용하여 데이터의 변경 여부를 확인합니다. 예를 들어, 파일 전송 중에 해시를 사용하여 데이터가 손상되지 않았는지 확인할 수 있습니다.
• 특정 키에 대한 값 매핑
  • 해시 테이블은 특정 키에 대한 값을 효율적으로 저장하고 검색하는 데 유용합니다. 예를 들어, 사전(Dictionary)에서 단어와 의미를 매핑하거나, 사용자 ID와 사용자 정보를 연결할 때 해시 테이블을 사용하면 성능이 향상됩니다.
• 유사 검색 문제
  • 해시는 문자열 검색 알고리즘에서 유사 검색 문제를 해결하는 데 사용됩니다. 예를 들어, 롤링 해시는 긴 텍스트에서 특정 패턴을 찾는 KMP 알고리즘과 함께 사용되어 효율적인 문자열 검색을 할 수 있게 합니다.

 

5. 코딩 테스트 문제 풀이 (c++ unordered_map 사용)

백준 1620번 나는야 포켓몬 마스터 이다솜 문제 링크 :

https://www.acmicpc.net/problem/1620

 

문제 풀이 소스코드 공유 :

http://boj.kr/10bbc2db2ca147a1b1f8f0209fe69c1f

 

해시와 해시 충돌은 프로그래밍에서 매우 중요한 개념으로, 데이터를 효율적으로 관리하고 검색하는 데 필수적입니다. 나눗셈법, 곱셈법, 체이닝, 개방 주소법 등 다양한 해시 함수와 충돌 해결 방법을 통해 다양한 문제를 해결하는 것을 볼 수 있습니다. 해시를 잘 활용하면 성능을 크게 향상시킬 수 있으므로, 적절한 상황에서 해시를 적용하면 좋겠습니다.
부족한 글 읽어 주셔서 감사합니다. 또한 잘못된 내용 있으면 지적해주시면 감사하겠습니다. 🙏

 

하얀종이 개발자

Reference

https://www.appsealing.com/kr/%ED%95%B4%EC%8B%B1-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/ - appsealing 해시함수

https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98 - 위키피디아 해시함수

https://en.wikipedia.org/wiki/Hash_collision - 위키피디아 해시충돌

https://medium.com/shell-tharsis/hash-collision-5891d7dde54f - MINIBEEF 해시충돌

https://www.youtube.com/watch?v=KsfmSyIYX3g - 코딩테스트 합격자되기 c++편 (해시)