(key, value)로 데이터를 저장하는 자료구조 중 하나
데이터의 크기에 관계 없이 빠르게 데이터를 검색할 수 있다.
그래서 해시테이블의 평균 시간복잡도는 O(1)이다.
Hashing
임의의 길이의 값을 해시함수를 사용해 고정된 크기의 값으로 변환하는 작업
HashTable
그리고 HashTable은 이 해싱 작업을 사용하여 데이터를 저장하는 자료구조 이다.
Direct Address Table
키 값을 주소로 사용하는 테이블 키 값이 21이면 배열 인덱스 21에 원하는 데이터를 저장할 수 있다. 가장 간단한 형태의 해시테이블
Insert, Searching, Deletion 작업 모두에 O(1)의 시간 복잡도를 가진다.
단점
- 최대 키 값을 알고 있어야 한다.
- 최대 값이 작을 때 더 효율적이다.
- 최대 값과 총 레코드 수와 많이 다르면 메모리 공간 낭비가 일어 날 수 있다.
해시 값이 충돌
충돌이 발생하지 않는 해시 테이블의 탐색, 삽입, 삭제 연산은
O(1)의 시간복잡도를 가지나
충돌이 발생하면 O(k)까지 걸리게 된다.
이는 같은 인덱스에 모든 키 값과 데이터가 저장된 경우라
모든 알고리즘 수행 단계에서 충돌이 발생했음을 의미한다.
때문에 이 충돌을 최대한으로 줄여 연산속도를 빠르게 만드는 것이
해시테이블의 핵심이다.
충돌을 해결하는 방법
1.해시 테이블 구조 개선
1-1. Chaining
해시 테이블에서 충돌 발생시 충돌이 발생한 (데이터-키값)들을 동일한 버킷에 저장하는데
이 버킷내의 (데이터-키값)을 연결리스트 형태로 저장하는 방법이다.
1-2. Open Addressing
원래는 해시 함수로 얻은 해시 값에 따라 (데이터-키값)을 저장하나
동일한 주소에 다른 데이터가 있다면 다른 주소도 이용할 수 있게 하는 방법이다.
Open Addressing의 3가지 충돌 처리 기법
- 1-2-1. 선형 탐사
가장 기본적인 충돌해결기법,
충돌이 일어난 지점에서 바로 인접한 인덱스에 데이터를 삽입하기 때문에 데이터가 밀집되는 클러스터링 문제가 발생한다.
이로 인해 탐색과 삭제가 느려지게 되는 문제가 발생한다.
- 1-2-2. 제곱 탐사
충돌이 일어난 인덱스에서 제곱을 하며 탐사를 하는 방식으로
선형 탐사보다는 탐색과 삭제에 효율적일 수 있다. (더 폭넓게 탐사를 하니까!)
그러나 초기 해시값을 탐사할 경우에는 클러스터링 문제가 발생 할 수있다.
- 1-2-3. 이중 해싱
선형탐사와 제곱 탐사에서 발생하는 클러스터링 문제를 피하기 위해 도입되었다.
처음 해시 함수로는 해시값을 찾기 위해 사용되고,
두번째 해시 함수는 충돌이 발생했을 때, 탐사 폭을 계산하기 위해 사용된다.
🙄사담
지금까지 풀어본 해시 관련 코딩 테스트 문제들을 보면
딕셔너리를 활용하여 얼마나 빨리 값에 접근할 수 있는지를 보는 것 같았다.
코테에서 위에 기술한 지식까지는 사용되진 않는듯..?
references
1. Data Structure and Algorithms - Hash Table
https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm
2. [DS] 해쉬 테이블(Hash Table)이란?
https://baeharam.netlify.app/posts/data%20structure/hash-table
3. Hashing Data Structure
https://www.geeksforgeeks.org/hashing-data-structure/
