해시(Hash) 개념 정리(Feat. 파이썬 알고리즘 인터뷰)

오늘부로 정글이 끝났다. 소회글도 한 번 적었어야 했는데, 여기에 개발 글 외에 다른 글을 쓰기가 부담스러워지는 바람에...나중에 회사 합격하고 한 번에 쓰는 걸로 할 예정이다. 당분간은 딴소리 없이 공부 관련 내용만 올릴 생각! 바로 가보자.

 

--

 

알고리즘 공부를 다시 시작하면서 프로그래머스 고득점 kit을 풀기 시작했다. 가장 먼저 나오는 단원인 해시부터 호기롭게 시작했건만 Level 2부터 턱 막혀버리는..게 아닌가. 그래서 내리 연달아 2문제를 공부하고 나서 관련 개념을 정리했다.

 

해시(Hash table)

Hash table: key를 value에 매핑하는 array 형태의 자료구조

우리가 흔히 해시라고 부르는 자료구조는 엄밀히 말하면 해시 테이블(Hash table), 또는 해시 맵(Hash map)을 뜻한다. 여기서 hash는 해시 함수를 말한다. 해시 함수의 정의 역시 살펴보자.

 

Hash function: 임의 길이 데이터(input)를 암호화된 고정 길이(output)의 데이터로 매핑(전환)하는 함수

 

근데 뭔가 이상하다. 해시 테이블과 해시 함수가 그래서 어떤 연관이 있다는 건가? 그림으로 살펴보자.

 

 

 

보통 많이 나오는 그림은 오른쪽인데, 저것만 보면 좀 헷갈릴 수 있다.

 

먼저 왼쪽 그림부터 보자. 사람 이름이 key로 들어가 있다. 이 key에 해당하는 임의 길이의 string을 hash 함수에 input으로 넣으면 01, 02, 04, ...와 같이 "고정된 길이의 int 데이터"로 변환되는 것을 볼 수 있다. 여기까지가 hash function의 역할이다. 위에서 말했던 '임의 길이 데이터를 암호화된 고정 길이 데이터로 전환하는 함수'인 것.

 

다시 오른쪽 그림을 보자. buckets라고 하는 칸에는 key인 사람의 전화번호가 들어있다. 해시 테이블에서 bucket은 key에 대응하는 데이터이다. 여기서 착각하면 안되는 게, 이 bucket에 들어가는 데이터는 hash function과는 아무런 상관이 없다는 점. 그냥 원래 우리가 배열에 넣고 싶었던 데이터다. 따라서 뭔가 변환하고 이런 것 없이 그냥 곧장 넣는다.

 

즉, key값을 hash func에 넣어 얻은 hash value를 배열의 인덱스로 쓰는 테이블을 우리는 hash table이라고 하는 것. 그런 면에서 보다 이해하기 쉬운 해시 테이블의 정의는 아래와 같겠다.

 

Hash table: key를 hash function에 넣어 얻은 hashes를 index로 value 데이터와 매핑하는 array(table) 형태의 자료구조

즉, [key] -> [hash func] ->  [hash(==h(key))] - [value(in bucket)] 라는 네 단계를 거치는 것.

 

특징

 

연산의 (평균)시간복잡도가 O(1)으로, 매우 빠르게 값을 찾아낼 수 있다.

여기서 질문. 어떻게 평균 시간 복잡도가 O(1)이 나올 수 있을까? 해시 테이블에 우리가 입력한 key에 대응하는 bucket을 찾는 과정을 살펴보자. 예전에 핀토스 공부하던 중에 정리해둔 해시 테이블 내용을 살펴보면

 

1) 해시 함수에 key를 입력해 해시 값을 받아내는 과정([key] -> [hash func] ->  [hash==h(key)]):  O(1)

 

해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 해싱(Hashing)이라고 한다. 가장 단순한 해싱 알고리즘 하나로 정수형 해싱 기법인 모듈러를 예시로 들어보자. 모듈러 함수는 나머지를 연산하는데 이로부터 해싱 인덱스를 뽑아낸다. 예를 들어 John Doe를 해싱 함수에 넣는다고 하자. 먼저, 이 John Doe를 함수 내부적으로 정한 규칙에 따라 정수로 바꾼다. 그 다음, 역시 내부적으로 정한 특정 값(보통 2의 멱수에 가깝지 않은 소수)으로 이 수를 나눈 나머지를 구한다. 이 나머지 값이 hash index가 되는 것.

 

이 과정은 그냥 나머지 연산만 하면 되므로 시간복잡도가 O(1)이다.

 

2) 테이블에서 해당 인덱스로 이동하는데 걸리는 시간: O(1)

array의 가장 큰 장점 중 하나는 특정 인덱스를 찾는데 걸리는 시간이 O(1)이라는 점이다. 예를 들어 우리가 14번째 bucket을 찾는다고 하자. 그러면 그냥 00번째 인덱스에 +14만 해주면 된다. 게다가 위의 1)에서 key와 hash index는 대응하므로 hash 연산만 돌리면 곧바로 bucket의 인덱스를 찾아낼 수 있다. 그러니 전체적으로 해시 테이블에서 bucket 데이터를 찾는데 걸리는 시간이 O(1)인 것.

 

이와 동일한 로직으로 찾거나(search), 데이터를 삽입하거나(insert), 지울 때(delete) 걸리는 평균 시간복잡도는 O(1)이 된다. 공간이야 array 형태니까 데이터 수에 비례하는 O(n)이다. 그런데 잠시만, 왜 search/insert/delete의 worst case가 O(n)일까? 저렇게 완벽한 로직을 가졌는데?

 

 

 

충돌(Hash collision)

이를 알기 위해서는 '충돌(collision)' 개념을 알아야 한다.

충돌이란? 서로 다른 key에 대해 동일한 hash값(index)가 부여되는 상황

 

충돌 개념 자체는 다른 곳에도 많이 소개되어 있으니 여기서는 충돌 발생 해결책에 대해서만 다룬다.

 

충돌 발생 해결책 1: Seperate Chaining(개별 체이닝)

충돌 발생 시 동일한 key에 다른 value를 연결리스트로 연결해 충돌을 해결하는 방법

 

 

 

가장 일반적인 충돌 해결 방식. 보통 해시 테이블이라 하면 이 형태를 뜻한다. 이를 구현하는 방식은 아래와 같다.

 

1. 키의 해시 값을 계산한다.

2. 해시 값을 이용해 배열의 인덱스를 구한다.

3. 만약 같은 인덱스가 있다면 연결 리스트로 연결한다.

 

아까 위에서 search/insert/delete에 걸리는 평균 시간복잡도는 O(1)이라고 했다. 이는 위의 그림과 같이 하나의 인덱스에 여러 개의 데이터가 연결리스트로 달려있지 않고 값이 고르게 분산되었을 경우에 해당한다.

 

그러면 O(n)이 나올 때는? 극단적으로, 위의 그림에서 모든 데이터가 0번 인덱스에 줄줄이 소세지 마냥 연결리스트로 연결되었다고 생각해보자. 이 경우, 연결 리스트 내에서는 O(N)으로 하나하나 체크해가며 값을 찾아내야 한다. 그러니 최악의 케이스에는 O(n)이 나오는 것.

 

여기서 재밌는 점 하나. 자바 8에서는 이 연결리스트 구조를 RB 트리 형태로 설계함으로써 더욱 최적화했다고 한다.

 

RB트리 복습할 겸 정리해보자. 연결 리스트를 linked list가 아닌 RB트리 형태로 구현하면 어떤 장점이 있을까? 바로 탐색/삽입/삭제에 걸리는 최악의 시간복잡도가 O(n)에서 O(logN)으로 급격히 줄어든다는 점이다. 왜 그럴까?

 

RB트리는 기본적으로 이진 검색 트리에 해당한다. 그런데 일반적인 이진 검색 트리는 노드 자신을 기준으로 자기보다 작은 값은 왼쪽 자식 노드에, 자기보다 큰 값은 오른쪽 자식 노드에 배치한다. 그러다보면 트리가 균형을 잃고 한쪽으로 쏠릴 수 있다. 마치 위의 해시 테이블 내 연결 리스트마냥, 일반적으로 탐색시 O(logN)의 시간복잡도를 가지는데 최악의 경우 O(n)이 되어버리는 셈. 

 

 

 

RB트리는 균형을 이루도록 고안된 검색 트리 구조이다. 최선, 최악 모두 항상 O(logN)의 시간복잡도를 보장한다. 어떻게 이를 구현할 수 있을까? 레드블랙 트리는 각 노드 당 1비트의 추가 기억 공간을 갖는다. 이 1비트에는 적색(Red) 혹은 흑색(Black)과 같이 노드 색상 정보가 들어있다. 색을 부여하는 이유는, 레드블랙 트리는 루트에서 리프까지의 경로에 나타나는 노드의 색을 제한함으로써 어떤 경로도 다른 것보다 두 배 이상 길지 않도록 보장하기 위함이다. 이런 규칙 덕분에 레드블랙 트리는 근사적으로 균형을 이룬 트리가 되는 것.

 

따라서 개별 체이닝에 줄줄이 달린 연결 리스트 구조를 RB트리 형태로 바꾸면 평균 시간복잡도는 O(1), 최악의 시간복잡도는 O(logN)이 되는 셈이다.

 

충돌 발생 해결책 2: Open Addressing(오픈 어드레싱)

충돌 발생 시 테이블 공간을 탐사해 빈 공간을 찾아나서는 방식

 

위의 개별 체이닝 방식은 버킷의 크기에 관계없이 연결리스트에 데이터를 줄줄이 달아놓음으로써 무한정 저장할 수 있는 반면(물론 해싱 효율은 많이 떨어진다. O(1)을 보장받기 힘들어지니까) 오픈 어드레싱 방식은 전체 테이블 내 슬롯 개수 이상은 저장이 불가능하다. 만약 인덱스가 겹치면 다른 빈 공간에 가서 데이터를 채워넣는 식이니, 모든 공간에 데이터가 차면 넣을 수 없을 테니까.

 

이 방식은 충돌이 일어나면 다른 테이블 공간을 탐사해 빈 공간을 찾고 거기에 데이터를 집어넣음으로써 해결한다. 물론 이때 넣는 위치의 인덱스는 원래 key를 해시 함수에 넣어 얻은 인덱스와 다르다. 따라서 개별 체이닝과 달리 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없다.

 

오픈 어드레싱을 구현하는 대표적인 방식은 선형 탐사(Linear probing)이다. 위의 그림이 선형 탐사를 보여주는 예시이다. 선형 탐사는 "충돌이 발생하면 해당 위치부터 순차적으로 탐사를 하나씩 진행"한다. 만약 특정 위치에 이미 값이 선점되었다면 바로 그 다음 위치를 확인한다. 그렇게 한 칸씩 이동하며 선형적으로 찾다가 빈 공간을 발견하면 그 자리에 삽입한다. 비효율적일 것 같지만 구현이 간단하면서도 전체적인 성능은 좋은 편으로 알려져 있다.

 

하지만 오픈 어드레싱 방식 역시 문제점이 존재하는데, 바로 클러스터링(clustering)이다. 클러스터링이란, 해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 현상을 뜻한다. 뭉치는 게 왜 문제일까? 클러스터가 점점 커지면 근처에 있는 클러스터와 서로 합치는 일이 일어나는데, 이러면 해시 테이블에 데이터가 한쪽으로 편중되고 다른 쪽에는 데이터가 거의 없다. 이렇게 클러스터링 현상이 생기면 탐사 시간이 오래 걸린다. linear probing 방식으로 데이터를 삽입하면 해당 키에 접근한다고 해서 한 번 만에 우리가 원하는 데이터를 찾을 수 없다. 해당 키에 대응하는 데이터를 기준으로 선형적으로 한 칸씩 내려오면서 쭉 찾아야 하는데, 이 과정이 길어질수록 해싱 효율이 떨어진다. 그런데 클러스터링은 한 곳에 많은 데이터가 뭉치게 되니 탐사하면서 내려오는 길이 역시 길어질 수밖에 없다. 이것이 클러스터링의 문제점이다.

 

이 오픈 어드레싱 방식은 버킷 사이즈보다 큰 경우에는 데이터를 삽입할 수 없다. 오픈 어드레싱은 무조건 빈 버킷에 데이터를 하나씩만 삽입하는 방식이기 때문이다. 따라서 기준이 되는 로드 팩터* 비율을 넘어서면 정해놓은 비율에 따라 더 큰 크기의 또 다른 버킷을 생성한 뒤 새 버킷에 복사하는 리해싱(Rehashing) 작업이 일어난다.

 

언어별 해시 테이블 구현 방식

 

파이썬에서는 자료구조 중 딕셔너리가 해시 테이블로 구성되어 있다. 그러면 파이썬의 해시 테이블은 충돌 시 어떤 방식으로 해결할까? 보편적인 방법이 개별 체이닝이라고 했으나 파이썬에서는 오픈 어드레싱으로 해결한다. 왜일까? 파이썬 코드 주석을 보면 이렇게 나와있다.

 

CPython에서 체이닝으로 구현할 시 malloc으로 메모리를 할당하는 오버헤드가 높아 오픈 어드레싱을 택했다.

이게 무슨 말이냐, 체이닝을 구현하려면 충돌이 발생할 때마다 연결 리스트를 만들어줘야 한다. 이를 위해서는 그때마다 추가로 메모리 할당(malloc)이 필요하다. 근데 CPython에너는 추가 메모리 할당이 상대적으로 느린 작업이라 택하지 않았다고 한다. 음.. 잘 이해가 안되는데.. 추가로 Python에서 memory management를 어떻게 하는지 나중에 따로 파봐야 할듯.

 

 

언어	방식
C++	개별 체이닝
자바	개별 체이닝
고(Golang)	개별 체이닝
루비	오픈 어드레싱
파이썬	오픈 어드레싱