해시 테이블(Hash Table) : 키(Key), 값(Value)을 대응시켜 저장하는 데이터 구조
- 키를 통해 해당 데이터에 빠르게 접근 가능합니다.
해싱(Hashing) : 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정입니다.
키(key) : 해시 테이블 접근을 위한 입력 값입니다.
해시 함수(Hash Function) : 키를 해시 값으로 매핑하는 연산합니다.
해시 값(Hash Value) : 해시 테이블의 인덱스입니다.
해시 테이블(Hash Table) : 키-값(key-value)을 연관 시켜 저장하는 데이터 구조입니다.
해시 충돌 : 해시 함수를 통해 index값을 구했을 때 중복이 생기는 충돌입니다.
- 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우입니다.
* 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우입니다.
- 해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있습니다.
개방 주소법(Open Address) : 충돌시, 테이블에서 비어 있는 공간의 Hash를 찾아 데이터를 저장합니다.
- Hash와 Value가 1:1 관계 유지합니다.
- 비어 있는 공간 탐색 방법에 따라 분류합니다.
* 선형 탐사법(Linear Probing)
* 제곱 탐사법(Quadratic Probing)
* 이중 해싱(Double Hashing)
선형 탐사법(Linear Probing)
- 빈 공간을 순차적으로 탐사하는 방법입니다.
* 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사합니다.
문제점
- 일차 군집화 문제 발생
* 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생합니다.
제곱 탐사법(Quadratic Probing)
- 빈 공간을 n제곱만큼의 간격을 두고 탐사하는 방법입니다.
* 충돌 발생 지점부터 이후의 빈 공간을 n제곱 간격으로 탐사합니다.
문제점
- 일차 군집화 문제 일부 보완합니다.
- 이차 군집화 문제 발생 가능성이 생깁니다.
이중 해싱(Double Hashing)
- 해싱 함수를 이중으로 사용
* 해시 함수 1 : 최초 해시를 구할 때 사용합니다.
* 해시 함수 2 : 충돌 발생 시, 탐사 이동 간격을 구할 때 사용합니다.
장점
- 선형 탐사(Linear Probing), 제곱 탐사(Quadratic Probing)에 비해 데이터가 골고루 분포됩니다.
분리 연결법(Separate Chaining) : 동일한 버킷(bucket)의 데이터에 대해 연결 리스트, 트리 등의 자료구조를 활용해 데이터의 주소를 저장하는 것입니다.
- 해시 테이블을 연결 리스트로 구성시킵니다.
- 충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결 리스트를 이용하여 해당 테이블에 데이터를 연결합니다.
Perfect Hashing
Hash Table 메소드
put(K key, V value): 해시 테이블에 키(key)와 값(value)을 추가합니다.
get(Object key): 주어진 키(key)에 해당하는 값을 반환합니다.
remove(Object key): 주어진 키(key)에 해당하는 키-값 쌍을 해시 테이블에서 제거합니다.
containsKey(Object key): 주어진 키(key)가 해시 테이블에 있는지 여부를 반환합니다.
containsValue(Object value): 주어진 값(value)이 해시 테이블에 있는지 여부를 반환합니다.
isEmpty(): 해시 테이블이 비어있는지 여부를 반환합니다. size(): 해시 테이블의 크기(키-값 쌍의 개수)를 반환합니다.
clear(): 해시 테이블의 모든 키-값 쌍을 제거합니다.
keys(): 해시 테이블의 모든 키(key)를 포함하는 열거형(Enumeration) 객체를 반환합니다.
values(): 해시 테이블의 모든 값(value)을 포함하는 컬렉션(Collection) 객체를 반환합니다.
clone(): 해시 테이블을 복제하여 새로운 해시 테이블 객체를 생성합니다.
replace(K key, V value): 주어진 키(key)에 해당하는 값을 새로운 값(value)으로 대체합니다.
entrySet(): 해시 테이블의 모든 키-값 쌍을 포함하는 Set 객체를 반환합니다.
시간 복잡도(Time Table)
삽입(Insertion) : Best-case -> O(1), Worst-case -> O(n)
삭제(Deletion) : Best-case -> O(1), Worst-case -> O(n)
검색(Search) : Best-case -> O(1), Worst-case -> O(n)
Reference
- Introduction to Algorithms, 2nd Ed - Thomas H. Cormen.pdf
- 파이썬 알고리즘 인터뷰
'Computer Science > Data Structure' 카테고리의 다른 글
| 힙(Heap) (0) | 2023.04.18 |
|---|---|
| 연결 리스트(Linked List) (0) | 2023.04.18 |
| 배열(Array) (0) | 2023.04.14 |
| 큐(Queue) (0) | 2023.04.13 |
| 스택(Stack) (0) | 2023.04.13 |