해시 맵(Hash Map, Hash Table)
해시맵은 키(Key)와 값(Value)이 한쌍으로 이루어진 데이터를 저장하고, 키를 이용하여 값을 검색할 수 있다. 내부적으로 배열을 이용하여 구현되며, 각 키는 해시 함수를 이용하여 배열의 인덱스로 변환되어 저장이 된다. 이 때, 해시 함수는 키의 일부를 이용하여 인덱스로 변환하는데, 이를 해싱(Hashing) 이라고 한다.
해시 함수를 통해 구한 인덱스에 해당하는 배열 위치에 데이터를 저장하면, 나중에 같은 키를 이용하여 검색할 때도 해시 함수를 통해 인덱스를 구한 후 해당 위치의 값을 바로 찾을 수 있다. 이 때 검색 시간 복잡도는 O(1)이기 때문에 매우 빠른 검색 속도를 보장하고 있다.
해시 맵(Hash Map)과 해시 테이블(Hash Table)의 차이점
해시 맵(Hash Map)과 해시 테이블(Hash Table)은 모두 해시 함수(Hash Function)를 사용하여 데이터를 저장하고 검색하는 자료구조이다. 하지만 두 개의 자료구조에서 차이점이 존재하는데 그것을 알아보고자 한다.
- 구현 방식
해시 맵은 연결리스트(Linked List)와 같은 자료구조를 사용하여 데이터를 저장한다. 반면에 해시 테이블은 배열(Array)을 사용하여 데이터를 저장한다.
- 충돌 처리 방식
해시 맵은 개방 주소법(Open Addressing)을 사용하여 충동을 처리하고, 해시 테이블은 체이닝(Chaining)을 사용하여 충돌을 처리한다.
- Null 값에 대한 처리방식
해시 맵은 null 값은 입력 받아도 예외처리가 되지 않고 그대로 사용이 가능하나, 해쉬 테이블은 null 값을 입력 받을 시 예외를 발생시킨다.
- Thread- safe 와 Thread-unsafe
해시 맵은 멀티 쓰레드 구동 방식에서 공용 변수값에 대한 확실성을 제공하지 않기 때문에 Threan-unsafe 하다고 하며 싱글 쓰레드에서 주로 사용이 된다. 반대로 해시 테이블은 Thread-safe 방식을 제공하므로 멀티 쓰레드 환경에서 해시 맵보다 우수하다.
해시 테이블(맵)의 구조
해시 테이블의 구조는 다음과 같다.
- 키 : 해시 테이블 접근을 위한 입력 값.
- 해시 함수 : 키를 해시 값으로 매핑하는 연산.
해시 함수
배열의 각 인덱스는 해시 함수를 이용하여 키를 연관시킨 값(value)을 저장한다. 이 때, 해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수로, 이 과정을 해싱(Hashing)이라고 한다.
- 해시 값 : 해시 테이블의 인덱스.
- 해시 테이블 : 키(key) - 값(value)를 연관시켜 저장하는 데이터 구조.
해시 충돌
해시 함수에 의해 연관된 인덱스에 이미 다른 값이 저장되어 있다면 충돌(Collision)이 일어나게 된다. 해시 충돌은 해시 함수의 효율성을 저하시키고, 데이터의 검색 성능을 감소시키는 원인이 된다. 따라서 충돌을 최소화하는 것이 중요하다.
해시 충돌 해결법
해시 충돌을 최소화하는 방법 중 하나는, 충돌이 발생했을 때 데이터를 저장할 다른 위치를 찾아내는 것이다. 대표적인 두 가지 방법은 개방 주소법(Open Address)과 연결 주소법(Separate Chaining) 그리고 분리 연결법(Separate Chaining)이 있다. 이에 대한 내용을 알아보도록 하자.
개방 주소법(Open Address)
충돌시 테이블에서 충돌이 발생한 해시 버킷이 아닌 다른 해시 버킷을 찾아 새로운 데이터를 저장하는 방법을 말한다. 즉, 개방 주소법은 해시 충돌이 발생하면 해시 함수를 다시 계산하여 새로운 위치를 찾는 방법이다.
개방 주소법에는 선형 탐사(Liner Probing), 이차 탐사(Quadratic Probing), 이중 해시(Double Hashing) 등이 있다.
선형 탐사는 충돌이 발생하면 다음 해시 버킷에 데이터를 저장하는 방법이다. 예를 들어, 만약 해시 버킷 3이 이미 사용 중이라면 해시 버킷 4에 데이터를 저장한다. 만약 해시 버킷 4도 사용 중이라면 해시 버킷 5에 데이터를 저장하는 식으로, 다음 해시 버킷에 차례로 데이터를 저장하게 된다. 문제점으로는 일차군집화 문제가 발생할 수 있다는 것이다.
일차 군집화
반복된 충돌이 발생할 시 해당 지점 주변에 데이터가 몰리는 경우를 말한다.
이차 탐사는 충돌이 발생하면 일정한 간격을 두고 다음 해시 버킷을 찾는 방법이다. 예를 들어, 만약 해시 버킷 3이 이미 사용 중이라면 해시 버킷 3 + 1^2에 데이터를 저장한다. 만약 해시 버킷 3 + 1^2도 사용 중이라면 해시 버킷 3 + 2^2에 데이터를 저장하는 식으로, 간격을 두고 다음 해시 버킷을 찾게 된다. 선형 탐사법의 일차 군집화를 일부 보완을 할 수 있으나 이차 군집화 문제가 발생 할 수 있다.
이중 해시는 충돌이 발생하면 두 개의 해시 함수를 사용하여 다음 해시 버킷을 찾는 방법이다. 예를 들어, 버킷 3이 이미 사용 중이라면 해시 함수 h1과 h2를 사용하여 다음 해시 버킷을 찾는다.
연결 주소법(Chaining)과 분리 연결법(Separate Chaining)
연결 주소법은 충돌이 발생한 버킷에 또 다른 데이터가 삽입될 때, 해당 버킷에 연결리스트를 이용하여 새로운 데이터를 연결시키는 방법이다. 이 방법은 간단하고 구현하기 쉬우며, 메모리를 효율적으로 사용할 수 있지만, 연결리스트의 길이가 길어질수록 탐색 시간이 늘어나느 단점이 있다.
반면 분리 연결법은 충돌이 발생한 버킷에 여러 개의 슬롯을 두어, 각 슬롯에 데이터를 저장하는 방법을 말한다. 삽입 시에는 해시 함수를 이용해 버킷을 찾은 뒤, 해당 버킷내에서 비어 있는 슬롯을 찾아 데이터를 저장한다. 이 방법은 연결 주소법에 비해 슬롯의 개수가 많을 수록 충돌 확률이 줄어들어 탐색 시간이 일정하게 유지된다는 장점이 있지만, 구현하기가 어렵고 메모리 공간을 많이 차지하는 단점이 있다.
따라서 연결 주소법은 데이터의 개수가 적은 경우나, 메모리 공간을 절약하고자 할 때 주로 사용되며, 분리 연결법은 데이터의 개수가 많거나, 해시 충돌이 자주 발생하는 경우에 주로 사용이 된다.
'Zero-Base > 자료구조-알고리즘' 카테고리의 다른 글
| 힙(heap) (0) | 2023.03.19 |
|---|---|
| 연결리스트(LinkedList) (0) | 2023.03.17 |
| 배열(Array) (0) | 2023.03.15 |
| 큐(Queue) 관련 문제 (0) | 2023.03.14 |
| 큐(Queue) (0) | 2023.03.14 |