해시테이블
해시함수
특정 값을 원하는 범위의 자연수로 바꿔주는 함수
해시함수의 조건
- 한 해시 테이블의 해시함수는 결정론적이어야한다.
- 결과 해시값이 치우치지 않고 고르게 나온다.
- 빨리 계산 할수 있어야 한다.
해시테이블
- 고정된 크기의 배열을 만든다.
- 해시함수를 이용해서 key를 원하는 범위의 자연수로 바꾼다.
- 해시함수 결과 값 인덱스에 key-value쌍을 저장한다.
충돌 (collision)
사용하고 있는 인덱스에 또 다른 키 밸류 쌍을 저장하는 것
Chaining
충돌이 일어나는 값들을 사슬처럼 묶는것
링크드 리스트를 통해 Chaining한 해시테이블 시간 복잡도
아래의 세연산은 모두 링크드 리스트의 탐색을 동반하기 때문에 O(n)의 시간 복잡도를 지닌다.
| 동작 (Operation) | 시간 복잡도 |
| 탐색 (search) | O(n) |
| 저장 (save) | O(n) |
| 삭제 (delete) | O(n) |
하지만 이는 모든 데이터가 한 인덱스 즉 인덱스에 있는 링크드리스트에 저장되는 경우이다.
⇒ 불공평하다!
⇒ 평균 시간 복잡도를 통해 불공평을 해소해보자!
우리는 모든데이터가 한 인덱스에 저장되는 경우를 생각해서 최악의 시간복잡도를 계산했다. 그렇다면 골고루 저장되면 시간 복잡도는 어떻게 될까?
키 밸류 쌍의 갯수(n) / 해시테이블이 사용하는 배열의 크기(m) 를 하면 한 인덱스에 들어가는 평균 링크드 리스트 길이를 구할 수 있다. 그렇다면 시간 복잡도는 O(n/m) 이라고 볼 수있다.
하지만 여기서 하나의 일반적인 해시테이블의 속성이 있는데 그것은 키밸류쌍의 크기(n)과 해시테이블이 쓰는 배열의 크기(m)이 사이즈가 비슷하거나 같다는 것이다. 왜냐면 데이터를 충분히 여유롭게 담을 수 있는 공간이 필요하기 때문이다.
⇒ 즉, m=n이라는 가정을 할수있고 O(1) 시간복잡도를 가진다고 말할 수있다.
그렇기 때문에 위의 시간 복잡도를 평균 시간 복잡도로 다시 표현한다면 아래와 같이 된다.
| 연산 (Operation) | 평균 시간 복잡도 |
| 탐색 (search) | O(1) |
| 저장 (insert) | O(1) |
| 삭제 (delete) | O(1) |
하지만 최악의 경우도 나올수 있기 때문에 정확하게 표현하자면 아래와 같다.
“해시 테이블 삽입, 삭제, 탐색 연산들은 최악의 경우 O(n)이 걸리지만, 평균적으로는 O(1)이 걸린다”
Open Addressing
충돌이 일어났을 때 빈 인덱스를 찾아 저장하는 방법
선형 탐사 (Linear probing)
충돌이 일어났을 때 빈 인덱스를 하나씩 순서대로 선형적으로 찾는 방법
제곱 탐사 (Quadratic Probing)
충돌이 일어나는 인덱스에서 제곱 수를 더해 빈 인덱스를 찾는 방법
Ex) 10(충돌)→ 11 → 15 → 24
Open Addressing한 해시테이블 시간 복잡도
삽입 탐색 삭제 연산은 탐사 연산을 포함 하기 때문에 탐사 연산의 시간 복잡도를 확인해야한다.
만약 빈 인덱스가 겹치는 인덱스 -1이라면 어떻게 될까? 아마 모든 배열의 인덱스를 다 탐사해야할것이다.
즉, 최악의 탐사 경우는 O(n)이 된다.
| 연산 | 시간 복잡도 (최악의 경우) |
| 삽입 | O(n) |
| 탐색 | O(n) |
| 삭제 | O(n) |
하지만 이는 빈 인덱스가 충돌 인덱스 -1 에 존재 할 때이다.
⇒ 불공평하다!
⇒ 평균 시간 복잡도를 통해 불공평을 해소해보자! 이를 해결하기 위해 load factor 부터 살펴보자
load factor
해시테이블에 얼마나 차있는지를 나타내는 변수
a=n/m
load factor를 가지고 평균 시간 복잡도를 구하면...
배열의 크기보다 많은 키 밸류쌍을 저장 할수 없기에 a<1이라고 가정할 수있다.
해시테이블에서 평균적으로 탐사를 해야되는 횟수는 1/1-a보다 적다(수학적 분석으로 인해)
⇒ 만약 load factor a가 0.9라면 (100칸 중 90칸을 키밸류가 차지) 10개보다 적은 인덱스를 확인하면 빈 인덱스를 찾을 수 있다.
그렇다면 0< a< 0.9같은 가정을 한다면 평균적으로 항상 10보다 적게 탐사 가능하다. 이러한 경우 시간 복잡도는 O(10) 즉, O(1)이된다.
| 연산 | 시간 복잡도 (평균) |
| 삽입 | O(1) |
| 탐색 | O(1) |
| 삭제 | O(1) |
이 또한 chaining과 마찬가지로
최악의 경우도 나올수 있기 때문에 정확하게 표현하자면 아래와 같다.
“해시 테이블 삽입, 삭제, 탐색 연산들은 최악의 경우 O(n)이 걸리지만, 평균적으로는 O(1)이 걸린다”