알고리즘/자료구조
선형 자료구조 - 6. 해시 테이블
- -
해시 테이블 (Hash Table)
해시 테이블이란 키(Key)와 값(Value)을 1:1로 대응시켜 저장하는 데이터 구조입니다.
키를 통해서 원하는 데이터에 빠르게 접근이 가능합니다.
해시 테이블 구조
- 키(Key) : 해시 테이블에 접근하기 위한 값
- 해시 함수(Hash Function) : 키를 해시 값으로 매핑하는 연산
- 해시 값(Hash Value) : 해시 테이블의 인덱스
- 해시 테이블(Hash Table) : 키-값을 저장하는 데이터 구조
해시 테이블은 입력받은 키 값을 해시 함수를 이용해 변환합니다. 여기서 나오는 값을 해시 테이블의 인덱스 삼아서 데이터를 저장하게 됩니다.
해시 충돌
해시 테이블을 올바르게 이용하기 위해선 적절한 해시 함수를 통해 테이블에 값들이 골고루 분포되도록 해야하며, 그러지 못할 경우, 해시 충돌이 발생합니다.
해시 충돌이란 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우를 뜻합니다. 보통 서로 다른 키인데도 불구하고 해시 함수를 통한 해시 값이 동일한 경우 발생합니다.
이러한 해시 충돌을 최대한 적게 발생하도록 해시 함수를 구성해야합니다.
해시 충돌을 해결하는 방법은 크게 두가지로 나눠볼 수 있습니다.
개방 주소법 (Open Address)
개방 주소법은 충돌 발생 지점부터 테이블의 비어있는 공간을 찾아 데이터를 저장하는 방법입니다.
Hash와 Value가 1:1 관계를 유지합니다.
비어있는 공간을 찾는 방법은 다음과 같은 방법들이 있습니다.
선형 탐사법
충돌 발생 지점부터 이후의 빈 공간을 순차적으로 탐사하는 방법입니다.
이러한 선형 탐사법은 일차 군집화 문제가 발생하게 됩니다.
충돌이 발생하면 근처에 데이터들이 저장되게 되는데, 이게 반복되면 데이터들이 몰려있는 부분이 생기게 되고, 해시 테이블에 골고루 분포되지않아 높은 확률로 그 군집에 해시충돌이 일어날 수 있게 되는 악순환이 발생할 수 있습니다.
제곱 탐사법
제곱 탐사법은 충돌 발생 지점부터 빈 공간을 n제곱만큼의 간격을 두고 탐사하는 방법입니다.
선형 탐사법의 일차 군집화 문제를 어느정도 해결할 수는 있지만, 결국 다시 충돌이 반복되다보면 선형탐사법의 문제점과 마찬가지로 이차 군집화 문제가 발생하게 됩니다.
이중 해싱
이중 해싱은 해싱 함수를 이중으로 사용하는 방법입니다.
첫번째 해시함수는 최초 해시를 구할 때 사용하고, 두번째 해시함수는 충돌 발생 시 얼마나 이동하여 탐사해야하는지를 구할 때 사용합니다.
이 방법은 앞에서 다룬 선형 탐사, 제곱 탐사에 비해 데이터가 골고루 분포됩니다.
분리 연결법 (Separate Chaining)
분리 연결법은 충돌 발생 시, 테이블 내의 다름 위치를 탐색하지 않고 연결 리스트를 이용하여 해당 테이블에 데이터를 계속해서 연결하는 방법입니다.
프로그래밍 언어에서 구현
Java
자바에서는 HashTable, HashMap이라는 이름으로 제공하고 있습니다.
둘의 차이점은 이곳을 참고하세요. 추가적으로 되도록이면 HashMap을 사용하고, Thread-Safe하고 싶다면 HashTable 대신 SyncronizedMap이나 ConcurrentHashMap을 사용하면 됩니다.
HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 10);
map.put("key2", 20);
map.get("key1"); // 10'알고리즘 > 자료구조' 카테고리의 다른 글
| 비선형 자료구조 - 2. 이진 탐색 트리 (0) | 2023.04.18 |
|---|---|
| 비선형 자료구조 - 1. 트리 (0) | 2023.04.17 |
| 선형 자료구조 - 5. 데크 (0) | 2023.04.17 |
| 선형 자료구조 - 4. 큐 (0) | 2023.04.17 |
| 선형 자료구조 - 3. 스택 (0) | 2023.04.14 |
Contents
소중한 공감 감사합니다