Hash Table

🤓오늘의 공부 주제: Hash Table🤓

Q. Hash Table은 어떤 자료구조인가?

A. Hash Table은 효율적인 탐색을 위한 자료구조로써 key, value쌍의 데이터를 입력받는다. 해시 함수에 key값을 넣어 얻은 해시값 h(k)를 위치로 지정하여 key-value 데이터 쌍을 저장한다.

저장, 삭제, 검색의 시간복잡도는 모두 O(1)이다.
이때 좋은 해시 함수란 연산 속도가 빠르고 해시값이 겹치지 않는 것.

Q. Hash table에서 collision이 발생하면 어떻게 해결하나?

A.충돌이 발생할 경우 해결 방법에는 두가지가 있다. 첫째는 open addressing으로 미리 정한 규칙에 따라 해시 테이블의 비어 있는 슬롯에 값을 넣는다. 이때 빈 슬롯을 찾는 방법은 크게 linear probing, quadratic probing, double hashing이 있다.
두번째는 seperate chaining으로 linked list이용해서 충돌 발생시 노드를 추가해서 데이터를 저장한다.

여기서 잠깐!💡

open addressing이란?

open addressing 방식은 collision이 발생하면 미리 정한 규칙에 따라 hash table의 비어있는 slot을 찾습니다.

추가적인 메모리를 사용하지 않으므로 linked list 또는 tree자료구조를 통해 추가로 메모리 할당을 하는 separate chaining방식에 비해 메모리를 적게 사용

방법1) linear probing (선형 조사법)
충돌이 발생한 해시값으로 부터 일정한 값만큼 건너 뛰어 비어 있는 슬롯에 데이터를 저장.
방법2) quadric probing (이차 조사법)
제곱수로 건너 뛰어 비어 있는 슬롯을 찾는다.

충돌이 여러번 발생하면 여러번 건너 뛰어 슬롯을 찾는데 선형 조사법과 이차조사법의 경우 충돌 횟수가 많아지면 특정 영역에 데이터가 집중되는 클러스터링 현상이 발생하는 단점이 있고 그 경우 평균 탐색 시간이 증가한다.

방법3) double hasing(이중 해시)
위의 방법 1,2의 경우 탐사이동폭이 같기 때문에 클러스터링 문제가 발생할 수 있음. 따라서 클러스터링 문제가 발생하지 않도록 2개의 해시함수를 사용하는 방식을 이중해싱이라고 함. 하나는 최초의 해시값 얻을 때 사용, 또 다른 하나는 해시 충돌이 발생할 때 탐사 이동폭을 얻기 위해 사용.

Separate chaining이란?

Separate chaining 방식은 linked list(또는 Tree)를 이용하여 collision을 해결합니다. 충돌이 발생하면 linked list에 노드(slot)를 추가하여 데이터를 저장합니다.

• 삽입: 서로 다른 두 key가 같은 해시값을 갖게 되면 linked list에 node를 추가하여 (key, value) 데이터 쌍을 저장. 시간복잡도는 $O(1)$.

• 검색: 기본적으로 $O(1)$의 시간복잡도 이지만 최악의 경우 $O(n)$의 시간복잡도.

• 삭제: 삭제를 하기 위해선 검색을 먼저 해야하므로 검색의 시간복잡도와 동일. 기본적으로 $O(1)$이지만 최악의 경우 $O(n)$의 시간복잡도.

  worst case의 경우 n개의 모든 key가 동일한 해시값을 갖게 되면 길이 n의 linked list가 생성. 이 때, 검색의 시간복잡도가 $O(n)$.

출처 : 인프런 - 기출로 대비하는 개발자 전공면접 [CS 완전정복]