1. 해시 테이블
- 해시 테이블을 이용하면 key-value 데이터를 저장할 수 있다.
- 해시 테이블에는 데이터 간 순서 관계를 나타낼 수 없다.
- 해시 함수는 특정 값을 넣었을때 원하는 범위의 자연수를 리턴하는 함수다.
- Direct Access Table을 이용하면 key - value 데이터를 시간 효율적으로 저장하고 찾을 수 있다.
- 해시 함수는 원하는 범위의 자연수를 빠르게(으로) 리턴하면 좋다.
2. 해시 테이블 충돌과 Chaining
- 충돌은 해시 테이블에서 한 인덱스에 두 개의 key - value 쌍을 저장해야 되는 경우이다.
- 충돌이 일어나면 해시 테이블을 제대로 사용하기 위해 Chaining이나 Open addressing 등을 이용해 충돌을 해결해야 한다.
- Chaining을 이용하는 해시 테이블이 사용하는 링크드 리스트가 가장 긴 경우는 모든 key - value 쌍이 하나의 인덱스에 저장됐을 때다.
- Chaining을 이용하는 해시 테이블의 모든 연산들은 최악의 경우 가 걸린다.
- Chaining을 이용하는 해시 테이블의 모든 연산들은 평균적으로 이 걸린다.
3. Open addressing
- Open addressing을 이용하면 충돌이 일어났을 경우 한 인덱스에 여러 개의 key - value 데이터를 저장하는 게 아니라, 저장할 수 있는 다른 인덱스를 찾아서 저장하는 방법이다.
- Open addressing을 사용하면 빈 인덱스를 어떻게 찾을지, 선형 탐사 같은 탐사 방법을 정해야 된다.
- Open addressing의 시간 복잡도 분석할 때는 load factor, 해시 테이블이 얼마나 차 있는지가 중요하다.
- Open addressing을 이용하면 해시 테이블의 모든 연산들을 평균적으로 이 걸린다.
- Open addressing을 이용하면 해시 테이블의 모든 연산들은 최악의 경우 이 걸린다.
'Algorithm > 자료구조' 카테고리의 다른 글
| [추상 자료형] 파이썬 자료형 잘 고르기 (0) | 2023.08.07 |
|---|---|
| [추상 자료형] 파이썬 자료형 주요 시간 복잡도 정리 (0) | 2023.08.07 |
| [링크드 리스트] 링크드 리스트 정리 (0) | 2023.08.03 |
| [해시 테이블] 파이썬 hash 함수 (0) | 2023.08.03 |
| [해시 테이블] 해시 함수 (0) | 2023.08.03 |
