2024. 5. 11. 11:07ㆍPython Algorithm
Basic Concept/Intuition of HashMap
Definition
HashMap(해시맵, 혹은 해시테이블)은 key와 value를 매핑하여 저장하는 데이터 구조이다.
해시맵이 왜 이러한 데이터 구조의 형태를 띠고 있는지,
key, value, mapping이라는 세 개의 키워드를 중심으로 알아보도록 하자.
Basic Concept
알고리즘 문제들을 풀다 보니 iteration algorithm을 hashmap algorithm으로 바꾸어 사용하니 time complexity를 줄이는 데 상당히 줄어드는 경우를 많이 확인할 수 있었다.
그래서 그런지, 최신 프로그래밍 언어는 대부분 hashmap의 기능을 내장하고 있다.
세부적인 구현 방식은 모두 상이하지만 각 언어가 구현한 해시맵의 기본적인 작동 방식은 모두 유사하다.
key 와 value 는 비교적 이해하기 어렵지 않은 개념으로, 마치 사전과 같이 대응 관계를 통해 데이터를 저장하는 방식이다.
mapping의 경우, key와 value를 연결하는 '함수'와 같은 개념이다.
아래 사진을 참고하자.
파이썬의 경우 해시맵은 dictionary라고 하는 datatype으로 구현되어 있다.
아래는 dictionary를 사용하는 가장 기본적인 방식으로, 더 자세한 내용은 공식 문서를 참고하자.
# 딕셔너리 생성 및 키-값 쌍 추가
my_dict = {'apple': 1, 'banana': 2}
# 데이터 접근
print(my_dict['apple']) # 출력: 1
# 데이터 추가
my_dict['orange'] = 3
# 데이터 업데이트
my_dict['banana'] = 4
# 데이터 삭제
del my_dict['apple']
# 키 존재 확인
'banana' in my_dict # 출력: True
# 모든 키와 값에 대해 반복
for key, value in my_dict.items():
print(key, value)여기서 헷갈리지 말아야 할 점은 key와 hash code는 유사하지만 다른 개념이라는 것이다.
key를 입력받으면 파이썬은 자동으로 hash code를 생성하여(hash() 함수 이용) 데이터를 저장할 위치를 결정하고, 이를 통해 value를 저장한다.
여기서 우리는 파이썬에서 key가 immutable한 datatype이어야 하는 이유를 알 수 있다.
key가 mutable(변경 가능)하다면 변경 후 hash code를 통해 데이터를 검색할 때 원치 않는 데이터가 저장된 주소나 아무것도 저장되어 있지 않은 주소에 접근할 수 있기 때문이다.
Intuition & Questions
1. index를 통해 value에 접근하는 list 와 다른 점은 무엇인가?
인간은 classification을 통해 simplify하는 동물이고, 이 idea를 algorithm에 접목한 것이 hashmap이라는 생각이 든다.
key:value 와 같은 데이터 형식으로 이루어져 있다는 점은 동일하지만, 중요한 차이점은 mapping 함수에서 발생한다.
index의 경우, 단순히 순서라는 기준으로 데이터를 정렬하는 것이지만, hashmap의 경우 규칙(즉, 분류 기준)을 사용하여 데이터에 접근할 수 있기 때문에 데이터의 관리가 훨씬 용이하다.
예를 들어, list에서 특정 값을 찾기 위해서는 모든 element를 iterate하는 과정이 필요하고, 이는 O(n)의 time complexity가 필요하지만 dictionary에서는 단순히 key를 통해 접근하면 되기 때문에, hash function을 실행하여 hash code를 찾고 해당 코드에 대응하는 데이터의 주소값에 접근하는 과정에 필요한 시간만 소요될 것이다.
2. 데이터를 저장하면 저장할수록 키 또한 늘어날 텐데, 그러면 시간 복잡도가 증가하지 않을까?
해시 함수는 키를 최대한 균등하게 분포시키도록 설계되어있다.
저장된 데이터에 대한 버킷 수가 특정 값 이하로 떨어질 경우, 자동으로 리사이징을 진행하여 해시 테이블의 크기를 늘린다고 한다.
따라서 키의 증가가 자동적으로 시간 복잡도의 증가와 연관되어 있지는 않은 것이다.
3. 하나의 해시 코드에 매핑된 데이터는 많을 수 있지 않은가? 그런데 그 중 하나만 선택하고 싶은 경우 해시맵은 비효율적인 것 아닌가?
타당한 지적이다. 그러나 해시맵은 하나의 특정 값에 접근하는 기능을 위해 고안한 data structure은 아닌 것이다.
해시맵은 기본적으로 키에 대한 빠른 접근을 위해 설계되었으므로, 같은 해시 코드를 공유하는 여러 키 중 특정 하나를 선택하는 작업은 추가적인 비용을 요구할 수 있다.
Example
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagram_group = defaultdict(list)
for string in strs:
sorted_string = str(sorted(string))
anagram_group[sorted_string].append(string)
return anagram_group.values()
이 문제를 iteration으로 해결하기 위해서는, 각 요소를 iterate하며 이후의 elements와 anagram을 비교하는 과정이 필요했을 것이다.
groupAnagrams 함수를 실행하는 데 필요한 time complexity는 각각 O(n) 과 O(n^2)이 될 것이다.