HashMap이란
C++에서 std::unordered_map으로 알려진 HashMap에 대해 알아보겠습니다.
Map 자료구조
우선 std::map의 기본 구조 부터 알아봅시다. Key와 Value의 묶음(내부적으로 std::pair를 사용하고 있습니다.)으로 구성된 Tree 자료 구조입니다. HashMap 또한 Key와 Value의 묶음을 사용하고 있습니다.
전체 구조 이미지는 충돌 해결(Collision resolution)에서 보실 수 있습니다.
Hash 함수란
입력한 임의의 데이터를 고정된 길이(크기)의 데이터로 변환하는 함수를 말합니다. Hash 함수를 통해 얻어진 결과를 Hash, Hash 값, Checksum 등으로 부릅니다.(이 글에서는 Hash 값으로 부르겠습니다.) 예를 들어 int 타입의 10을 MakeHashStringByInt()에 입력하면 aqdz9081와 같이 8자리 문자열로 변환할 수 있습니다.(다른 경우도 마찬가지입니다.)
해쉬 함수의 간단한 형태
Hash Table
HashMap(std::unordered_map)은 Hash 값을 Key로 씁니다. 그리고 Tree 구조가 아닌 Hash Table 구조로 구성되어있습니다.
Hash Table은 버켓(Buket)들로 구성된 공간입니다. 버켓은 둘 이상의 슬롯(Slot)으로 구성될 수 있습니다. Key를 사용해 Hash Table에 삽입, 삭제, 탐색 등을 수행하는 구조입니다.
충돌 해결
HashMap은 Hash 함수에 의존하기 때문에 Hash 값의 중복(일반적으로 충돌)이 발생할 수 있는 근본적인 문제를 가집니다. 이를 해결하기 위해 여러 방법이 있습니다만 이 글에서는 체이닝(Chaining) 혹은 Separate chaining으로 알려진 방법을 사용하겠습니다.
Separate chaining
해쉬맵 전체 구조(Chaining으로 충돌을 해결). 출처: 위키백과
Separate chaining은 버켓이 Key 그리고 포인터 하나를 가집니다. 포인터는 엔트리(Entry)를 가리킵니다. 엔트리는 포인터, Key 데이터(Hash 값이 되기 전의 데이터) 그리고 Value에 해당하는 데이터를 가지고 있습니다. 엔트리의 포인터는 Hash 충돌이 있을 경우 다른 엔트리를 가리키게 됩니다.
Entry 구조(코드에서는 Node로 표현함)
HashMap
위에서 구현한 Hash 함수와 Entry(Node)를 사용한 HashMap의 전체 구조를 간략하게 코드로 구현하면 아래와 같습니다.
마치면서
구현한 해쉬맵 프로젝트는 이곳에서 확인하실 수 있습니다.
해쉬맵에서 필요한 간단한 기능들을 구현했으니 확인해보세요