🔗HashTable?
-
hash는 내부적으로 배열을 사용하여 저장하기 때문에 빠른 검색 속도를 갖는다. 특정한 값을 Search하는데 데이터 고유의 인덱스로 접근하게 되므로 average case에 대하여 Time Complexity가 O(1)이 되는 것이다. 근데 이게 항상 O(1)이라는 것이 아니고 average case에 대해서 O(1)이라는 것이다. 왜냐하면 해시 함수는 데이터가 매우 많거나 해시 테이블의 크기가 작은 경우에는 다른 데이터가 같은 해시값을 가지는 collision이 발생할 수 있기 때문이다.
-
해시테이블에서 인덱스로 사용되는 키값은 일반적으로 입력된 데이터의 해시값을 이용하여 결정이 된다. 따라서 해시 함수가 제대로 구현되어 있지 않을경우 Hash Tabel은 인덱스로 저장되는 key값이 불규칙하게 된다. 따라서 해시 함수를 잘 구현해야 한다.
🔗Hash Function?
- Hash Function에 의해 반환된 데이터의 고유 숫자값을 hashcode라고 한다. 즉, 저장되는 key값을 hash function을 통해서 작은 범위의 값들로 바꿔준다.
- 어설픈 hash function을 통해서 key값들을 결정한다면 동일한 값이 도출될 수가 있다. 이렇게 되면 동일한 key값에 복수 개의 데이터가 하나의 테이블에 존재할 수 있게 되는 것인데 이를 collision 이라고한다.
🎇좋은 Hash Function
일반적으로 좋은 hash function은 키 일부분을 참조하여 해쉬 값을 만들지 않고 전체를 참조하여 해쉬 값을 만들어 낸다. 왜냐하면 키의 일부분만을 참조하여 해시 값을 생성하면, 해시값이 충분히 분포되지 않아 충돌이 자주 발생할 수 있기 때문이다. 하지만 근본으로 좋은 해시 함수는 키가 어떤 특성을 가지고 있느냐에 따라 달라지게 된다. 이유는 다음과 같다.
입력 데이터의 분포가 균등하지 않은 경우에는 키의 일부분만을 참조하여 해시 값을 생성하는 것이 충돌을 줄여 더 효율적일 수 있다.입력 데이터의 크기가 매우 큰 경우에는 키 전체를 참조하여 해시 값을 생성하는 것이 계산 복잡도 면에서 비효율적일 수 있다. 이 경우에는 해시 함수가 일부분의 데이터만을 참조하여 해시 값을 생성하는 것이 더 효율적이다.
지금부터 해시 충돌을 해결하기 위한 다양한 자료가 있지만 기본적인 두 가지 방법을 설명하겠다. 나머지는 다음 두 가지 방법을 응용한 방법이기 때문이다.
🔗충돌 해결법 - Open Address 방식(개방주소법)
- 해시 충돌이 발생하면, (즉 삽입하려는 해시 버킷이 이미 사용중인 경우) 다른 해시 버킷에 해당 자료를 삽입하는 방식이다.(해시 버킷이란 해시 테이블에서 각각의 데이터를 저장하는 공간을 의미)
- 공개 주소 방식이라고도 불리는 이 알고리즘은 충돌이 발생하면 데이터를 저장할 장소를 찾아 해맨다. 최악의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아 올 수 있다. 이 과정에서도 여러 방법들이 존재하는데 3가지를 알아보면 다음과 같다.
Linear probing: 순차적으로 탐색하여 비어있는 버킷을 찾을 때까지 계속 진행
Quadratic probing: 일정한 간격으로 떨어진 새로운 버킷을 탐색하는 방법이다. 일반적으로는 제곱수를 이용하여 간격을 설정
Double hashing probing: 하나의 해쉬 함수에서 충돌이 발생하면 2차 해쉬함수를 이용해 새로운 주소를 할당한다. 다시말하면 해시 충돌이 발생한 버킷에서 일정 간격으로 떨어진 새로운 버킷을 찾는 대신, 다른 해시 함수를 이용하여 해시값을 계산하고, 그 결과값을 이용하여 새로운 위치를 찾는다. 이는 위에서 설명한 두 가지 방법에 비해 많은 연산량을 요구한다.
🔗충돌 해결법 - Seperate Chaining 방식(분리 연결법)
Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면 Worst Case 에 가까워 지는 빈도를 줄일 수 있다. Java 7 에서는 Separate Chaining 방식을 사용하여 HashMap 을 구현하고 있다. Separate Chaining 방식으로는 두 가지 구현 방식이 존재한다.
연결 리스트를 사용하는 방식(Linked List)
각각의 버킷(bucket)들을 연결리스트(Linked List)로 만들어 Collision 이 발생하면 해당 bucket 의 list 에 추가하는 방식이다. 연결 리스트의 특징을 그대로 이어받아 삭제 또는 삽입이 간단하다. 하지만 단점도 그대로 물려받아 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담이 된다. 또 다른 특징으로는, 버킷을 계속해서 사용하는 Open Address 방식에 비해 테이블의 확장을 늦출 수 있다.(일반적으로는 테이블의 확장이 자주 발생하는 것보다는 테이블의 확장을 최소화하는 것이 좋다.)
Tree 를 사용하는 방식 (Red-Black Tree)
기본적인 알고리즘은 Separate Chaining 방식과 동일하며 연결 리스트 대신 트리를 사용하는 방식이다. 연결 리스트를 사용할 것인가와 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 key-value 쌍의 개수이다. 데이터의 개수가 적다면 링크드 리스트를 사용하는 것이 맞다. 트리는 기본적으로 메모리 사용량이 많기 때문이다. 데이터 개수가 적을 때 Worst Case 를 살펴보면 트리와 링크드 리스트의 성능 상 차이가 거의 없다. 따라서 메모리 측면을 봤을 때 데이터 개수가 적을 때는 링크드 리스트를 사용한다.
🔗어떤 충돌 해결 방식이 좋냐?
일반적으로 Open Addressing은 Seperate Chaining보다 느리다. Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 충돌 처리에 더 많은 시간이 소요 되기때문에 느릴 수 있다. 하지만 데이터셋의 크기나 해시 함수의 특성에 따라서 성능 차이가 달라질 수 있다 일반적으로 데이터셋의 크기가 작고 해시 함수의 분배가 균등하다면 Open Addressing 방식이 Separate Chaining 방식보다 더 빠를 수 있다. 왜냐하면 Separate Chaining 방식에서는 각각의 버킷마다 연결 리스트를 유지해야 하기 때문에 메모리 사용량이 크고, 삽입 또는 삭제 시에는 해당 리스트를 순회해야 하기 때문이며, 이러한 경우 Cache Miss(CPU가 참조하려는 데이터나 명령어가 캐시에 존재하지 않고 메모리에서 읽어와야 하는 경우) 가 발생할 가능성이 높아진다.
Seperate Chaining이 무조건적으로 좋다는게 아닌게, Seperate Chaining 방식은 Open Addressing 방식보다 테이블의 확장을 늦출 수는 있지만 작은 데이터를 저장할 때는 연결 리스트 자체의 오버헤드가 부담이 되므로, 데이터의 크기와 분포에 따라 적절한 방식을 선택을 해야한다.
🔗Separate Chaining이 Open Addressing 방식에 비해 확장을 늦출 수 있는 이유
Open Addrssing방식에서는 충돌이 자주 발생한다. 이는 성능을 저하시키는 원인이 되며 성능이 저하되었을때는 2가지 선택지가 있는데 해시 테이블의 크기를 늘이거나, 해시 함수를 개선하는 것이다. 해시 테이블의 크기를 늘이기 때문에 Separate Chaining방식에 비해서 확장이 급하다는 것이다.
Separate Chaining 방식은 Open Addressing 방식과 달리 버킷 내부에서 충돌이 발생하더라도 새로운 노드를 추가할 수 있으므로, 일정 수준 이상의 충돌이 발생하지 않는 한 버킷 크기를 늘리지 않아도 된다. 이러한 이유로 Separate Chaining 방식은 Open Addressing 방식보다 해시 테이블의 확장을 늦출 수 있다는 것이다.
🔗Python의 HashTable은 어떤 자료구조 기반인가?
예전에는 https://github.com/python/cpython/blob/main/Objects/odictobject.c#L466에서 연결리스트 기반으로 하는 것을 확인할 수 있었다. 그러나 3.6부터는 odictobject.c파일을 사용하지 않으며, dictobject.c 파일을 사용한다.
14번째 줄에 들어가면, https://mail.python.org/pipermail/python-dev/2012-December/123028.html 사이트로 이동을 할 수 있다.
불필요하게 비효율적인 파이썬의 해시테이블을 현재는 24바이트 항목을 희소 인덱스 테이블이 참조하는 dense 테이블로 표현한다고 한다.
위와같이 배열 기반으로 저장을 한다고 한다. 이는 이전과 동일한 해시 알고리즘을 사용하면서 메모리 절약에 매우 효율적이기 때문이라고 한다.
🔗Javascript의 HashTable은 어떤 자료구조 기반인가?
사실 js가는 경우는 엔진에 따라서 해시맵의 구현방식이 다르다. v8을 기준으로 설명을 해보겠다. js의 헤시테이블은 헤시맵 기반인데 배열 기반이다. 이는 아래의 주소에서 확인할 수 있다.
https://github.com/v8/v8/blob/main/src/base/hashmap.h
위의 주소에서 찾아보면, 해시맵의 배열 기반 구현은 TemplateHashMapImpl 클래스 내부에서 이루어진다.
TemplateHashMapImpl클래스의 정의에서 보면,using Entry = TemplateHashMapEntry<Key, Value>;라인이 있다. 이는TemplateHashMapEntry구조체를Entry로 별칭(alias)하여 사용한다는 의미이다.
map_라는 멤버 변수가 선언되어 있다. 이 변수가 해시맵의 배열을 가리키고 있다.Initialize()함수에서impl_.map_ = impl_.allocator().template AllocateArray<Entry>(capacity);라인에서map_에 동적으로 메모리를 할당하고 있다. 이 때AllocateArray함수를 사용하여 배열 기반으로 메모리를 할당하고 있다.
위와 같은 코드를 보면, 해시맵의 엔트리들이 Entry* 배열 형태로 관리되고 있음을 알 수 있다. 배열 기반으로 해시맵이 구현되어 있기 때문에 인덱스를 사용하여 빠르게 엔트리를 찾고 삽입할 수 있기 때문이다.
🔗Java의 HashTable은 어떤 자료구조 기반인가?
자바의 경우에는 Hashtable.java파일에서 배열인 것을 바로 확인할 수 있다. 주소는 다음과 같다.
https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/Hashtable.java
새로운 entry를 생성하는것에 배열을 사용한다.
자바의 해시테이블이 배열 기반인 이유는 다른 언어처럼 해시 버킷을 배열의 인덱스로 직접 접근하여 데이터를 저장하고 검색하기 때문에 매우 빠른 접근 시간을 제공하기 때문이라고 한다. 다만, 이는 크기가 동적으로 되지 않기 때문에 최근에는 HashMap을 사용한다.
HashMap은 해시 테이블을 배열로 구현하지만, 크기를 자동으로 조정하여 동적으로 관리할 수 있기 때문에 더 많이 사용.
🔗마무리
포스팅을 하면서 3가지 언어의 해시테이블의 자료구조 기반을 바로 보여주기에는 설명이 부족하다는 것을 느끼게 되었다. 마침 깃허브에 이론적으로 잘 정리가 되어있는 페이지를 찾아서 내가 공부한 이론과 잘 적용해서 글을 적었다. 이후 각 언어의 코드를 살펴보며, 적용된 자료구조를 찾아보며 깊이 있는 공부를 했다는 느낌을 받았다.
참고자료
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#hash-table
https://mail.python.org/pipermail/python-dev/2012-December/123028.html
https://github.com/v8/v8/blob/main/src/base/hashmap.h
https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/Hashtable.java
소중한 정보 잘 봤습니다!