1. hash table 이란 ?
key를 hash function을 통해 hash값으로 바꾼뒤
이 hash값을 index로 사용해 key - value 형식으로 저장하는 자료구조 입니다!
hash table은 순서없이 key - value로만 값을 저장하기 때문에 순서가 필요한 데이터에는 적합하지 않습니다!
타 자료구조에 비해 굉장히 빠른 속도로 삽입, 삭제, 탐색이 가능합니다.
2. hash table의 구성!
key
- 고유한 값이자, hash function의 input값이 되는 값입니다!
- key를 그대로 data의 key로 사용하면 key의 길이만큼 메모리 공간을 차지하기 때문에,
hash function을 통해 고정된 길이를 가지는 hash값으로 변환합니다!
hash function
- key를 고정된 길이의 hash값으로 변경해주는 역활을 하는 함수입니다!
- hash table에서는 key의 개수가 테이블의 크기보다 크기 때문에
서로 다른 key를 input값으로 넣어 함수를 실행 했음에도
output값인 hash값이 동일 한 경우가 경우가 생기는데 이를 해쉬 충돌(collision) 이라고 합니다. - 해쉬 충돌을 줄이기 위해서 좋은 hash function을 사용해야 합니다.
hash
- key를 hash function의 input으로 실행 했을 때 나오는 output입니다.
- value의 key가 됩니다.
value
- bucket 이라고 불리는 저장소에 저장되는 실질적인 값입니다.
- hash로 접근 가능합니다.
load factor
- 적재율이라고 불리며 bucket의 크기 대비 key의 개수를 나타내고 key의 개수 / table의 크기 로 구합니다.
- 보편적으로 기호 'α' 로 정의합니다.
3. hash table의 장점!
key - value의 1대1 매칭 구조이기 때문에
삽입, 삭제, 검색 모두 평균적으로 (충돌이 없는 경우) O(1)의 시간 복잡도를 가집니다.
즉 빠릅니다!!!
4. hash table의 단점!
데이터가 저장되기 전에 미리 공간을 만들어놔야 하므로
공간 효율성이 떨어집니다.
hash function이 복잡하다면 hash를 만들어내는데 시간이 많이 소모되므로
hash function의 의존도가 높습니다.
index를 hash function이 정하기 때문에 배열처럼 순차적인 index를 보장하지 않습니다!
순서를 보장하지 않습니다!
최악의 경우 ( 같은 인덱스에 모든 키값과 데이터가 저장된 경우 = 전부 충돌한 경우 )
O(key의 개수) 즉 O(n)의 시간 복잡도를 가집니다.
5. collision 발생시 해결방법!
1. Chaining
체이닝은 bucket에 충돌이 일어나면 연결리스트의 형태로 저장하는 방법을 말합니다.
그림과 같이 충돌이 일어나면 기존의 hash값에 해당하는 value와 충돌이 발생한 value를
연결리스트의 형태로 저장합니다.
1-1. Chaining의 장점
- 충돌을 대비하기 위한 bucket 공간을 미리 확보할 필요가 없으므로 상대적으로 메모리소모가 적습니다.
1-2. Chaining의 단점
- 하나의 bucket에 여러개의 자료들이 연결될수록 시간복잡도가 증가합니다.
- 연결리스트를 위한 추가적인 외부 메모리를 사용해야 합니다.
1-3. Chaining으로 충돌 처리된 hash table의 시간 복잡도
- α >= 1 입니다. ( 1개의 bucket에 최소 1개의 값이 저장됩니다. )
- linked list의 head에 value를 삽입하는 경우.
- head값 재설정에 대한 연산만 하면 되므로 O(1)
- linked list의 tail에 value를 삽입하는 경우.
- linked list의 모든 값을 지나서 tail에 접근해야 하기 때문에 O(α)
- 최악의 경우 1개의 hash의 linked list가 모든 value를 가지고 있을 수 있으므로 O(n)
- 탐색, 삭제하는 경우.
- linked list를 차례대로 탐색해야 하므로 O(α)
- 최악의 경우 1개의 hash의 linked list가 모든 value를 가지고 있을 수 있으므로 O(n)
2. Open Addressing (개방 주소법)
개방주소법은 hash에 충돌이 발생하면 주변에 비어있는 hash를 찾아 충돌 hash를 저장하는 방법입니다.
비어있는 hash를 찾는 탐사법에는 크게 3가지가 있습니다.
- 선형 탐사(Linear probing)
- 충돌이 발생한 hash를 기준으로 고정폭 만큼 건너뛰면서 비어있는 hash를 찾습니다.
- 특정 hash값의 주변 bucket이 전부 채워져 있는, 데이터가 밀집되는 현상인 clustering이 발생합니다.
- 제곱 탐사(Quadratic Probing)
- 충돌이 발생한 hash를 기준으로 n^2의 폭 만큼 건너뛰면서 비어있는 hash를 찾습니다.
- 선형 탐사에 비해 보다 넓은 기준으로 탐사하기 때문에 탐색, 삭제가 효율적일 수 있습니다.
- 초기 hash값이 같다면 제곱 탐사 역시 clustering 문제가 발생합니다.
- 이중 해싱(Double Hashing)
- 충돌이 발생하면 또 다른 hash function으로 처리하여 hash를 찾습니다.
- 기존 hash function은 최초 hash를 얻을 때 사용하고
나머지 하나는 충돌 발생 시 탐사의 폭을 얻기 위해 사용합니다.
- 최초 hash로 나온 값이 같더라도,
다른 hash function을 거치면서 각기 다른 탐사 폭이 나올 확률이 높기 때문에
여러 공간에 골고루 저장될 확률도 높아집니다.
- clustering 문제를 해결하기 위해 도입 되었습니다.!
2-1. Open Addressing의 장점
- 별도의 메모리 공간 없이 hash table 내에서 충돌에 대한 처리가 가능합니다.
- hash table의 특징인 key - value 1대1 매칭 구조가 유지됩니다.
2-2. Open Addressing의 단점
- 데이터가 늘어나는 만큼 bucket에 공간을 미리 확보해야 합니다.
- 충돌이 많이 발생할 수록 clustering으로 인해 시간복잡도가 증가합니다.
2-3. Open Addressing으로 충돌 처리된 hash table의 시간 복잡도
- α <= 1 입니다. ( 1개의 bucket에 최대 1개의 값이 저장됩니다. )
- 삽입, 삭제, 탐색 하는 경우.
- 모든 경우에서 대상이 되는 hash를 찾아가는 과정에 따라 시간복잡도를 계산합니다.
hash를 탐사하는 횟수가 많아질수록 시간복잡도가 점차 증가합니다.
- 충돌이 없는 최상의 경우 O(1)
- 충돌로 인해 탐사를 해야할 때 최악의 경우 O(n)
6. Resizing ( 테이블 크기 재할당 )
hash table은 유한한 공간에 무한한 데이터를 담기 위한 자료구조인 만큼 어느 순간 bucket이 꽉 차버릴 수 있습니다.
open addressing을 사용하는 경우에는 어느순간 table이 꽉 차서 데이터 저장을 못하게 되고,
chaining을 사용하는 경우에는 table의 빈공간이 적어지면 충돌이 발생할 수록 linke list의 길이가 길어져
hash table의 의미가 없어지게 됩니다..
때문에 hash table을 사용 할 때에는 데이터가 어느 정도 차오르면 테이블의 크기를 늘려줘야 합니다.
일반적으로 기존 table의 2배 크기의 새로운 table을 할당해서 기존 테이블 자료를 이동시키는 방법을 사용합니다.
반대로 table 크기에 비해 자료가 적다면 메모리의 낭비를 방지하기 위해 table의 크기를 줄이기도 합니다.
'Data Structure' 카테고리의 다른 글
| 자료구조 - 트리, 이진 트리, 이진 탐색 트리, 트리 순회, JS 트리 구현 (0) | 2022.08.03 |
|---|