[자료구조] Hash
[자료구조] Hash
[ Hash Table 이란? ]
key-value로 이루어진 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조
해시 테이블이 빠른 검색 속도를 제공하는 이유 -> 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문.
해시 테이블은 각각의 Key값이 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 됨.
(여기서 실제값이 저장된느 장소 -> bucket 또는 slot)
key는 hash 함수를 통해 hash로 변경이 되며 (이 과정을 Hashing이라고 함) hash는 value와 매칭되어 저장소에 저장됨.
< Hash Table Data Structure >
- key : 고유한 값이며, 해시 함수의 input이 됨. 최종 저상소에 저장되면 다양한 길이 만큼의 저장소를 구성해 두어야 하기 때문에 해시 함수로 값을 바꾸어 저장이 되어야 공간의 효율성을 추구할 수 있음.
- 해시함수 : key를 hash로 바꿔주는 역할. 다양한 길이를 가지고 있는 key를 일정한 길이를 가지는 hash로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와줌.
단, 서로 다른 key가 같은 hash가 되는 경우 해시충돌(Hash Colllision)이라고 한다. -> 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요!!- 해시(Hash) : Hash Function의 결과물, 저장소(buckey, slot)에서 값(value)과 매칭되어 저장됨.
- 값(Value) : 저장소(bucket, slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색. 접근이 가능해야 함.
< 장단점 >
장점
해시테이블은 Key-Value가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 검색의 과정에서 모두 평균적으로 O(1)의 시간복잡도를 가지고 있음.
단점
- 해시 충돌이 발생 (개방 주소법, 체이닝 과 같은 기법으로 해결해줘야함)
- 순서/관계가 있는 배열에는 어울리지 않음.
- 공간 효율성이 떨어짐. 데이터가 저장되기 전에 저장공간을 미리 만들어야 함. 공간을 만들었지만 공간에 채워지지 않는 경우 발생
- Hash fuction의 의존도가 높음. 해시함수가 복잡하다면 Hash를 만들어 내는데 오래 걸림. </br>
Direct-address table : 키의 전체 개수와 동일한 크기의 bucket을 가진 해시테이블
장점 : 키의 개수와 테이블의 크기가 같기 때문에 해시 충돌 문제가 발생하지 않음. 단점 : 전체 키의 개수만큼의 테이블 크기를 유지하는 것은 메모리 낭비일 수 있음.
-> 실제 키 개수보다 적은 해시테이블을 사용하기 때문에 해시 충돌이 발생할 수 밖에 없고, 해시 충돌을 해결하기 위해 다양한 방법들이 고안되었음.
해시 충돌
A,B 두가지 key가 hash function을 통해 얻은 Hash 값이 똑같을 때
Key-Value가 1:1로 매핑되어야 함
해결방법 1. Chaining
저장소(Bucket)에서 충돌이 일어나면 기존 값과 새로운 값을 연결리스트로 연결하는 방법
장점
- 미리 충돌을 대비해서 공간을 많이 잡아 놓을 필요가 없음. 충돌이 나면 그때 공간을 만들어서 연결해주면 됨.
단점
- 같은 hash에 자료들이 많이 연결되면 검색시 효율이 낮아짐. Open Addressing은 충돌이 일어나면 비어있는 hash에 데이터를 저장하는 방법이기 때문에 hash table은 hash와 value가 1:1 관계를 유지함.
1) 연결리스트를 사용하는 방식 (Linked List)
- 각각의 bucket들을 연결리스트 (Linked List)로 만들어 Collison이 발생하면 해당 bucket의 list에 추가하는 방식
- 삭제 또는 삽입이 간단
- 작은 데이터들을 저장할 때 연결 리스트 자체의 overhead가 부담
2) Tree를 사용하는 방식 (Red-Black Tree) 트리를 사용하는 방식은 메모리 사용량이 많음.
해결방법 2. 개방 주소법 (Open Addressing)
해시 충돌이 일어나면 다른 버킷에 데이터를 저장하는 방식 1) 선형탐색
- 해시 충돌시 다음 버킷에 저장하는 방법 2) 제곱 탐색
- 해시 충돌시 제곱만큼 건너뛴 버킷에 데이터를 저장하는 방법 3) 이중 해시
- 해시 충돌시 다른 해시함수를 한 번 더 적용한 결과를 저장
장점
- 체이닝처럼 포인터가 필요 없고, 지정한 메모리 외에 추가적인 공간이 필요 없음.
- 삽입, 삭제시 오버헤드가 적음
단점
- 최악의 경우 비어있는 bucket을 찾지 못하고 탐색을 싲가한 위치까지 되돌아 올 수 있음.
- 특정 위치에만 데이터가 몰리는 현상이 나타날 수 있음.