[edx] HashMap

Hyeon Soo·2022년 5월 20일

1. 개요

Map은 key-value짝의 모음으로 이루어진 자료구조이다. 탐색을 지원하고, 순서가 없다는 특징을 가지고 있다.
개별 key는 유일해야하고, 변형도 불가능해야하지만, value는 동일할 수 있다.
HashMap은 array를 기반으로 하는 자료구조이며, 특정 index에 바로 접근하는 시간 복잡도가 항상 O(1)임을 이용하여 탐색을 효율적으로 수행하기 위한 자료구조이다. 특정 key를 hashing하여 나온 값을 index로 하여 array에 저장한다면, 특정 key를 입력하면 데이터에 바로 접근할 수 있음을 이용한 것이다.

Key를 hashing하는 과정에서, 도출한 index가 겹칠 수 있다. 이런 경우, 서로 다른 key는 독자성을 가져야하는 원칙을 어긴다. 이렇게 index가 겹치는 것을 collision이라고 부른다.
이를 해결하기 위한 방법들은 크게 두 분류로 나눌 수 있는데, 충돌한 key들을 동일한 장소에 보관하면 closed addressing, 다른 장소에 보관하면 open addressing이라고 부른다.
Closed addressing방법 중 가장 단순한 방법은 external chaining이다. 이는 array에 value를 보관하는 것이 아니라, array에 linkedlist를 보관함을 통해 하나의 index에 여러 value를 보관할 수 있도록 하는 방법이다.
이 경우 충돌이 얼마나 일어나든 상관이 없지만, 탐색의 효율성을 담보하기 위하여 주기적으로 resize를 해주어야한다.
Open addressing의 방법은 probing이 있다. Probing은 다시 linear probing과 quadratic probing으로 나눌 수 있다.
Probing의 요체는 만약 충돌이 일어나면, 비어있는 다른 자리를 찾아 데이터를 삽입하는 것이라 할 수 있다. Linear probing은 index를 1씩 더해가며 빈 자리를 찾고, quadratic probing은 제곱해가면서 찾는다.
한편, 충돌이 발생할 경우, 특정 값을 더하는 등의 방법을 수행하고 추가로 hashing을 처리하는 방법도 존재한다. 이를 double hashing이라고 하며, open addressing의 일종이다.

이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.