C++로 해시 충돌이 발생한 인덱스를 찾는 방법

문제 정의

숫자 p와 n개의 원소를 가진 배열 X가 있다고 가정해 봅시다. 버킷이 p개인 해시 테이블이 있으며, 각 버킷은 0부터 p-1까지 번호가 매겨집니다. 우리는 배열 X에 있는 n개의 숫자를 이 해시 테이블에 삽입하려고 합니다.

X[i]가 들어갈 버킷은 해시 함수 h(X[i])에 의해 결정되며, 여기서 h(k) = k mod p입니다. 하나의 버킷에는 두 개 이상의 원소를 저장할 수 없습니다. 따라서 이미 차 있는 버킷에 새로운 숫자를 삽입하려고 하면 "충돌(collision)"이 발생했다고 합니다.

이 문제에서는 충돌이 발생한 시점의 인덱스를 반환해야 하며, 끝까지 충돌 없이 모든 숫자를 삽입할 수 있다면 -1을 반환하면 됩니다.

예를 들어 입력이 p = 10, X = [0, 21, 53, 41, 53]이라면 출력은 3이 됩니다. 첫 번째 숫자 0은 버킷 0에, 두 번째 숫자 21은 버킷 1에, 세 번째 숫자 53은 버킷 3에 삽입됩니다. 그러나 네 번째 숫자 41 역시 버킷 1(41 mod 10 = 1)에 들어가려다 이미 차 있어 충돌이 발생하므로, 해당 원소의 인덱스인 3을 반환하게 됩니다.

풀이 접근 방식

이 문제는 크기가 p인 별도의 배열을 사용해 각 버킷의 점유 여부를 추적하는 방식으로 해결할 수 있습니다. 전체 알고리즘은 다음과 같습니다.

n := X의 크기
크기가 p인 배열 arr을 선언하고 0으로 초기화
for i := 0 부터 i < n 까지 반복 (i는 1씩 증가):
    x := X[i]
    만약 arr[x mod p]가 0이 아니라면:
        return i
    arr[x mod p] 값을 1 증가
return -1

C++ 구현 예제

더 나은 이해를 위해 아래 구현 예제를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int solve(int p, vector<int> X){
    int n = X.size();
    int arr[p] = { 0 };
    for (int i = 0; i < n; i++){
        int x = X[i];
        if (arr[x % p]){
            return i;
        }
        arr[x % p]++;
    }
    return -1;
}
int main(){
    int p = 10;
    vector<int> X = { 0, 21, 53, 41, 53 };
    cout << solve(p, X) << endl;
}

코드 설명

solve 함수는 먼저 크기가 p인 배열 arr을 0으로 초기화하여 모든 버킷이 비어 있음을 나타냅니다. 이후 배열 X를 순회하면서 각 숫자 x에 대해 x % p 위치의 값이 0이 아니면, 즉 해당 버킷이 이미 사용 중이라면 현재 인덱스 i를 반환합니다. 그렇지 않으면 arr[x % p]를 1 증가시켜 해당 버킷이 사용되었음을 기록합니다. 모든 원소를 충돌 없이 처리하면 -1을 반환합니다.

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(p)입니다.

입력

10, { 0, 21, 53, 41, 53 }