Algorithm & Data Structure (5) - Hashing Table

kimseyoung·2023년 1월 24일

ComputerScience

목록 보기

6/8

해시 테이블

대부분의 프로그래밍 언어는 해시 테이블(Hash Table)이라는 자료구조를 포함한다. 해시 테이블에는 빠른 읽기라는 놀랍고 엄청난 능력이 있다. 해시 테이블은 다양한 프로그래밍 언어에서 서로 다른 이름으로 불린다. 해시, 맵, 해시 맵, 딕셔너리, 연관 배열 등의 이름을 갖는다.

파이썬의 딕셔너리가 해시 테이블의 대표적인 예이다.

# Dictionary

dict = {"key1" : value1, "key2" : value2, ...}

자바에서는 맵 인터페이스, 해시맵 객체가 존재한다.

해시 테이블은 쌍으로 이뤄진 값들의 리스트다. 첫 번째 항목을 키(key)라고 부르고, 두번째 항목을 값(value)라고 부른다. 해시 테이블에서 키와 값은 서로 중요한 관계다. 키를 이용해 값에 접근하는 방법은 다음과 같다. (파이썬 예제)

dict["key1"]

>> value1

해시 함수

ASCII코드는 각 문자열에 대응하는 정수값을 가지고있다. 해시 함수도 동일하다. 하지만, 해시는 대응하는 정수값이 아닌, 해시함수를 통하여 대응시킨다. 예를 들어, 다음과 같은 해시 함수가 존재한다.

A = 1
B = 2
C = 3
D = 4
.
.

이러한 대응 코드를 가지고 BAD를 해싱(Hashing) 시키면 다음과 같은 결과를 낼 것이다. 이를 전부 더하여 결과를 내보낸다.

BAD ===> f(x)(Hash Function) ====> 214 ====> 2 + 1 + 4 ====> 7

또는, 모든 수를 곱하여 결과를 내보낸다.

BAD ===> 2 1 4 ===> 8

이러한 과정을 해싱(Hashing) 이라고 한다. 해시 함수는 유효하기 위해 딱 한 가지 기준을 충족해야하는데, 바로, 동일한 문자열을 해시 함수에 적용할 때 마다. 동일한 숫자로 항상 반환해야한다.

예를 들어, 난수나 현재 시간을 계산에 넣어 사용하는 해시 함수는 유효하지 않다. 이러한 함수를 사용하면, BAD가 한 번은 12로, 다른 한 번은 106으로 변환될 수 있다.

하지만 위의 "곱셈" 해시 함수를 쓰면 BAD는 항상 8로 변환된다. B는 항상 2고, A는 항상 1이고, D는 항상 4이기 때문이다. 다른 결과는 있을 수 없다.

하지만, DAB 역시 8이 된다. 이로 인해 실제로 해시 테이블은 문제가 발생한다. 차 후 이 문제에 대해서 설명한다.

해시 테이블 룩업(LookUp)

해시테이블에서 간단하게 "BAD"에 저장된 값을 불러온다고 생각해보자, 다음과 같이 간단한 과정을 거쳐 O(1)의 상수 시간 복잡도로 룩업이 가능하다.

BAD를 해싱한다.
인덱스 8 에 대응하는 값을 반환한다.

해시 테이블은 무조건 룩업에 대해 O(1)밖에 안되는 상수 시간 복잡도를 가진다. 매우 빠르다고 할 수 있다. 다른 이 전의 다른 룩업에 대해 생각해보자, 모두 O(N) 또는 O(logN)의 더 나아가 O(N^2)의 복잡도를 가지고 있었다. 이러한 빠른 룩업이 해시 테이블의 가장 큰 장점이다.

단방향(one-directional) 룩업

해시 테이블에서 한 단계 만에 값을 찾는 기능은 그 값의 키를 알 때만 가능하다는 점에 주목하자. 키를 모른 채 값을 찾으려면 해시 테이블 내 모든 키/값 쌍을 검색하는 수밖에 없고 이는 O(N)의 복잡도를 가진다.

거꾸로, 값을 이용해 키를 O(1)의 단순한 룩업을 활용 할 수 없다. 이는 키가 값의 위치를 결정한다는 해시 테이블의 대전제 때문이다. 하지만 이 전제는 한 방향으로만, 다시 말해 키를 사용해 값을 찾는 식으로만 동작한다. 값으로는 키의 위치를 알아내지 못하니 전부 훑는 것 이외에는 키를 쉽게 찾을 방법이 없다.

그렇다면, 키는 어디에 저장되는가? 앞선 설명은 값이 해시 테이블에 어떻게 저장되고, 룩업되는지만 설명한다. 세부적으로는 언어에 따라 다르지만, 어떤 언어는 값 바로 옆에 키를 저장한다. 이렇게 저장하면, 위에서 언급한 중복된 인덱스 값에 대한 충돌을 해결 가능하다.

충돌 해결

위에서 언급했다 싶이, BAD라는 문자열을 해싱한 결과와 DAB 문자열을 해싱한 결과는 동일한 충돌이 발생한다. 이러한 충돌을 해결하는 방법에 대해 설명하고자 한다.

분리 연결법(Separate Chaining)

분리 연결법이란, 충돌이 발생했을 때 셀에 하나의 값을 넣는 대신 배열로의 참조를 넣는 방법이다.

	"taxi"		"evil"
5	6	7	8	9

위와 같은 자료가 저장되어 있는 해시 테이블이 있다, 이 때, 8번 인덱스에 "pat" 문자열을 추가하려 하지만, 이미 evil이 있다. 따라서 인덱스 8을 다음과 같은 배열로 대체한다.

	"taxi"		["bad","evil"],["dab","pat"]
5	6	7	8	9

이러한 분리 연결법이 적용된 해시 테이블에서 룩업이 어떻게 작용하는지 알아보자.

키 값을 해싱 (DAB ==> 8)
해싱 된 키값에 맞는 8번 인덱스를 룩업한다. 이 때, 단순 값이 아닌 배열들의 배열을 포함 하고 있음을 인지한다.
각 하위 배열의 인데스 0을 찾아보며 룩업하고 있는 단어인 ("dab")를 찾을 때 까지 배열을 순회 조회한다. 일치하는 하위 인덱스 값을 반환한다.

즉, 최악의 상황의 경우 이 분리 연결법은 O(N)의 시간 복잡도를 가지게 되어, 해시 테이블의 장점을 활용하기 어려워 진다. 그럼, 어떻게 해야 O(1)의 복잡도를 유지하게 할 것인가.

효율적인 해시 테이블 만들기

궁극적으로 해시 테이블은 다음 세 요인에 따라 효율성이 정해진다.

해시 테이블에 얼마나 많은 데이터를 저장하는가.
해시 테이블에서 얼마나 많은 셀을 쓸 수 있는가.
어떤 해시 함수를 사용하는가.

처음 두 요인이 중요한 까닭은 직관적으로 와닿을 것이다. 세번째, 해시 함수의 종류에 대한 의미는 와닿지 않을것이다. 다음의 예를 보자.

항상 1과 9 사이의 값만 반환하는 해시 함수를 쓰고 있다고 가정하자. 예를 들어 글자를 상응하는 숫자로 변환해서 하나의 숫자가 될 때 까지 결괏값의 숫자들을 계속해서 합하는 해시 함수라고 하자.

PUT = 16+21+20 = 57
## 57은 숫자가 둘 이상이므로 해시 함수는 5와 7을 쪼개 더한다.
5+7 = 12
## 마찬가지로 12도 둘 이상이므로 해시 함수는 1과 2를 쪼개 더한다.
1+2 = 3

결국 PUT은 3으로 해싱된다. 위 해시 함수는 당연하게도, 결과가 1과 9 사이값이 나오게 된다. 이러한 해시 함수는 충돌을 더욱 야기시키게 된다.

따라서 좋은 해시 함수란 사용 가능한 모든 데이터를 분산시키는 함수 이다. 데이터를 넓게 퍼뜨릴수록 충돌이 적다.

충돌 횟수가 줄어들수록 해시 테이블의 효율성이 높아진다고 했으니, 이론상 충돌을 피하는 최선의 방법은 해시 테이블에 많은 셀(할당 메모리)를 두는 것이다. 해시 테이블에 항목을 5개만 저장하고 싶다고 하자. 해시 테이블에 셀이 1000개면 충돌이 일어날 가능성이 거의 없으니 아주 좋을 듯 싶지만, 이는 메모리 낭비이다.

해시 테이블은 반드시 충돌 조정을 수행해야 한다. 좋은 해시 테이블은 많은 메모리를 낭비하지 않으면서 균형을 유지하며 충돌을 피한다.

이 때, 부하율(load factor)은 0.7이 가장 이상적이다. 부하율이란, 총 셀과 데이터를 저장할 셀의 비율이다. 즉, 14개의 데이터를 저장하려면, 20개의 셀이 있는것이 가장 이상적이다.