Python 랜덤 해시를 이용한 해시 충돌 피하기

1. python dict의 내부 구현 원리 간단하게

 

Python에서 dict {key:value}는 내부적으로 2가지 배열을 가지고 구현된다

 

indices : 어떤 위치에 데이터가 있는지 인덱스만 기록

 

entries: 데이터가 들어온 순서대로 [해시값, key, value]를 저장

 

초기 상태는 보통 8칸으로 시작하고, 

 

indices = [-1,-1,-1,-1,-1,-1,-1,-1]

 

entries = []

 

만약 {} 빈 dict에 {10:3}으로 저장한다면...?

 

key의 hash값을 계산하고 배열 크기로 나눈 나머지를 구한다.

 

10의 hash는 10이고, 이를 8로 나눈 나머지 2를 구해 indices의 2번 칸에 넣는다.

 

indices = [-1,-1,0,-1,-1,-1,-1,-1]

 

그리고 entries에는 [10,10,3]으로 넣어주면 entries = [[10,3,3]]

 

여기서 h[10]의 value를 찾으려고 한다면? key인 10의 hash값을 계산해서 hash(10) mod 8 = 2라는것을 알고,

 

indices의 2번칸인 0을 구한 다음, entries의 0번 원소인 [10,10,3]을 가져온다.

 

여기서 value는 3이니까 value = 3이라고 바로 답을 낸다.

 

 

2. 우연히 똑같은 위치로 계산된다면...

 

어떤 key:value를 저장하는데, 우연히도 hash(key) mod (크기) 계산값이 똑같을 수 있다

 

계산했는데, indices배열의 값이 -1이 아니면 충돌로 생각하고...

 

일단 그 위치의 entries로 들어간 다음, key가 같은 값이라면 value를 바꿔주고

 

key가 다르다면, 새로운 위치를 계산해야한다.

 

 

이때 새로운 위치를 계산하는 방법은 open addressing(개방 주소법)의 선형 탐사법을 이용하는데

 

단순히 1칸 다음이 아니라 파이썬에서는 자체적으로 계산하는 특수한 공식을 이용한다고 함

 

(다음위치) = (5*(현재위치) + 1 + perturb) (mod 배열크기)

 

이 공식은 배열의 크기가 2의 거듭제곱일때, 배열의 모든 칸을 중복없이 한번씩 순회하여 찾을 수 있다는 것이 증명되어있다.

 

 

perturb는 key의 hash값인데, 충돌날때마다 새롭게 5비트씩 깎아내리는 특수한 계산값이다.

 

 

대충 {10:3}에서 indices = [-1,-1,0,-1,-1,-1,-1,-1], entries = [[10,10,3]]일때, 10: 5를 저장한다고 생각해보자.

 

10의 hash는 10이고, 10 mod 8 = 2이기 때문에, indices의 2번 자리에 본다.

 

이때, 0번이 있고 -1이 아니기 때문에 entries의 0번에 가본다.

 

0번의 [10,10,3]에서 key = 10이고 현재 저장하려는 key와 같으므로 value를 갱신해서  [[10,10,5]]로 업데이트 해준다.

 

 

그렇다면 18:99를 저장한다고 해보자.

 

18의 hash는 18이고, 18 mod 8 = 2이므로, indices의 2번 자리를 본다.

 

역시 0번이 있고, -1이 아니기 때문에 entries의 0번에 간다.

 

0번의 [10,10,5]에서 key = 10으로 저장하려는 key = 18이므로 달라서, 충돌이 일어났다.

 

그래서 다른 위치에 저장해야한다. 이때, 초기 perturb = 18이고, 현재 위치 = 2이므로 계산 공식에 따라 다음 위치는...

 

(다음 위치) = (5*2 + 1 + 18) mod 8 = 29 mod 8 = 5

 

5번 위치로 간다.

 

5번 위치는 -1이므로 -1에 1을 저장해둔다. [-1,-1,0,-1,-1,1,1,1]

 

그리고 entries에 [18,18,99]를 새롭게 추가하면 끝

 

 

 

3. 너무 많은 수가 들어간다면...

 

초기에 8칸으로 시작하니 당연히 8개보다 많은 수가 들어간다면... 들어갈 자리가 없다.

 

그래서 Python은 적재율을 계산하고 2/3정도의 적재율에 도달하면 자동으로 배열의 크기를 확장하고,

 

배열의 크기가 커졌으니 숫자들의 자리를 다시 계산하는 과정을 거친다.

 

이때 배열의 크기는 2의 거듭제곱을 유지한다.

 

원래 8칸이면, 확장하면 16칸, 그 이후 32칸,.... 이런 식으로

 

배열의 크기가 달라지면, {10:3}에서 원래 10은 indices의 2번칸에 저장되어있는데, 

 

이는 hash(10) mod 8 = 2이기 때문이고, 16칸이 된다면... 16으로 나눈 나머지를 구해야하므로

 

hash(10) mod 16 = 10이므로 10번째 칸에 재배치한다.

 

이때 entries는 여전히 그대로다...

 

왜냐하면 [-1,-1,0,-1,-1,-1,-1,-1]이 [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,-1,-1,-1,-1,-1]로 저장된거라...

 

entries의 0번에 있다는건 그대로니까 

 

이때, 배열의 확장은 생각보다 자주 일어나지 않고, 전체적으로는 결국 O(1)의 효율이 나도록 설계되어있다고 함

 

 

 

4. 랜덤 해시 테크닉

 

문자열 같은 경우는 내부적으로 복잡하게 hash가 구현되어 있다. 그래서 보통은 해시충돌이 일어나지 않음

 

다만 정수는 기본적으로 hash(x) = x로 아주 간단하게 구현되어 있다.

 

그리고 해시 충돌이 일어나면 어디로 탐사할지 5*i + 1 + p 공식도 이미 알려져있다.

 

따라서, 악의적으로? 데이터를 만들면 데이터를 저장할때마다 해시 충돌이 계속해서 일어나게 구성할 수 있으며,

 

따라서 dict의 탐색 효율은 최악의 경우인 O(N)으로 만들 수 있다.

 

 

그래서 정수를 저장할때, 랜덤값을 xor하여 저장한다면 이를 피할 수 있다.

 

이때 XOR은 똑같은 수를 XOR하면 원래 수로 복원할 수 있는 성질도 있다.

 

즉, x ^ (random) ^ (random) = x이다.

 

random하게 아무 값을 미리 생성해두고, x를 저장할때, x^(random)을 저장해둔다면 hash(x^(random)) = x^(random)

 

이므로, x값은 알면서도 x에 대한 해시를 랜덤한 함수로 바꿀수 있는 효과가 있다.

 

import random

# 1. 64비트의 아주 큰 난수를 하나 생성합니다. (프로그램 실행 시마다 바뀜)
RANDOM = random.getrandbits(64)

H = {}
x = 10  # 딕셔너리에 넣고 싶은 키

# 2. 키를 넣거나 찾을 때, 원래 숫자 x 대신 x ^ RANDOM 을 사용합니다.
H[x ^ RANDOM] = H.get(x ^ RANDOM, 0) + 1

# 3. 값을 꺼낼 때도 마찬가지로 난수를 XOR해서 찾습니다.
count = H.get(x ^ RANDOM, 0)