오늘은 자료구조에서 Hash Map에 대해서 알아보는 시간을 갖도록 하겠다.
Hash Table
(0) 배경 지식
* Hash
임의의 길이의 값을 해시함수(Hash Function)를 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다.
* Hash Function
키(Key)를 해시(Hash)로 바꿔주는 역할을 한다. 다양한 길이를 가지고 있는 key를 가지는 hash로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다. 다만, 서로 다른 key가 같은 hash가 되는 경우를 해시 충돌(Hash Collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.
* Key
고유한 값이며, 해시 함수의 input이 된다. 다양한 길이의 값이 될 수 있다. 이 상태로 최종 저장소에 저장이 되면 다양한 길이 만큼의 저장소를 구성해 두어야 하기 때문에 해시 함수로 값을 바꾸어 저장이 되어야 공간의 효율성을 추구할 수 있다.
* Value
저장소(bucket, slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능하다.
* Slot
한 개의 데이터를 저장할 수 있는 공간을 말한다. (bucket으로 불리기도 한다.)
(1) 정의
- 키(Key)에 데이터(Value)를 저장하는 데이터 구조이다.
(2) 특징
- Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라진다.
- 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용한다. (공간과 탐색 시간을 맞바꾸는 기법)
(3) 장점
- 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
- 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉽다.
(4) 단점
- 일반적으로 저장공간이 좀더 많이 필요하다.
- 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도의 자료구조가 필요하다.
- Hash Function의 의존도가 높다. (Hash Function 성능이 중요하다.)
- 순서가 있는 배열에는 어울리지 않는다.
(5) 주요 용도
- 검색이 많이 필요한 경우
- 저장, 삭제, 읽기가 빈번한 경우
- 캐쉬 구현시 (중복 확인이 쉽기 때문)
(6) 시간 복잡도
- 일반적인 경우(Collision이 없는 경우) : O(1)
- 최악의 경우(Collision이 모두 발생하는 경우) : O(n) (Chaining에 연결된 리스트들까지 검색을 해야할 때)
(7) 충돌(Collision) 해결1 : 알고리즘
① Separate Chaining (분리 연결법)
- 해시 테이블 저장공간 외의 공간을 활용하는 기법으로 충돌이 일어나면, Linked List라는 자료 구졸르 사용해서, Linked List를 추가로 뒤에 연결시켜서 저장하는 기법이다.
그림을 보면 John Smith와 Sandra Dee의 인덱스가 152로 충돌하게 된 경우인데, 이 때 Sandra Dee를 John Smith 뒤에 연결함으로써 충돌을 처리했다.
*장점
1) 한정된 저장소를 효율적으로 사용할 수 있다.
2) 해시 함수를 선택하는 중요성이 상대적으로 적다.
3) 상대적으로 적은 메모리를 사용해, 미리 공간을 잡을 필요가 없다.
*단점
1) 한 해시에 자료들이 계속 연결된다면 검색 효율이 떨어진다.
2) 외부 저장 공간을 사용한다.
3) 외부 저장 공간 작업을 추가로 해야 한다.
② Open Addressing (개방 주소법)
- 추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다. Open Addressing을 구현하기 위한 대표적인 방법으로는 3가지 방식이 존재한다.
1. Lenear Probing (선형 탐사)
- 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
2. Quadratic Probing (제곱 탐사)
- 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.
3. Double Hashing Probing (이중 해싱 탐사)
- 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.
*Open Addressing 장점
1) 또 다른 저장공간 없이 해시테이블 내에서 데이터 저장 및 처리가 가능하다.
2) 또 다른 저장공간의 추가적인 작업이 없다.
*Open Addressing 단점
1) 해시 함수의 성능에 전체 해시테이블의 성능이 좌지우지한다.
2) 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해 두어야 한다.
(8) 충돌(Collision) 해결2 : 해시 함수 개선
1. 해시 함수 개선
2. 해시 테이블 저장공간의 확대
References
해시 테이블 - 위키백과, 우리 모두의 백과사전
ko.wikipedia.org
[자료구조] 해시테이블(HashTable)이란?
1. 해시테이블(HashTable)이란? [ HashTable(해시테이블)이란? ] 해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블이 빠른
mangkyu.tistory.com
Hash, Hashing, Hash Table(해시, 해싱 해시테이블) 자료구조의 이해
0_HJVxQPQ-eW0Exx7M.jpeg DATA들이 사용하기 쉽게 정리되어 있다. 자료구조는 도대체 무엇일까? 자료구조(Data-Structure)는 데이터들의 모임, 관계, 함수, 명령 등의 집합을 의미한다. 더 쉽게 표현하자면, 1)
velog.io
'컴퓨터 이론 > 자료구조 & 알고리즘' 카테고리의 다른 글
| [자료구조] 힙(Heap)에 대해서 알아보자. (0) | 2021.10.28 |
|---|---|
| [자료구조] 트리(Tree)에 대해서 알아보자. (0) | 2021.10.28 |
| [자료구조] 큐(Queue)에 대해서 알아보자. (0) | 2021.10.25 |
| [자료구조] 스택(Stack)에 대해서 알아보자. (0) | 2021.10.25 |
| [자료구조] Linked List에 대해서 알아보자. (0) | 2021.10.21 |