Set, Dict의 자료구조가 검색이 빠른 이유? hash 함수
Summary: set, dict은 해시함수를 이용한 해시값을 저장하고있는 해시테이블이란 자료구조를 사용하기 때문에, 빠른 탐색이 가능함. 해시는 임의의 변수(문자열 등)를 숫자로 변환하여, 매핑하는 것을 의미함. 따라서, 임의의 변수가 오더라도 숫자로 매핑할 수 있고, 이 숫자로 매핑한 경우 인덱스처럼 사용할 수 있어 빠른 검색이 가능함.
도입: 파이썬으로 자료를 저장하다보면 많은 양의 데이터를 저장해야하는 경우가 있다. 가령, 유전정보와 같이 1번 유전자의 100번째의 위치의 DNA가 바뀌었는지 여부 뿐만아니라... 101번, 10,000,000번째의 위치가 변경되었는지, 변경되었으면 무엇으로 변경되었는지 저장한다. 문제는 이렇게 많은 정보를 저장한 것을 읽어, 특정위치(Input으로 주어지는 위치)에 변이가 있었는지 찾아야한다면? 많은 연산을 해야할 것이다.
해시란(hash)?
해시는 임의의 길이를 갖는 임이의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말한다. 쉽게 말해서, 입력값을 아무거나 넣더라도, 각기 다른 출력값을 반환하는 것이다(단, 출력값의 길이는 동일 // 입력값을 동일하게 할경우 출력값은 일관성 있게 동일). 예를 들어, 가장 쉬운 해시는 mod 연산이다. mod k 연산은 어떤 숫자를 k로 나눴을 때 나머지를 구하는 연산인데 이를 통해 해시를 구현할 수 있다. 아래의 예시와 같이 임의의 숫자 13, 3, 14, 23, 22를 7로 나눠 각각 나머지를 구했다. 이런식으로 각각 원소인 13을 6으로 매핑, 3을 3으로 매핑 14을 0으로 매핑하는 것처럼 원래 데이터를 매핑하는 것을 의미한다.
| mod 7 (13) | 6 | A -> G |
| mod 7 (3) | 3 | G -> A |
| mod 7 (14) | 0 | T -> C |
| mod 7 (23) | 2 | C - > T |
| mod 7 (22) | 1 | C -> T |
(Table 1. mod 7 연산의 결과)
그런 다음에, 6을 인덱스로 해서 "A->G"라는 데이터를 저장하고, 3에 "G->A"라는 것을 저장하듯 모든 배열을 위와같이 저장한다. 그러면, 14의 내용이 무엇인지 찾고자할때, 13, 3, 14, 23, 22의 중에 14를 찾아서 따라가는 것이 아니라, 1) 14을 mod 7 (14)을 해서, 0을 얻은다음, 2) 0의 인덱스에 무엇이 저장되어있는지 확인하면 된다. 이런 방법으로하면, 상당히 긴 배열에서도 13=14냐? 3=14이냐? 23이 23이냐?? 모두 1:1로 비교하는 방법(선형탐색)을 하지 않고, 바로 검색을 할 수 있다. 이 이유가 hash를 쓰는 이유이다.
| 6 | A -> G |
| 3 | G -> A |
| 0 | T -> C |
| 2 | C - > T |
| 1 | C -> T |
그리고, 우리는 위의 6, 3, 0, 2, 1과 같은 값들을 해시값(hash value) 또는 다이제스트(Digest)라고 부르고, 해시값과 저장되어있는 값("A->G", "G-A"...)와 같이 위의 정보를 테이블형태로 저장하고 있는 자료구조를 해시테이블(hash table)이라고 한다.
Hash collision: 혹시나 해시값이 중복이면 어떻게되나?
해시충돌의 경우는 아래와 같다. 아래처럼 14의 값과 21을 해시함수 mod 7을 했을 경우 결과값(해시값)이 동일하다. 이 경우는 해시값이 중복인 경우 (예, 0인 경우), 14에서 부터 해시값이 나온건지 21에서부터 해시값이 0이 나온것인지 구분이 필요하다.
| mod 7 (13) | 6 | A -> G |
| mod 7 (3) | 3 | G -> A |
| mod 7 (14) | 0 | T -> C |
| mod 7 (23) | 2 | C - > T |
| mod 7 (22) | 1 | C -> T |
| mod 7 (21) | 0 | T -> A |
위의 예시만 봐도, 위의 mod 함수를 해시함수로 쓰는 경우 해시값(output)의 충돌은 발생한다. 가장 좋은 건 해시함수를 좋은 해시함수(결과물의 충돌이 거의 없는 함수)를 쓰는 것이 좋다. 그러나, 좋은 해시함수를 쓰더라도, 해시충돌이 발생할 확률은 언제나 존재한다. 이 원인에 대한 직관적인 이해는 비둘기집의 원리와 같다.
비둘기집의 원리: "차량등록번호", "휴대전화번호"처럼 차량수/휴대전화가가 등록할수 있는 번호의 개수를 초과하는 경우와 같은 원리. 비둘기집이 9개가 있고, 각 비둘기집에는 한 마리씩 비둘기가 있을 수 있다고 가정해보자. 만일 비둘기가 10마리가 있다면 어떻게될까? 9개의 집 중, 하나는 두마리가 들어가야한다. 마찬가지로 "고정길이 문자열을 반환하는 해시값은 유한하다. 따라서, 임의의 가변길이 문자열의 개수 > 반환할 수 있는 고정길이 문자열이기에, 겹칠 수 있다"는 말이다. 예를 들어, 영어 알파뱃 26개인데 정보를 10개의 고정길이 문자열로 반환하는 해시함수를 만들었다고 하자. 해시함수가 반환할 수 있는 값은 26의 10제곱이다. 그러나 입력값을 0부터 ZZZZZZZZZZZZZZZZZZZZZ까지 엄청나게 많은 은 알파벳과 숫자의 조합이라면? 매핑할 수 있는 값의 종류가 모자르다.
자세한 내용은 아래를 참고하자 (https://en.wikipedia.org/wiki/Pigeonhole_principle)
따라서, 해시값이 충돌할 경우, 여러 방안이 존재한다. 체이닝, Open addressing (선형탐사, 제곱탐사, 이중해시).. 등 여러 방법이 존재한다. 가장 쉬운 예시는, 겹치는 해시값안에는 여러 변수를 일단 배열형태로 저장한 후에, 선형탐사하는 것이다. 일단 겹치는 경우, 저장하고 훨씬 적은 수를 선형탐사해서 찾겠다는 것과 같다.
Set, Dict 에서의 hash테이블: 파이썬의 set, dict자료구조는 해시테이블을 이용한다. 즉, dict의 key와 set의 원소를 x라한다면, hash(x)을 실행시켜 같으면 x원소가 반드시 존재한다는 것으로 활용할 수 있다. 아래는 set의 해시테이블을 직접 접근한 예시이다. 아래와 같이 파이썬의 내장함수는 해시함수를 제공하고 있다.
>>> hash
<function hash(obj, /)>
그리고, 파이썬의 객체는 hash함수값을 매직매서드로 가지고있다. 아래의 "a"라는 문자의 해시값은 "8870042888964940309"이다.
>>> "a".__hash__()
8870042888964940309
그리고 set을 하나 만들어, 해시값을 소환해보자. set 내부에 해시테이블을 직접 접근하는 방법은 찾지 못했으나, 이와 유사하게 아래와같이 각 원소의 hash값을 알고있으면 이를 통해서 검색하면 매우 빠르다.
>>> myset = {"a", "b"}
>>> {element.__hash__() for element in myset}
{8703158610484096297, 8870042888964940309}