해시

간단히 정리해 봅니다. ↘

 

해시 Hash?

임의의 길이의 데이터를 고정된 길이의 데이터로 만들어 주는 자료구조로 key와 value가 쌍을 이루는 구조이다.

swift에서는 대표적으로 Dictionary가 있다. Dictionary의 key를 이용해서 원하는 value를 한번에 조회 할 수 있다. 이때 key를 이용하여 한번에 조회 할 수 있게 해주는 것이 바로 해시이다.

Dictionary 형태를 보면 key는 Hashable한 타입만을 포함시킬수 있는데, 내부에서 이 key를 배열처럼 index 형태로 변환하여 값에 바로 접근 할 수 있게 해준다. 이 변환 작업을 해싱이라고 한다.

 

해싱 Hashing?

Dictionary의 key에 접근하여 value를 가져오는데에는 O(1)의 시간복잡도를 가진다. 이렇게 빠르게 원하는 값을 가져올 수 있는 이유는 key가 해싱을 통해 인덱스화 되기 때문이다.

이 해싱 작업은 해시 함수를 통해 이뤄지고, 이를 통해 인덱스화된 key와 value가 묶여 쌍을 만들면 (이 하나의 쌍을 slot 또는 bucket이라 부른다.) 해시테이블 내에 쌓이게 된다.

 

충돌 Collision?

해싱 과정에서 해시테이블에 이미 존재하는 인덱스를 반환 받게 될 수도 있다. 이미 존재하는 인덱스와 새로 반환 받은 인덱스가 동일한 현상을 충돌이라 한다.

충돌이 발생하면 크게 두가지의 해결 방법이 있다.

1. Chaining

• 동일한 버킷 뒤에 체인을 연결하여 데이터를 줄줄이 저장하는 방법
• 최악의 경우 데이터를 찾는데 O(n)의 시간이 걸린다
• 종류: 연결리스트, 트리

2. Open Addressing

• 저장해야하는 인덱스에 값이 있으면 다른 버켓에 저장하는 방법
• 다른 버켓을 찾아 저장하므로 테이블 확장이 필요할 수 있지만 구현이 간단하다.
• 종류: 선형 탐사, 제곱 탐사, 이중 해싱