먼저, 해시 함수에 대해 알아보기 전에 해시에 대해서 알아보는 시간을 가져보겠습니다.
해시(Hash)
- 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것입니다.
- 해시 함수를 구현하여 데이터 값을 해시 값으로 매핑합니다.
Lion -> 해싱함수 -> 5
Tiger -> 해싱함수 -> 3
Dog -> 해싱함수 -> 2
...
Bird -> 해싱함수 -> 5 // Lion과 해싱값 충돌
위와 같이 데이터가 많아지면, 다른 데이터가 같은 해시 값으로 충돌되는 현상이 발생합니다.
이것을 'Collision' 현상이라고 부릅니다.
그래도 해시 테이블을 쓰는 이유는 뭘까요???
적은 자원으로 많은 데이터를 효율적으로 관리하기 위해서입니다.
하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 적은 메모리로도 프로세스 관리가 용이하기 때문입니다.
- 언제나 동일한 해시값 리턴, index를 알면 빠른 데이터 검색이 가능해집니다.
- 해시 테이블의 시간 복잡도 : O(1)
- ex) 이진 탐색 트리 : O(logN)
배열 : O(1) -> 배열은 메모리를 미리 할당 시켜두기 때문에 공간 효율 X
충돌 (Collision) 문제 해결 방법
1. 체이닝 : 연결 리스트로 노드를 계속 추가해나가는 방식 (제한 없이 계속 연결 가능, but 메모리 문제 )
아래 그림과 같음
2. Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용
( 해당 키 값에 저장되어 있으면 다음 주소에 저장 )
3. 선형 탐사 : 정해진 고정 폭으로 옮겨 해시값의 중복을 피함
4. 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시 값의 중복을 피함
해시 테이블 Hash Table
- 해시 함수를 사용하여 키를 해시값으로 매핑하고, 이 해시 값을 index 혹은 주소로 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조를 해시 테이블(Hash Table)이라고 합니다.
- 이 때 데이터가 저장되는 곳을 버킷(Bucket) 또는 슬롯(Slot)이라고 합니다.
- 해시 테이블의 기본 연산은 삽입, 삭제, 탐색입니다.
[참고자료]
https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/
반응형