맵 Map 자료구조란?
저장된 데이터가 키 key와 값 value로 하나의 쌍을 이루는 자료구조를 말합니다.
키가 존재하지 않는 값은 저장할 수 없으며, 모든 키는 중복되지 않습니다.
키를 통해 값을 바로 구할 수 있으므로 데이터를 검색하는데 O(1)의 시간복잡도가 소요됩니다.
- 배열을 기반으로 하는 Map
배열을 기반으로 맵을 구현하면 index 값으로 데이터를 저장 및 검색이 가능하므로 O(1)이 소요됩니다.
그러나 배열은 컴파일 이전에 크기를 정해줘야 하므로 배열 사이즈를 넘어가는 key 값은 사용할 수 없는 문제가 있습니다.
즉, key값의 범위가 배열 사이즈를 초과하는 경우 수용할 수 없습니다.
이러한 문제를 해결하기 위해 나온 자료구조가 해쉬 테이블 Hash Table입니다.
해시 테이블 Hash Table이란?
해시 함수를 사용해서 키에 대한 해시값을 구하고, 해시값을 index로 삼아 key-value 쌍으로 데이터를 저장하는 자료구조입니다.
데이터가 저장되는 곳을 버킷 Bucket 또는 슬롯 Slot이라고 합니다.
- 해시 함수 Hash Function
해시 함수는 넓은 범위의 key 값을 좁은 범위의 key 값으로 변경하는 역할을 합니다.
적은 메모리에 데이터를 효율적으로 관리하기 위해 해쉬 함수가 필요합니다.
그림에서 f(x)를 해시 함수라고 합니다.
데이터가 많아지거나 잘 짜여진 해시 함수가 아니라면, 다른 데이터와의 해시값이 같아서 충돌 Collision이 발생할 수 있습니다.
충돌을 피하기 위해 배열의 크기를 늘리는 방법은 제한적이기 때문에, 충돌을 해결해 나가는 방법으로 해시 함수를 구현해야 합니다.
- 좋은 해시 함수의 조건
좋은 해시 함수는 특정 메모리 영역에 데이터가 집중적으로 몰리는 클러스터 Cluster 현상이 발생하지 않도록 하여 충돌을 덜 일으키는 함수라고 말할 수 있습니다.
데이터가 몰려있으면 충돌이 발생할 확률이 높아지고 충돌이 많이 발생할수록 데이터 검색/삽입에 필요한 시간복잡도가 O(n)에 가까워 집니다.
Hashing된 인덱스에 이미 다른 값이 들어있다면 저장할 다른 위치를 찾는 과정이 필요하기 때문입니다.
따라서 데이터가 테이블의 전체 영역에 고루 분포시켜 충돌이 발생할 확률이 낮춰야 합니다.
키의 특성에 따라서 해시 함수를 디자인하는 방법이 달라지며, 좋은 해시 함수는 키의 일부분을 참조하는 것이 아닌 키 전체를 참조해서 해시 값을 만들어 냅니다.
적은 수의 데이터를 조합해서 해시값을 생성하는 것보다 많은 수의 데이터를 조합하여 해시값을 생성했을 때, 더 다양한 해시값을 생성할 수 있기 때문입니다.
- 충돌 Collision 해결 방법
- 열린 어드레싱 방법 (Open Addressing Method, 개방주소법)
Open Addressing 방법은 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장하는 방법으로 충돌을 해결한다.
충돌을 해결하기 위해 Linked List와 같은 추가적인 메모리 공간을 사용하지 않고 빈 슬롯을 찾아나간다.
따라서 Seperate Chaining 방법에 비해 메모리를 적게 사용한다.
하지만 기본적으로 배열을 사용하기 때문에 데이터를 더 넣기 위해서 배열을 확장해야 할 수도 있다.(Resizing)
Open Addressing 방법은 채워진 버킷이 많아질수록 충돌 발생 확률이 더 높아지기 때문에 일반적으로 Seperate Chaining 방법보다 느리다.
1. 선형 조사법 Linear Probing
충돌이 발생했을 때 순차적으로 n칸씩 탐색하면서 빈 버킷을 찾아 저장하는 방법입니다.
key = k이고 f(k)에서 충돌이 났을 때, f(k)+1 -> f(k)+2 -> f(k)+3 -> · · · 으로 빈 버킷을 찾아 나갑니다.
따라서 선형 조사법은 충돌 횟수가 증가함에 따라 클러스터 현상이 발생하는 단점이 있습니다.
또한, 슬롯의 상태 정보를 별도로 관리해줘야 하며, 해시값이 같으면 빈 슬롯을 찾기 위해 접근하는 위치가 늘 동일하므로 O(n)이 소요될 수 있습니다.
2. 이차 조사법 Quadratic Probing
충돌이 발생했을 때 n^2칸 뒤의 슬롯을 탐색해 나가면서 빈 슬롯을 찾아 저장하는 방법입니다.
key = k이고 f(k)에서 충돌이 났을 때, f(k)+1^2 -> f(k)+2^2 -> f(k)+3^2 -> · · · 으로 빈 버킷을 찾아 나갑니다.
이차 조사법 역시 슬롯의 상태 정보를 별도로 관리해줘야 하는 단점이 있으며, 해시값이 같으면 빈 슬롯을 찾기 위해 접근하는 위치가 늘 동일해 O(n)이 소요될 수 있습니다.
* 선형 조사법과 이차 조사법의 슬롯의 상태 정보 관리
1. EMPTY: 해당 슬롯에 데이터가 저장된 적이 없음
2. DELETED: 해당 슬롯에 데이터가 저장되었으나, 현재는 비워진 상태
3. INUSE: 해당 슬롯에 현재 유효한 데이터가 저장되어 있음
데이터가 삭제된 슬롯의 상태 정보(DELETED)를 따로 두어서 충돌이 발생했음을 의심하여 선형 조사법/이차 조사법에 따라 탐색 과정을 진행해야하기 때문에 슬롯의 상태 정보를 함께 관리해줘야 하는 과정이 필요합니다.
3. 이중 해시 Double Hash
이중 해쉬는 1차 해시값이 같아 충돌이 발생하면 2차 해시 함수를 통해 2차 해쉬값의 크기만큼 건너 뛰면서 빈 슬롯을 찾아나가는 방법입니다.
key가 다르면 2차 해쉬 값도 달라서 빈 슬롯을 찾기 위해 건너 뛰는 길이도 달라지기 때문에 클러스터 현상의 발생 확률을 낮출 수 있다는 장점이 있습니다.
1차 해시 함수는 key를 근거로 저장위치를 결정하는 함수이고, 2차 해시 함수는 1차 해시값으로 충돌이 발생했을 때 몇 칸 뒤로 건너 뛸지를 결정합니다.
이중 해시는 이상적인 충돌 해결책으로 알려져 있습니다.
- 닫힌 어드레싱 방법(Closed Addressing Method, 분리 연결법 Separate Chaining)
충돌이 있더라도 해당 해시값에 데이터를 연결 리스트나 트리를 활용해서 새 데이터를 저장하는 방법입니다.
1. 체이닝 Chaining
충돌이 발생하면 슬롯을 생성해서 연결 리스트에 추가하는 방식으로 해결하는 방법입니다.
연결 리스트의 특징으로 인해 슬롯의 삭제/삽입이 간단하다는 장점이 있습니다.
하지만 슬롯을 탐색할 때는 동일한 해시값으로 연결되어 있는 슬롯들을 모두 탐색해야 합니다.(O(n) 소요)
따라서 충돌이 자주 발생하지 않도록 해시 함수를 잘 정의하면 리스트 길이를 줄일 수 있습니다.
슬롯이 8개 이하일 경우에는 연결리스트를 사용하며, 8개 이상으로 늘어날 때는 트리를 사용한다.
트리는 연결 리스트에 비해 메모리 사용량이 많기 때문에 데이터가 적을 때는 연결리스트를 사용하는 것이 효율적이다.
트리를 사용하면 연결 리스트 방식에 비해 탐색에 소요되는 시간이 적다.(O(h) 소요)
* Open Addressing vs Separate Chaining
두 방법 모두 Worst Case에서는 O(n)이 소요됩니다.
Open Addressing 방법은 연속된 공간에 데이터를 저장하기 때문에 Saparate Chaining에 비해 캐시 효율이 높습니다.
Separate Chaining 방법은 충돌이 발생할 때마다 추가 슬롯을 계속해서 생성하는 반면, Open Addressing 방법은 테이블 확장이 필요할 수 있다.
따라서 데이터 개수가 적다면 Open Addressing 방법이, 많다면 Saparate Chaining 방법이 더 효율적이다.
참고
- 참고 도서: 열혈 자료구조 - 윤성우 지음
해시테이블 - 해시넷
해시 테이블로 된 작은 전화 번호부 해시테이블(hash table)은 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 인덱스 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하여 검색을
wiki.hash.kr
'Computer Science > Data Structures' 카테고리의 다른 글
| [비선형 구조] 그래프 Graph (0) | 2022.05.15 |
|---|---|
| [비선형 구조] 트리 Tree (0) | 2022.05.15 |
| [선형 구조] 스택과 큐 (0) | 2022.05.14 |
| [선형 구조] 리스트 (0) | 2021.07.18 |
| Prologue. 자료구조 (0) | 2021.06.28 |