[알고리즘 스터디 with 케이시] 선형 자료 구조 - 해시 테이블

사물함의 각 칸에 이름과 번호가 있어서 바로 찾기가 쉽듯,

해시 테이블도 키를 인덱스로 변환하여 값을 넣는다.

정의

• 키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조
• 삽입은 O(1)이며 키를 알고 있다면, 삭제, 탐색도 O(1) 로 수행한다. 

 

Hash == 고기와 감자를 잘게 다져 요리한 것

키를 잘게 잘라 인덱스로 만들어 사용한다는 것이 비슷하다.

해시 함수는 입력 받은 값을 특정 범위 내 숫자로 변경하는 함수 

특별한 규칙이 있는 것은 아니다. 

해시 충돌 Hash Collision

해시 충돌이란, 키값을 인덱싱한 결과 서로 다른 키지만, 인덱스 값이 같은 경우, 해시 충돌이라고 한다. 

1. 선형 탐사법

충돌이 발생하면 옆으로 한 칸 이동한다. 

2. 제곱 탐사법

충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다. 

3. 이중 해싱

충돌이 발생하면 다른 해시 함수를 이용한다. 

4. 분리 연결법

버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다. 

사용처

학생 정보를 어떻게 관리 할 것인가?

링크드 리스트 탐색 - O(N)

배열 인덱스를 모를 경우 탐색 - O(N)

반면 해시 테이블을 이용하면 O(1) 에 찾을 수 있다. 

따라서 빠르게 값을 찾아야하는 경우 해시 테이블을 사용하는 것이 좋다. 

이름을 키로 하여 탐색과 삽입 삭제를 하면 수월하게 할 수 있다. 

스위프트에선, Set<>, Dictionary[:] 를 사용할 때 키로 Hashable 이 채택된 타입을 사용해야한다.