코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.
- IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
- 상세 설명 - 수원대학교(대학일자리 플러스센터)
해시테이블(Hash Table)
- 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 삼아 데이터의 값 (value)을 키와 함께 저장하는 자료구조
- 이때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot)이라고 한다.
- 해시테이블의 탐색, 삽입, 삭제의 시간복잡도는 평균적으로 O(1)을 갖지만 충돌이 빈번하게 일어나면 최악의 경우인 O(n)의 시간복잡도로 수렴할 수 있다.
해시 충돌(Hash collision)
-
해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생하게 된다.
-
buckets은 보통 메모리를 적게 사용하기 위해 적게 할당해 따라서 keys > buckets인 경우가 잦아지며 충돌이 일어난다.
-
Direct Address Table : keys = buckets인 테이블이며 충돌이 일어나지 않는다.
아래 그림은 이름-전화번호를 매핑하기 위한 해시함수를 개념적으로 나타낸다.
예시의 해시 함수는 ‘daniel’과 ‘bill’를 모두 ‘05’로 매핑해 해시충돌을 일으키고 있다.
충돌 해결
아래는 해시 충돌을 해결하기 위한 방법들이다.
체인법(Separate Chaining)
- 한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써 모든 자료를 해시테이블에 담는 것
- 연결리스트와 비슷하고, 해당 버킷에 데이터가 이미 있다면 체인처럼 노드를 추가하여 다음 노드를 가리키는 방식으로 구현하기 때문에 체인이라고 한다.
개방번지화(Open Addressing)
-
Separate chaining과 달리 한 버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시테이블이며, 해시함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용한다는 취지다.
-
해시충돌이 자주 일어날 수 있다.
1. 선형탐사(Linear probing) - 최초 해시값에 해당하는 버킷에 다른 데이터가 저장되어 있으면 해당 해시값에서 고정 폭으로 옮겨 다음 해시값에 해당하는 버킷에 액세스(삽입, 삭제, 탐색)한다. - 만약 여기에 데이터가 또 저장되어 있으면 고정폭으로 또 옮겨 액세스한다. 2. 제곱탐사(Quadratic probing) - 최초 해시값에 해당하는 버킷에 다른 데이터가 저장되어 있으면 해당 해시값에서 그 폭이 제곱수로 늘어난다는 특징이 있다.
- 임의의 키값에 해당하는 데이터에 액세스할 때 충돌이 일어나면 1²칸 을 옮긴다.
- 여기에서도 충돌이 일어나면 이번엔 2²칸, 그 다음엔 3²칸 옮기는 식이다.3. 이중해싱(Double hashing) - 탐사할 해시값의 규칙성을 없애버려서 clustering을 방지하는 기법 - 2개의 해시함수를 준비해서 하나는 최초의 해시값을 얻을 때, 또 다른 하나는 해시충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용한다.
위와 같이 시간복잡도를 학습한 후 풀이한 문제는 아래와 같다.
끄적끄적