[자료구조] HashTable 이란?

HashTable이란?

(key, value)로 데이터를 저장하는 자료구조 중 하나입니다.

 

왜 사용해?

빠른 속도로 데이터를 검색하기 위해 사용합니다.

왜 빠른지에 대해서 배열과 비교해서 설명하겠습니다.

[1,2,3,4,3] 에서 3의 갯수를 알려면 배열전부를 돌아서 찾아야합니다. 따라서 시간 복잡도는 O(n)이 됩니다.

그러나 해쉬테이블에 저장한다면?

key	value
1	1개
2	1개
3	2개
4	1개

var hashTable : [Int : Int] = [1 : 1,  2 : 1, 3 : 2, 4: 1]

key 값들 (1, 2, 3, 4) 중에 3을 찾아서 hashTable[3] = 2 를 찾는 것이 아니라

한방에 key값이 3인 곳을 찾아갑니다. 따라서 시간복잡도는 O(1) 입니다.

 

 

어떻게 빠르게 검색할 수 있지?

해쉬함수가 키값을 해쉬값을 변환시키고 이 해쉬값 자체가 bukets의 인덱스로 사용되기 때문에 한번에 접근할 수가 있습니다.

해쉬테이블은 평균 O(1)의 시간복잡도로 데이터를 조회할 수 있습니다. 하지만 데이터의 충돌이 발생한 경우 Chaining에 연결된 리스트들까지 검색을 해야 하므로 O(N)까지 시간복잡도가 증가할 수 있습니다.

 

언제, 왜 충돌이 발생하지?

• 서로 다른 입력(키값)이 해쉬함수를 돌린 값이 동일한 출력(value)으로 나올 때 : 키값이 문자열일 때 그 가짓수가 무한대 인 반면에 해쉬값은 정수개 만큼 제공을 못하기 때문이다
  
  
  
• 서로 다른 키값이 다른 출력으로 나오긴 했는데 해쉬테이블의 인덱스로 변환했더니 같을 때 : 해쉬테이블은 고정적인 메모리 영역을 잡는데 그 영역에서 나눠 담아야하기 때문에 같은 인덱스가 나올 수 있다.

 

 

충돌은 어떻게 해결해?

1. 체이닝(chaining)

해시 충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식이다. 

체이닝 설명

2. 개방주소법(Open Addressing)

해시 충돌이 일어나면 인접한 다른 버켓에 데이터를 삽입하는 방식. 체이닝과는 다르게 다른 버켓의 주소에 저장한다.

1. 선형 탐색(Linear Probing): 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.
2. 제곱 탐색(Quadratic Probing): 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)
3. 이중 해시(Double Hashing): 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함.

 

참고 및 출처
https://preamtree.tistory.com/20