Hash란?
- Key / Value 시스템
- 데이터를 관리/유지하는 자료구조
- 리소스 < 속도
똑같은 데이터가 올때마다 똑같이 분류하는 규칙성
데이터 -> 해시함수의 규칙 (ex. /100)으로 분류 -> 인덱스
>> 일련의 과정을 "해싱"이라고 부른다.
Hash 관련 용어 정리
- 해시테이블 : 데이터가 저장되는 장소이며 인덱스와 해시값으로 분류
- 인덱스(키) / 인덱스 컬럼 내에 있는 값은 버켓
- 해시값(밸류) / 해시값 컬럼 내에 있는 값은 엔트리
Hash의 특징
선형탐색(Array)은 O(n)의 시간 복잡도를 가지는 반면, Hash Table은 O(1)의 시간 복잡도를 가진다.
선형탐색과 같은 Array구조를 가지고 있는 Hash Table이 검색속도가 더 빠른 이유는 인덱스를 바로 찾아가기 때문인데
인덱스를 빠르게 찾는 방법이 Hash Function이다.
Hash Function은 찾고자 하는 Key를 숫자로 변환하고 이 숫자가 Index가 된다.
따라서,
데이터를 검색 할 때 해시함수를 거쳐서 인덱스를 뽑아내고 인덱스에 바로 접근하기 때문에 데이터 검색속도가 빠르다
하지만, 같은 인덱스에 다른 값이 들어가게 되면 충돌이 발생한다.
이를 해결하기 위해 아래와 같은 방법을 사용한다.
Hash 충돌(Collision) 해결 방법
Chaining
자료를 저장하고자 하는 인덱스에 값이 있다면 리스트와 같은 자료 구조를 통해 여러개의 값을 넣는다.
값을 List 형식으로 저장하고 인덱스에 접근후 저장된 List를 선형검색을 한다.
따라서, 충돌이 있을 경우 선형 검색 때문에 시간복잡도는 O(1)이 넘어갈 수 있다
하지만 한 인덱스에 너무 많은 값이 포함될 수 있다.
Linear Probing (선형 탐색)
선형 탐색의 원래 의미는 처음부터 끝까지 쭉 탐색하는 방법이다.
Chaining의 단점을 해결하기 위해 고안된 방법
해당 인덱스에 값이 있다면 비어있는 버켓에 데이터를 넣는 방법이다.
자리가 꽉 찼다면 테이블 크기를 늘리고 자료를 재정렬 하여 데이터를 삽입한다.