이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다.
https://github.com/AeroCodeX/
해시 테이블 ADT |
키-값 형식의 딕셔너리 구조체로,
해시 함수의 입력으로 값을 넣고, 결과값을 키로 사용하는 자료구조 인터페이스.
배열을 미리 할당한 뒤,
키에 대응되는 인덱스에 데이터를 저장한다.
이때, 해시함수의 범위는 [0, 배열의 크기)로 정한다. (인덱스가 배열을 넘어가면 안되기 때문.)
해시 함수 |
값을 인자로 받아 키로 매핑하는 함수.
해시 함수의 범위는 배열의 크기를 벗어나지 말아야 한다.
또한 해시 함수가
- 너무 복잡하거나 (해시 함수의 시간 복잡도가 너무 크거나),
- 너무 간단하면 (해시 함수의 결과 범위가 너무 작거나).
해시 테이블의 전체 성능에 영향을 끼치므로 주의해야 한다.
해시 충돌 |
해시 함수의 결과 범위가 너무 작으면,
서로 다른 데이터가 같은 키를 갖는 경우가 빈번하게 발생한다.
양의 정수를 저장하는 해시 테이블에 대하여,
해시함수를 Hash(x) = x mod 10 이라고 정의하면,
{ 1, 11, 21, 31, 41, .. }의 모든 요소가 같은 키를 가지게 될 것 이다. (이것을 해시 충돌이라고 한다.)
해시 충돌이 발생하면, 해시 테이블의 성능이 급감하는데.
아쉽게도, 해시 충돌을 허용하지 않으면 데이터 소실이 발생할 위험이 있다.
해시 충돌의 허용 여부에 따라,
- 키 중복 허용 (안전하나, 복잡하고 느림)
- 키 중복 불가 (안전하지 않으나, 간단하고 빠름)
키 중복 허용 (해시 충돌 허용) |
해시 충돌을 허용하는 방법에는 2가지가 있다.
- 비어있는 다른 키에 저장하거나,
- 애초에 중복을 가정하고, 키를 배열로 구현하는 것 이다.
1) 비어있는 다른 키에 저장.
아래는 해시함수 Hash(x) = x mod 10 을 사용하는 해시 테이블이다.
52를 저장하려고 했지만, 72로 인해 충돌이 발생했다.
비어있는 다른키에 저장해야 하므로, 앞으로 한칸씩 비어있는 키를 찾는다.
이 경우에는 6번 칸에 저장될 것 이고, 비어있는 칸이 없다면 삽입이 실패한다.
저장이 완료된 후에, 72를 삭제하더라도 52를 옮기지 않는 편이 좋다.
모든 해시 충돌을 해소하기에는 너무 많은 비용이 소요되기 때문이다.
2) 키를 배열로 구현.
같은 키를 갖는 데이터를, 하나의 배열에 집어넣는 방식이다.
해시 충돌과 성능 |
왜 해시 충돌이 발생하면 성능이 급감할까?
해시 충돌을 거부하는 경우와, 허용하는 경우에 대해 생각해보자.
- 해시 충돌을 거부
충돌이 일어나지 않을것이라는 확신을 갖고 있는 경우,
해시 테이블은 최상의 시간적 성능을 제공한다.
주민등록번호를 키값으로 갖는 해시 테이블의 경우,
인덱스 접근비용만으로 데이터에 액세스할 수 있다.
- 탐색/검색 : O(1) (단, 해싱함수 오버헤드 있음.)
- 삽입/삭제 : O(1)
- 해시 충돌을 허용
각 고유키마다 메모리를 할당해야 하므로,
모든 고유키를 포용하기 어려운 경우, 차선으로 해시 충돌을 허용한다.
이 경우에는, 같은 키지만 다른 데이터인 경우를 상정해야 한다.
이름을 통해 사람을 검색할 때, 동명이인이 포함되어 있으므로,
내가 찾는 사람이 있는지 검사하는 과정이 존재해야 한다.
동명이인이 많으면 많을수록 성능은 급감한다.
- 탐색/검색 : O(n) (단, 해싱함수 오버헤드 있음.)
- 삽입/삭제 : O(n)
구현에 따른 해시 테이블의 성능 (충돌 거부) |
키(인덱스) 기반의 인터페이스이기 대문에,
우선 인덱스를 지원하지 않는 구현을 사용할 수 없다.
- 배열?
인덱싱을 통한 조회 성능이 우수할 뿐만 아니라,
처음, 중간 데이터가 삭제되더라도 데이터를 앞당기지 않는 해시 테이블의 특성 덕분에,
배열의 단점이 디메리트가 되지 않는다.
- 단일 연결 리스트?
인덱싱 불가.
- 이중 연결 리스트?
인덱싱 불가.
- 벡터?
수용량이 유동적이라는 것만 다를 뿐, 기본적으로 배열과 동일하다.
단, 해당 데이터가 담긴 부분배열을 찾는데 걸리는 오버헤드를 감수해야 하며.
실수로라도 중간 지점에서 데이터를 삽입하거나 제거한 경우,
자동적으로 순서가 변경되기 때문에 유의해야 한다.
- 스킵 리스트?
인덱싱 불가.
인덱스 스킵 리스트의 경우.
인덱스 탐색비용이 O(log n)이기 때문에, 배열이나 벡터에 비해 불리하다.
- 환형 배열?
인덱스가 동적으로 변화하므로,
인덱스 보장이 불가.
- 덱 (데크)
수용량이 유동적이라는 것만 다를 뿐, 기본적으로 배열과 동일하다.
단, 해당 데이터가 담긴 부분배열을 찾는데 걸리는 오버헤드를 감수해야 하며.
실수로라도 중간 지점에서 데이터를 삽입하거나 제거한 경우,
자동적으로 순서가 변경되기 때문에 유의해야 한다.
구현에 따른 해시 테이블의 성능 (충돌 허용) |
각 키의 배열을 어떻게 구현할 것인가?
- 배열?
간단하고 별다른 오버헤드도 없으나.
저장된 데이터를 파악하기 어렵고, 수용량을 늘리기 어렵다는 단점이 있음.
- 단일 연결 리스트?
노드당 1개의 포인터를 추가로 지불해야 하지만, 미비한 편.
유동적인 수용량 조절이 가능하지만, 역방향 탐색이 불가능한 것이 단점이다.
- 이중 연결 리스트?
노드당 2개의 포인터를 추가로 지불해야 하지만, 역시 미비한 편.
유동적인 수용량 조절이 가능하다.
- 벡터?
수용량이 유동적이라는 것만 다를 뿐, 기본적으로 배열과 동일하다.
단, 수용량 확장이 일어날 때, 오버헤드가 발생한다는 것에 유의하자.
- 스킵 리스트?
메모리를 추가로 지불해야 하긴 하지만, 자체적인 이분검색을 사용하므로,
O(log n)시간만에 검색할 수 있다는 것은 상당히 매력적이다.
- 환형 배열?
기본적으로 배열과 동일하다.
다만 저장된 데이터의 수를 파악하기에는 용이하다.
- 덱 (데크)?
수용량이 유동적이라는 것만 다를 뿐, 기본적으로 배열과 동일하다.
단, 수용량 확장이 일어날 때, 오버헤드가 발생한다는 것에 유의하자.
해시 테이블 ADT의 특성 |
- 실질적인 데이터 정렬이 불가능한 인터페이스.
- 해시 충돌 여부가 전체성능에 큰 영향을 끼침.
해시 테이블의 성능을 향상시키는 법 |
- 해시 충돌이 발생하지 않게 한다.
- = 메모리를 추가적으로 지불한다.
- = 해시 함수의 범위를 충분히 늘린다.
