2023. 10. 10. 20:12ㆍ자료구조, 알고리즘
해시테이블이란?
해시테이블은 테이블과 해시 개념이 합친 것으로
테이블은 Key, Value가 쌍을 이룰 때, 데이터를 구분하기 위한 Key를 가지게 되고, Key는 데이터를 구분하기 위한 기준이 되어야 하기 때문에 유일 해야한다. 즉, Key는 중복되면 안된다.
해시 개념은 해시 함수와 해싱이 있는데, 해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 변환하는 함수이며, 해싱은 데이터를 이러한 해시 함수로 해시값(해시코드)로 변환하는 과정이다.
해시함수는 입력에 대한 결과가 항상 동일한 값이어야하고. 처리가 빨라야하며, 결과가 밀집도가 낮아야한다.
해시테이블은 Key, Value가 쌍을 이룰 때, 이 Key를 가지고 해시함수로 해시 코드로 변환하고, 이 코드는 고유한 인덱스로 작용하여 Key의 Index로 위치에 해당하는 Value에 접근, 검색, 추가, 삭제하는 테이블에 해시 개념을 더한 것이다.
해시테이블은 Key를 해싱하여 Index로 변환하고 그 Value에 접근하므로 O(1)로 매우 빠른 속도로 접근, 검색, 추가, 삭제에 시간 복잡도를 가지고있지만, 최악의 경우 O(n)만큼의 시간 복잡도를 가지게 된다. 이러한 경우 해시 충돌이 발생한 경우이다.
해시충돌
해시 충돌이란 서로 다른 Key값을 해시 함수로 해싱 했을 때 동일한 결과 값, 인덱스를 반환한 경우이다. Key는 데이터를 구분하기 위한 기준이기 때문에 중복 되면 안되기 때문에 이러한 해결 해주어야 한다.
해시충돌 해결방법
이러한 경우 개방주소법과 체이닝 방식을 가지고 해결할 수 있다.
개방주소법은 서로 다른 Key값에 대해 동일한 인덱스로 변환했을 때, 미리 들어온 Key가 있어 해당 위치(Index)가 사용 중이라면 뒤로 이동하며 사용 중이지 않는 위치로 이동한다. 삽입에 있어서는 해당 위치가 이미 사용 중이라면 빈 곳 즉 사용 중이지 않는 위치로 이동하고 그 위치에 삽입해 주고, 탐색과 삭제에 있어서는 해당 위치가 이미 사용 중이라면 탐색과 삭제할 요소와 동일한 Key를 찾을 때까지 뒤로 이동하며 찾는다. 추가로 해시테이블의 공간 사용률이 높을 경우 성능저하가 발생해 이 때는 크기를 늘리고 테이블 내의 모든 데이터를 재해싱한다.
체이닝 방식은 LinkedList와 트리 방식을 사용하는데 만약 서로 다른 Key값에 대해 동일한 인덱스로 변환했을 때, 삽입에 있어서 미리 들어온 Key가 있을 경우 해당 Key의 tail에 참조하는 방식을 사용하면 된다. 없었을 경우 head가 되고, 탐색과 삭제에 있어서는 해당 위치가 이미 사용 중이라면 그 위치에 뒤에 붙은 노드들을 head부터 tail까지 찾으며 탐색하고 삭제하는 방식이다.
'자료구조, 알고리즘' 카테고리의 다른 글
| 탐색 알고리즘 (0) | 2023.10.16 |
|---|---|
| 정렬 알고리즘 (0) | 2023.10.11 |
| 이진탐색트리 (0) | 2023.10.09 |
| 우선순위 큐 - Heap (0) | 2023.10.08 |
| 스택 vs 큐 (0) | 2023.10.07 |