[알고리즘] 해시 맵(Hash Map)

해시맵(Hash Map)이란?

• 해시맵은 키-값(key-value) 쌍으로 데이터를 저장하는 자료구조이다.
• 해시 함수를 통해 키를 해시값으로 변환하고, 이 해시값을 인덱스로 사용하여 값을 빠르게 저장하거나 조회할 수 있다.
• 해시맵은 평균적으로 O(1)의 시간 복잡도로 데이터를 검색, 삽입, 삭제할 수 있다는 장점이 있다.

해시맵의 특징

• 빠른 검색: 키를 통해 값을 매우 빠르게 찾을 수 있다.
• 중복 불가: 키는 중복될 수 없다. 같은 키로 값을 저장하면 기존 값이 덮어써진다.
• 순서 보장 X: 대부분의 해시맵 구현체는 데이터의 저장 순서를 보장하지는 않는다.
  • 순서 보장이 필요한 경우엔 orderedDict 등 별도의 라이브러리나 작업을 해줘야 한다.

언어별 해시맵

• 자바스크립트에서의 해시맵
  • 자바스크립트에서는 객체(Object)나 Map 자료형을 해시맵처럼 사용할 수 있다.

// 객체를 이용한 해시맵 예시
const hashMap = {};
hashMap["apple"] = 3;
hashMap["banana"] = 5;
console.log(hashMap["apple"]); // 3

// Map 객체를 이용한 해시맵 예시
const map = new Map();
map.set("apple", 3);
map.set("banana", 5);
console.log(map.get("apple")); // 3

• 파이썬에서의 해시맵
  • 파이썬에서는 딕셔너리(Dictionary)가 해시맵 역할을 한다.

# 딕셔너리 예시
hash_map = {}
hash_map["apple"] = 3
hash_map["banana"] = 5
print(hash_map["apple"])  # 3

해시맵의 활용 예시

• 빈도수 세기: 문자열이나 배열에서 각 원소의 등장 횟수를 셀 때 자주 사용된다.
• 중복 체크: 이미 등장한 값을 빠르게 확인할 때 유용하다.
• 캐싱: 연산 결과를 저장해두고, 동일한 입력에 대해 빠르게 결과를 반환할 때 활용된다.

해시맵은 알고리즘 문제 풀이에서 매우 자주 등장하는 핵심 자료구조이다.
자바스크립트와 파이썬 모두 해시맵을 쉽게 사용할 수 있는 문법을 제공하므로, 다양한 문제에 적극적으로 활용하는 것이 좋다.