해시 테이블의 개념, 충돌 해결 방법

[bdrsky2010]

• 해시 테이블의 개념, 충돌 해결 방법

[bdrsky2010]

• 해시 테이블의 개념, 충돌 해결 방법

📕 해시의 개념

우리가 살아가고 있는 이 현대 사회는 데이터가 나날히 증가하고 있어 이러한 데이터를 효율적으로 저장하고 탐색하는 과정은 항상 중요한 문제로 이야기 되고있습니다.

어떤 데이터를 찾아야할 때 가장 쉬운방법은 처음부터 끝까지 확인하면서 탐색하는 방법이 있습니다. 가장 확실한 방법일 수 있지만 최악의 경우 모든 데이터를 다 확인하면서 탐색하기 때문에 비효율적입니다.

만약 찾아야하는 값이 어디에 위치하고 있는 지 우리가 알고있다면 즉, 데이터가 저장되는 위치를 규칙으로 정해놓고 해당 위치에 저장한다면 굳이 확인할 필요없이 바로 데이터를 찾을 수 있을 것입니다. 이런 아이디어를 바탕으로 만들어진 자료구조가 바로 'Hash' 입니다.

'Hash'는 Key와 Value의 형태를 갖는 자료구조입니다. 전화번호부랑 동일한 개념을 갖고있으며 검색창에 이름을 입력하면 전화번호 결과가 나오게 되는 것이죠.

이름 = Key, 전화번호 = Value 즉, 무언가를 찾기 위한 검색어 = Key 그 검색어로 나온 결과 = Value

Hash가 없던 시절로 돌아가보면 아래의 문자열 배열 타입의 전화번호를 접근하려면 오직 정수 형태인 인덱스로밖에 접근을 할 수밖에 없습니다.

var phonebook: [String] = ["01012341234", "01023452345", "01034563456"]
phonebook[2]

우리가 친구의 이름을 알고있다고 해서 그 친구의 이름으로 전화번호를 얻을 방법은 없습니다.

var name: String = "minjae"
phonebook[name] // error

해쉬라는 개념이 없던 시절 전화번호를 얻는 유일한 방법은 처음부터 끝까지 하나하나 확인하면서 내가 찾는 이름이 맞는 지 비교를 해줘야했습니다.

struct Person {
    var name: String
    var phone: String
}

var phonebook: [Person] = [Person(name: "minjae", phone: "01012341234")]

for i in 0..<phonebook.count {
    if phonebook[i].name == "minjae" {
        phonebook[i].phone
    }
}

반면 해시를 사용하면, 확인하면서 탐색할 필요 없이 특정 데이터의 위치를 알고 있어 탐색 효율이 좋습니다. 그림에서 해시 테이블(Hash Table)은 키와 대응한 값이 저장되어 있는 공간이며, 해시 테이블의 각 데이터를 버킷(Bucket) 이라고 부릅니다. 그리고 그 사이에는 키를 이용하여 해시값 혹은 인덱스로 변환하는 해시 함수(Hash Function)가 있습니다. 해시 함수는 이런식으로 키를 일정한 해시값으로 변환시켜 값을 찾을 수 있도록 도와줍니다.

📗 해시 함수(Hash Function)

해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시 값(hash value), 매핑하는 과정을 해싱(hashing)이라고 합니다.

[Hash Generator] (https://passwordsgenerator.net/sha256-hash-generator/?source=post_page-----6962be197523--------------------------------) 위의 링크로 들어가보시면 해시 값을 생성해주는 사이트에 접속할 수 있는데 입력값이 바뀔 때마다 해시 값이 바뀌는 것을 확인할 수 있습니다.

해시 함수는 해시 알고리즘 이라고도 불리는데 해시 알고리즘은 종류가 다양하며 알고리즘마다 hash 값의 길이도 다릅니다. 해시 알고리즘은 모두 공개되어 있는데 이 말은 해커들도 볼 수 있어 이미 보안이 뚫린 MD5, SHA-1, HAS-180은 사용하면 안된다고 합니다. SHA-256, SHA-512 등을 사용하기를 권고하고 있으며 2012년에는 안전성이 높은 SHA-3이 발표되었습니다.

📚 해시 함수의 특징

• 입력값이 일부만 변경되어도 전혀 다른 해시 값을 생성한다. (눈사태 효과라고 함)
• 입력값 상관없이 고정된 길이의 해시 값을 생성한다.
• 해시 함수는 단방향 암호화 기법으로 복호화가 불가능하다.
• 복잡하지 않은 알고리즘을 구현되기 때문에 상대적으로 CPU, 메모리 같은 시스템 리소스를 덜 소모한다.
• 값은 입력값에 대해서는 같은 출력 값을 보장한다.
• 특수 목적용으로 해시 값을 생성하는 원본과 별도의 값을 입력받아서 같은 입력에 대해 다른 출력 값을 가지게 하는 해시 함수도 존재한다.

📚 해시 함수를 구현할 때 고려할 내용

1. 해시 함수가 출력한 값은 인덱스로 활용되기 때문에 해시 테이블의 크기를 넘으면 안됩니다. 아래 그림으로 예를 들자면, 해시 함수의 출력값은 해시 테이블의 크기인 0 이상 N - 1 이하의 값을 내야 합니다.

2. 해시 함수가 출력한 값의 충돌은 최대한 적게 발생해야 합니다. 충돌의 의미는 서로 다른 두 키 즉, 입력값에 대해 해싱 함수를 통한 출력값의 결과가 동일한 상황을 의미하는데 아래 그림과 같이 홍길동과 홍길서를 해시 함수에 전달했을 때 둘 다 결과값이 1이면 저장하는 위치가 동일해지기 때문에 충돌이 발생합니다.

총돌이 최대한 적어야 하는 이유는 충돌이 아예 발생하지 않는 해시 함수는 거의 존재하지 않기떄문입니다.

📚 자주 사용하는 해시 함수

🔗 나눗셈법

나눗셈법은 가장 떠올리기 쉬운 단순한 해시 함수입니다. 나눗셈법은 키를 소수로 나눈 나머지를 활용합니다. 이처럼 나머지를 취하는 연산을 모듈러 연산이라고 하며 나눗셈법을 수식으로 작성하면 아래와 같습니다. $$h(x) = x\ mod\ k$$ x는 키(key), m은 소수입니다. 키를 소수로 나눈 나머지를 인덱스로 사용하는겁니다. 나눗셈법을 그림으로 나타내면 아래와 같습니다.

🔖 대체 왜 소수로 나누는 것일까요?

소수를 사용하는 이유는 다른 수를 사용할 때보다 충돌이 적기 때문입니다. 예로 소수가 아닌 15를 나눗셈법에 적용했다고 가정해보겠습니다. x는 3의 배수인 경우를 봤을 때 아래 그림을 보면 규칙적으로 계속 같은 해시 값이 반복되는 것을 볼 수 있습니다. x를 5의 배수로 생각해봐도 충돌이 많이 발생합니다.

🔖 왜 충돌이 많이 발생할까요?

이유는 생각보다 간단합니다. N의 약수 중 하나를 M이라고 해보면 임의의 수 K에 대해 M K = N 이 되는 수가 반드시 존재합니다. 위 그림에서는 N이 15이고, M이 3인 경우인 것이죠. 3 5 = 15 이므로 K = 5 가 됩니다. 그리고 그림은 K를 주기로 같은 해시값이 반복되는 것을 볼 수 있습니다. 따라서, K는 1과 자신만 약수로 같는 소수를 사용하는 것입니다.

🔖 나눗셈법의 해시 테이블 크기는 K

나눗셈법의 해시 테이블 크기는 자연스럽게 K가 됩니다. 이유는, K에 대해 모듈러 연산을 했을 때 나올 수 있는 출력값은 0 ~ (K - 1) 이기 때문입니다. 즉, 상황에 따라 대량의 데이터를 저장해야 한다면 굉장히 큰 소수가 필요할 것입니다. 매우 큰 소수를 구하는 효율적인 방법은 아직 없으며 필요한 경우 기계적인 방식으로 구해야 합니다. 나눗셈법의 단점 중 하나인 것이죠.

🔗 곱셈법

나눗셈법은 상황에 따라 큰 소수를 사용해야 하는데 큰 소수를 구하기가 쉽지 않다는 단점이 있습니다. 곱셈법은 나눗셈법과 비슷하게 모듈러 연산을 활용하지만 소수는 활용되지 않습니다. 곱셈법의 공식은 아래와 같습니다. $$h(x) = (((x A)\ mod\ 1) m)$$ m = 최대 버킷의 갯수 A = 황금비(Golden Ratio Number)

• 황금비는 무한소수로 대략 1.6180339887...이며 황금비의 소수부의 일부인 0.6183만 사용했습니다.

황금비는 수학적으로 임의의 길이를 두 부분으로 나누었을 때, 전체와 긴 부분의 비율이 긴 부분과 짧은 부분의 비율이 같은 비율을 뜻합니다.

1️⃣ 키에 황금비를 곱합니다

2️⃣ 1에서 구한 값의 모듈러 1 연산을 해줍니다. 쉽게 말해 정수 부분을 제외한 소수점 아래 부분만 갖고가는거죠.

3️⃣ '2'에서 구한 값을 가지고 실제 해시 테이블에 매핑합니다. 테이블의 크기가 m이면 '2'에서 구한 수에 m을 고합 훈 정수 부분을 갖고가는 연산을 통해 해시 테이블에 매핑할 수 있습니다. '2'에서 구했던 값은 0.xxx의 값이므로 매핑할 테이블의 크기인 m을 고합하면 테이블의 인덱스인 0 ~ (m - 1)에 매치할 수 있습니다.

이처럼 곱셈법은 황금비를 사용하여 소수가 필요 없다는 장점이 있습니다. 따라서 해시 테이블의 크기가 커져도 추가 작업이 필요 없는 것이지요.

🔗 문자열 해싱

지금까지 알아본 해시 함수는 키의 자료형이 숫자였습니다. 키의 자료형이 문자열일 때도 사용할 수 있는 해시 함수인 문자열 해싱도 알아보겠습니다. 문자열 해싱은 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱하며 공식은 아래와 같습니다. 아래 함수는 문자열 해싱을 하기 위해 사용하는 'polynomial rolling method' 라고 합니다.

p = 31 m = 해시 테이블 최대 크기

p를 31로 정한 이유는 홀수이면서 메르센 소수이기 때문입니다. 메르센 소수는 일반적으로 2N - 1 형식으로 표시할 수 있는 숫자 중 소수인 수를 말합니다. 메르센 소수는 해시에서 충돌을 줄이는데 효과적이라는 연구 결과가 있습니다.

$$hash(s) = (s[0] + s[1] p + s[2] p^2 ...\ s[n - 1] * p^{n-1})\ mod\ m$$ 1️⃣ 아래 그림은 알파벳 a부터 z까지 숫자와 매치한 표와 키입니다.

2️⃣ "a"는 매치 표를 보면 1입니다. 따라서 "apple"의 "a"는 1입니다. 그러므로 수식의 s[0]은 1이 됩니다.

3️⃣ 두 번째 문자 "p"에 대해 연산을 진행합니다. "p"는 16입니다. 여기에 p를 곱하면 16 * 31 = 496이 됩니다.

4️⃣ 이렇게 곱한 값들을 더하면 최종값은 4,990,970이 됩니다. 이를 해시 테이블의 크기 m으로 모듈러 연산하여 활용하면 됩니다.

기존에는 키 자체가 숫자였기 때문에 바로 해시 함수를 적용했지만 키가 문자열인 경우 각 문자들을 적절한 숫자로 변환 후 해시 함수를 적용해야 합니다. 이런 변환 과정을 통해 문자열이 키인 데이터도 해시를 사용할 수 있습니다. 하지만 해시 함수를 적용해야하는 값이 해시 테이블 크기에 비해 너무 큰 경우 문제가 생길 수 있습니다. 위 그림의 경우 "apple"이라는 간단 문자열을 해싱했는데도 결과값은 4,990,970으로 굉장히 큰 값이 출력되는데 이러한 경우 오버플로우를 발생시킬 여지가 있어 아래 연산 법칙을 활용하여 문자열 해시 함수를 수정할 수 있습니다.

덧셈 연산을 모두 수행한 후 모듈러 연산을 하는 것보다는 덧셈이 이뤄지는 중간 중간 모듈러 연산을 해 더한 값을 모듈러 연산하면 오버플로우를 최대한 방지할 수 있습니다.

이를 바탕으로 문자열 해싱 공식을 수정하면 아래와 같습니다. $$hash(s) = (\ (s[0] \ mod\ m) + (s[1] p \ mod\ m) + (s[2] p^2 \ mod\ m) ...\ (s[n - 1] * p^{n-1} \ mod\ m) )\ mod\ m$$ 해시 함수뿐만 아니라 보통 수식에 모듈러 연산이 있는 문제 중 큰 수를 다루는 문제는 이런 오버플로우 함정이 있는 경우가 많기 때문에 기억해두면 좋습니다.

📘 충돌 처리

서로 다른 키에 대해서 해시 함수의 출력값이 동일하면 충돌(Collision)이 일어나게됩니다. 하나의 버킷에 2개 이상의 데이터를 적재할 수는 없으므로 해시 테이블을 관리할 때는 반드리 충돌에 대한 처리를 해줘야 합니다.

위 그림을 보면 두 키의 값은 서로 다르지만 해시 함수를 통과해 해시값이 17이 나왔습니다. 이렇게되면 해시 테이블의 같은 인덱스를 가리키기 때문에 충돌이 발생하게 됩니다. 이런 충돌이 발생하면 어떻게 처리를 해야할까요?

📚 체이닝

체이닝은 해시 테이블에 해싱값이 충돌이 일어난 경우 해결하는 간단한 방법입니다. 체이닝은 충돌이 발생하면 해당 버킷에 연결리스트로 같은 해시값을 가지는 데이터를 연결합니다.

위 그림을 보면 B와 C의 해싱값으로 3이 출력됐습니다. 즉, 해시 테이블의 같은 위치를 가리켜 데이터를 저장하려는 순간 충돌이 발생합니다. 이 때 체이닝은 연결리스트로 충돌한 데이터를 연결 연결하는 방식으로 해결합니다. 이처럼 체이닝은 충돌을 연결리스트로 간단하게 해결할 수 있다는 장점이 있지만 단점도 존재합니다.

🔖 해시 테이블 공간 활용성이 떨어진다

충돌이 많이 발생하게되면 그만큼 연결리스트의 길이가 길어지고, 다른 해시 테이블의 공간은 덜 사용하므로 공간 활용성이 떨어지게 됩니다.

🔖 검색 성능이 떨어진다

충돌이 많이 발생하게되면 연결리스트의 단점 때문에 검색 성능이 떨어집니다. 연결리스트로 연결된 값을 찾아야 할 경우 연결리스트의 head부터 순차적으로 탐색하기 때문입니다. 아래 그림을 보면 맨 뒤 K에 해당하는 키에 대한 값을 찾기 위해서는 B, C, K를 거쳐 확인해야합니다. 만약 N개의 키가 있고 모든 키가 충돌하여 체이닝됐다면 마지막 버킷을 검색하는 경우 시간 복잡도는 O(N)입니다.

📚 개방 주소법(Open Addressing)

개방 주소법은 충돌이 발생한 경우 빈 버킷을 찾아 충돌이 발생한 해싱값을 해당 위치에 적재합니다. 이 방법은 해시 테이블의 공간을 최대한 활용하므로 체이닝보다 공간을 더 효율적으로 사용합니다.

🔗 선형 탐사 방식(Linear Probing)

선형 탐사 방식은 충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동합니다. 수식은 아래와 같습니다.

보통 간격은 1로 하는 것이 일반적입니다.

m = 수용할 수 있는 최대 버킷 수 선형 탐사 시 테이블의 범위를 넘으면 안되기에 모듈러 연산을 적용합니다 $$h(\ k, i \ ) = (\ h(\ k \ ) + i \ )\ mod\ m$$

키 5에 해시 함수를 적용하면 값 2가 있는 위치를 가리켜 충돌이 발생하지만 선형 탐사 방식으로 1칸씩 아래로 내려갑니다. 값 3, 값 4를 지나 그 다음 위치에 값 5를 적재합니다. 하지만 이 방식도 단점이 존재합니다. 충돌 발생 시 1칸씩 이동하며 해시 테이블의 빈 위치에 값을 적재하면 충돌이 발생한 해시값끼리 모이는 영역이 생기는 현상이 일어나는데 이를 클러스터가 형성된다고 합니다. 이런 군집이 생기면 해시값은 충돌이 일어날 확률이 더 올라갑니다.

그래서 이를 방지하기 위해 제곱수만큼 이동하며 탐사하는 방식도 있습니다.

🔗 이중 해싱 방식

이중 해싱 방식은 말 그대로 해시 함수를 2개 사용하는 것입니다. 때에 따라 해시 함수를 N개로 늘리기도 합니다. 두 번째 해시 함수의 역할은 첫 번째 해시 함수를 통해 충돌이 발생하면 해당 위치를 기준으로 어떻게 위치를 정할지 결정하는 역할을 합니다. 예를 들어 h1이 1차 해시 함수, h2가 2차 해시 함수입니다. $$h(\ k, i\ ) = (\ h_1(k) + i \ *\ h_2(k)\ )\ mod\ m$$ 수식을 보면 선형 탐사와 비슷하게 더하는 방식으로 데이터의 위치를 정하지만 클러스터를 줄이기 위해 m을 제곱수로 하거나 소수로 합니다. 이는 주어지는 키마다 이동하는 위치를 해시 함수로 다르게 해서 클러스터 형성을 최대한 피하기 위함입니다.

참고 [해시 Hash 알고리즘 설명 5분만에 이해하기] https://youtu.be/zFL29ydL9D8?si=-nFUS_k9AGtgnJMw [해시의 개념] https://goldenrabbit.co.kr/2023/11/29/%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%95%A9%EA%B2%A9%EC%9E%90-%EB%90%98%EA%B8%B0-%ED%95%B4%EC%8B%9C-1-%ED%95%B4%EC%8B%9C%EC%9D%98-%EA%B0%9C%EB%85%90/ [해시(hash)란?] https://ru-magazine.tistory.com/47 [(Crypto) 해시(hash)란?] https://medium.com/@su_bak/crypto-%ED%95%B4%EC%8B%9C-hash-%EB%9E%80-6962be197523 [해시 함수와 충돌 처리] https://goldenrabbit.co.kr/2023/12/01/%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%95%A9%EA%B2%A9%EC%9E%90-%EB%90%98%EA%B8%B0-%ED%95%B4%EC%8B%9C-2-%ED%95%B4%EC%8B%9C-%ED%95%A8%EC%88%98%EC%99%80-%EC%B6%A9%EB%8F%8C-%EC%B2%98/