key : value 시스템을 따르는 자료구조의 일종
개요
Hash Table은 내부적으로 배열을 사용하여 데이터를 저장한다.
때문에 빠른 검색 속도를 갖는다.
그러나 일반적인 배열과는 데이터를 다루는 방식이 다르다.
데이터를 저장하는 방법
key값에 특수한 알고리즘을 적용하여 고유한 인덱스를 생성하고 해당 인덱스에 value값을 저장한다.
예를 들어, key값으로 학번을 사용하고 value는 이름을 지정한다고 하자.
- 길이가 10인 배열
- 데이터 : 20221234: "홍길동"
- 알고리즘 : key%n (n=배열의 길이)
위와 같이 데이터와 알고리즘이 주어졌다고 했을 때,
key값인 20221234에 알고리즘을 적용해보면 4라는 고유의 인덱스 값이 생성된다.
그리고 배열의 4번째 인덱스에 "홍길동"이라는 value값이 저장된다.
Hash Function
고유한 값(인덱스)을 생성하는 함수
앞서 설명했던 특수한 알고리즘을 해시함수라고 한다.
해시함수의 로직은 하나로 정해져 있지 않고 설계하기 나름이다.
위의 예시는 간단하게 작성한 알고리즘이고 실제로는 더 정밀하게 작성해야 한다.
만약, 20221234를 저장한 후에 20221124라는 key값을 가진 새로운 데이터를 저장한다고 하자. 위의 해시함수를 적용하면 둘 다 동일하게 4라는 인덱스가 나오게 된다.
이 처럼, 해시함수는 서로 다른 key값을 가지고 있어도 같은 인덱스가 나오는 충돌 (Collision)이 발생할 수가 있다.
key와 인덱스가 1:1로 대응해서 충돌이 없으면 정말 좋겠지만 현실적으로 그런 해시함수는 구현하기가 불가능에 가깝다.
따라서, 해시함수는 충돌을 최소화하는 방향으로 설계해야 한다.
충돌 해결(Collision Resolution)
충돌을 완전히 없애는 것은 불가능하기 때문에 충돌이 발생했을 때 적절한 방법을 통해서 해결해주어야 한다.
넓게 보자면 2가지 방법이 존재 한다.
- Open Address 방식
- Separate Chaining 방식
Open Address
충돌이 발생하면, 비어있는 다른 슬롯을 찾아서 데이터를 삽입하는 방식이다.
순차적으로 슬롯 하나하나 확인하면서 비어있는지 확인하기 때문에 최악의 경우는 비어있는 슬롯을 찾지 못하고 탐색을 시작한 위치까지 돌아올 수도 있다.
탐색을 하는 방식도 여러가지가 있다
-
Linear Probing
충돌이 일어난 슬롯에서부터 한 슬롯씩 순차적으로 비어있는 슬롯을 찾을 때까지 탐색한다.
-
Quadratic Probing
충돌이 일어난 슬롯에서부터 1^2, 2^2, 3^2··· 슬롯씩 이동하며 비어있는 슬롯을 찾을 때까지 탐색한다. -
Double Hashing Probing
또 다른 해시함수를 적용해서 새로운 인덱스를 생성하는 방식
Separate Chaining
같은 인덱스를 가지는 여러 데이터를 하나의 슬롯에 또 다른 자료구조로 담는 방식
Open Address 방식에 비해 충돌 발생 빈도가 낮다.
크게 두 가지 자료구조로 담는다.
- 연결 리스트 (Linked List)
- 트리 (Red-Black Tree)
일반적으로 데이터의 개수가 적다면 연결리스트를 사용하고 그 외에는 트리를 사용한다.
동적 확장 (Resize)
Hash Table의 모든 공간이 사용중이라면 크기를 확장해야 한다.
근데 일반적으로는 모든 공간이 다 사용되기 전에 크기를 확장하도록 설계한다.
왜냐하면, Hash Table의 사용중인 공간이 점점 늘어남에 따라서 충돌 빈도 또한 증가하기 때문에 이를 줄이기 위해서 일정 개수 이상의 공간이 사용되면 자동으로 크기를 확장한다.
일정 개수 이상이라는 임계점은 퍼센트 단위로 설정하게 된다.
보통 0.5, 0.75 등등의 수치를 갖고 이 때 이 수치를 Load Factor라고 부른다.
참고
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#hash-table
