👩🏻‍💻기초지식/CS

[자료구조] 해시 테이블(Hash Table)

공대 컴린이 2023. 8. 25. 18:22
728x90

해시 테이블

https://en.wikipedia.org/wiki/Hash_table

 

해시테이블은 효율적으로 빠른 탐색을 하기 위한 자료구조로, key-value 쌍의 데이터를 입력받습니다. 해시 Function h에 key 값을 입력으로 넣어 얻은 해시값 h(k)를 위치로 지정하여 key-value 데이터 쌍을 저장합니다.

키는 무조건 존재해야 하며, 중복되는 키가 있어서는 안됩니다. 해시 테이블을 구성하고 있는 key-value 데이터를 저장할 수 있는 공간을 slot 또는 bucket이라고 합니다.

 

> 해싱함수

더보기
해싱 함수 h(k)
어떤 키 k에 대한 테이블 주소를 계산하기 위한 방법으로 주어진 키 값으로부터 레코드가 저장되어 있는 주소를 산출해 낼 수 있는 수식을 말한다.

해싱 함수 h를 이용하여 key-value를 index : h에 저장하는데, 이것을 "키 k값을 갖는 원소가 위치 h(k)에 hash 된다" 또는 "h(k)는 키 k의 해시값이다" 라고 표현합니다.

 

시간복잡도

저장, 삭제, 검색 : O(1)

그러나, collision으로 인해 최악의 경우 O(n)이 될 수 있다.

해시 테이블은 시간복잡도가 빠르지만, 데이터가 저장되기 전에 미리 (slot-bucket)을 확보해야 하기 때문에 공간 효율성은 떨어집니다.

 

Collision

해시 테이블에서 collision이란 서로 다른 key의 해시값이 똑같을 때를 말합니다. 즉, 중복되는 key는 없지만 해시값은 중복될 수 있는데 이때를 collision이 발생했다고 합니다.

이러한 collision이 최대한 적게 나도록 해시 함수를 잘 설계해야 하고, 어쩔 수 없이 collision이 발생하는 경우 Separate Chaining 또는 Open Addressing 등의 방법을 사용하여 해결해야 합니다.

 

해시 테이블에서 Collision이 발생하면 어떻게 되나요? 어떻게 해결해야 하나요?

콜리전이 발생한다면 Open Addressing 방식 또는 Separate Chaining 방식으로 해결할 수 있습니다.

 

Open Addressing 방식

https://namu.wiki/w/%ED%95%B4%EC%8B%9C

첫번째 Open Addressing 방식은 콜리전이 발생하면 미리 정한 규칙에 따라 해시 테이블에 비어있는 slot을 찾습니다.

추가적인 메모리를 사용하지 않으므로 링크드 리스트나 트리를 통해 추가적으로 메모리를 할당하는 Separate Chaining 방식에 비해 메모리를 적게 사용한다는 장점이 있습니다.

다른 관점에서는 무한정 저장할 수 있는 체이닝 방식과 달리, 전체 슬롯의 개수 이상은 저장할 수 없다는 한계를 가진다고 볼 수도 있습니다.

 

빈 slot을 찾는 방법은 크게 Linear Probing, Quadratic Probing, Double Hashing으로 나뉩니다.

 

Linear Probing(선형 조사법)은 충돌이 발생한 해시값으로부터 일정한 값만큼 건너뛰어, 비어있는 slot에 데이터를 저장하는 방법입니다.

 

Quadratic Probing(이차 조사법)은 제곱수로 건너뛰어 비어있는 slot에 데이터를 저장하는 방법입니다.


탐색(Probing)의 문제점과 해결방안

선형 조사법과 이차 조사법은 충돌 횟수가 많아지면 특정 영역에 데이터가 집중적으로 몰리는 클러스터링 현상이 발생한다는 단점이 있습니다. 클러스터링 현상이 발생하면 평균 탐색 시간이 증가하게 됩니다.

 

Double Hashing(이중해시)는 선형 조사법과 이차 조사법의 클러스터링 문제를 해결하기 위해, 2개의 해시함수를 사용하는 방법입니다. 하나는 최초의 해시값을 얻을 때 사용하고, 또 다른 하나는 해시 충돌이 발생할 때 탐사 이동폭을 얻기 위해 사용합니다.


Separate Chaining 방식

https://namu.wiki/w/%ED%95%B4%EC%8B%9C

 

두번째 Separate Chaining 방식은 링크드 리스트(또는 트리)를 이용합니다. 서로 다른 두 키가 같은 해시값을 갖게 되면 링크드 리스트에 노드인 slot을 추가하여 데이터를 저장하게 됩니다.

 

보통은 separate chaining 방식은 링크드 리스트로 데이터를 저장하지만, 콜리전이 많이 발생하여 링크드 리스트의 길이가 너무 길어지는 경우엔, 이진 탐색 트리(BST, Binary Search Tree) 자료구조를 사용하여 데이터를 저장하기도 합니다. 이진탐색 트리를 사용하면 최악의 검색/삭제 시간복잡도였던 O(n)을 O(log N)으로 낮출 수 있습니다.

 

시간복잡도

삽입 : O(1)

검색 : O(1), 최악의 경우엔 O(n)

삭제 : O(1), 최악의 경우엔 O(n)

최악의 경우는 n개의 모든 key가 동일한 해시 값을 갖게 되는 경우를 말합니다. 이땐 길이 n개의 링크드 리스트가 생성되어 검색의 시간복잡도와 삭제의 시간복잡도는 O(n)이 됩니다.

삭제를 위해선 결국 검색을 수행해야 하므로 삭제 시간복잡도는 검색 시간복잡도와 같습니다.

 

좋은 해시 함수의 조건은 뭔가요?

각 상황마다 좋은 해시 함수의 조건이 달라질 수 있지만 대략적인 기준은 연산속도가 빨라야 하고, 해시값이 최대한 겹치지 않아야 합니다.

 

해시 테이블 종류 1 - Direct-address Table (직접 주소화 테이블)

직접 주소화 테이블은 키 값을 주소로 사용하는 테이블입니다. 예를 들어 키 값이 100이라고 하면, 배열의 인덱스 100에 원하는 데이터를 저장합니다.

 

문제점

직접 주소화 테이블은 최대 키 값에 대해 알고있어야 한다는 점과, 최대 키 값이 작을 때 실용적으로 사용할 수 있다는 점, 키 값으로 다양한 자료형을 사용할 수 없다는 한계점이 있습니다. 또한 키 값들이 골고루 분포되어있지 않다면 메모리 낭비가 심합니다.

728x90