[자료 구조] 해시맵(HashMap)이란

안녕하세요! 오늘은 비선형 자료 구조인 해시맵에 대해서 공부해보겠습니다.

• 파이썬을 주로 사용하셨다면 dict, golang을 주로 사용하셨다면 map, 자바를 주료 사용하셨다면 HashTable로 익숙하실거에요!

간단한 알고리즘 문제들은 해시맵을 사용하는 것만으로도 해결할 수 있는 경우가 많으니 이 참에 공부해봐요 ㅎㅎ

---

해시맵이란

해시맵은 대표적인 비선형 자료 구조로 키-값 쌍으로 데이터가 저장되며, 조회 속도가 빠르다는 장점이 있습니다.

하지만 데이터의 순회가 까다롭고, 내부적으로 사용되는 해시 함수의 성능에 영향을 많이 받는다는 단점도 있습니다!

 

빠른 조회 속도

해시맵의 조회 속도가 빠른 이유가 뭘까요?키값을 이용해서 데이터의 메모리 주소를 바로 구할 수 있는 해시 함수 덕입니다.

 

해시맵에 키-값 쌍을 추가하려고 하면, 해시 함수를 이용하여 키의 해시값을 구합니다.이렇게 구한 해시값을 이용해서 해시맵에 데이터를 저장하는 것이죠.

 

그렇다면 역으로 데이터를 조회할 때는 주어진 키의 해시값을 구해서 접근하면 되겠죠?

간단하게 살펴보는 해시맵에 데이터가 저장되는 과정

 

해시 충돌 처리

여기서 질문 하나가 떠오르지 않으세요?

혹시 hash 함수가 다른 두 키에 대해서 동일한 주소를 반환하면 어떡하죠?

이를 해시 충돌(hash collision)이라고 표현하는데요.해시 충돌을 해소하는 방법으로는 대표적으로 1) Chaining, 2) Open Addressing 들이 있습니다.

 

1) Chaining을 해시 충돌이 발생한 데이터에 대해서 추가적으로 메모리를 할당받아서 관리합니다.

리스트를 추가해서 해시 충돌이 발생한 데이터들을 관리합니다.

 

2) Open Addressing은 추가적인 메모리 할당 없이 기할당받은 메모리를 활용하는 방법입니다.

 

충돌이 나는 주소에서 적당히(?) 먼 곳에 할당합니다.

---

해시맵에 대해서 공부해봤는데 어떠신가요?

Chaning, Open Addressing들의 상세 구현 방법을 살펴보면 흥미로운 부분이 많은데 다음에 공부해보는 것은 어떨까요ㅎ

부족한 부분 알려주시면 보완하도록 하겠습니다! 같이 열심히 공부해봐요 :)