해시 테이블, Hash Table 의 장단점 및 한계

 

해시태그라 불리는 #

그렇다면 해시 테이블은 뭔지 알까?

수많은 자료 구조들 중 하나로 속도가 빠른 자료구조로 알려져 있다.

한 번 알아보자

 

---

 

해시 테이블은 

기본적으로 Key- Value 시스템을 가지고 있다.

key는 value를 찾는 수단이고

우리가 찾는 것은 value이다.

 

사전을 생각해보면 쉽다.

"배추" 의 정의는

배추를 찾아야 그 밑에 설명이 있다.

우리가 필요한 것은 배추라는 단어가 아니라 배추가 뭔지이다.

 

---

 

해시 테이블의 적합하지 않은 데이터들도 있다.

정렬된 데이터가 필요하거나, 멀티 미디어 데이터를 저장할 때

혹은 키의 길이가 길거나 가변적이어서 키에 대한 검색이 필요할 때

데이터의 키가 유일하지 않을 때

등이 있다.

 

---

 

해시 테이블은 O(1)의 시간복잡도를 가진다고 알려져 있다.

??

 

 

딱봐도 Array 같은데.. 어떻게 시간복잡도가 그렇게 낮지??

 

물론 내부적으로 배열로 이루어져있다.

다만 배열이 순차적인 인덱스에 데이터를 저장한다고 하면

해시 테이블에서는 해당 인덱스를 키 값과 해시 함수가 정한다는 특징이 있다.

 

즉, key 값을 hash function이 숫자로 바꾸어주고

해당 숫자가 바로 그 key 값에 해당하는 index가 되는 것이다.

 

key 값을 넣기만 하면 해당 인덱스를 바로 찾을 수 있으니

배열에서 메모리 접근 속도 O(1)과 같다고 생각하면 되겠다.

** 삽입/탐색/삭제 모두 O(1)을 가진다.

 

 

아니 그럼 배열을 왜쓰냐 무조건 얘 쓰면 되는데..?

혹시 캐시의 지역성 기억나나..?

연속적인 메모리를 참조하기에는 비효율적이다. 그럴 땐 차라리 배열이 훨씬 낫다.

또한 해시 함수의 역할이 중요한데.. 해시 함수를 잘 짜야.. 제대로 작동을 할 수 있다.

 

 

그리고 해시함수는 O(N)의 시간복잡도를 가진다.

????

위에서 상수시간이 가능하다고 했는데??

 

해시함수를 잘못설정했거나

버킷이 충분하지 않거나

그럴 경우 발생한다.

 

key 값을 이용하여 hash function을 거치고 난 후에 

다른 key지만 같은 인덱스를 가리키면 어떻게 하는가? 가 문제다.

이것을 Collision, 충돌이라고 하는데

충돌이 발생하면 충돌 시 알고리즘을 구현하는데

보통 해당 인덱스 + 1로 구현한다.

 

 

다시 말해서 

해당 인덱스에 2개를 저장할 수도 있지만

해당 인덱스 다음 인덱스에 저장할 수도 있다.

이걸 충돌 해결 방법이라고 하는데

이것도 해시 테이블의 성능에 지대한 영향을 끼친다.

 

만약 해시 함수를 설정을 잘못해서 자꾸 특정 인덱스가 많이 나온다?

충돌이 많이 발생한다?

해당 인덱스 주변에 데이터가 모여있다?

결국 O(N)에 가까워지는 것이다.

 

해당 인덱스를 가리키는 것은 O(1)이나

한 번에 찾지 못한다면

해당 인덱스 내의 데이터를 뒤지거나

주변 인덱스를 찾아봐야 하는 등

충돌 시 알고리즘을 제대로 짜야 O(1)에 가까운 성능을 발휘한다.

 

---

 

충돌 제거 기법에는 여러가지가 있는데

1. 연결리스트로 Chaining

2. Open Addressing 배열로 구현

-> 다른 버킷에 저장

3. Double Hashing, 두 개의 해시함수 이용

 

---

아래 글을 참고해도 좋다.

 

 

[문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - Hash, 해시 테이블 , 자료구조 [CPP

[컴퓨터(Computer Science)/자료구조(Data Structure)] - [C언어] 자료구조 - Hash 해시 ,해싱-1