[Hash] 해시 기반 자료구조

728x90

Hash 

자바스크립트로 알고리즘 문제를 풀다 보면 Object, Map, Set과 같은 해시 기반 자료구조를 자주 만나게 됩니다. 이들은 모두 내부적으로 해시 테이블(Hash Table) 구조를 기반으로 하며, 빠른 탐색, 삽입, 삭제(O(1)) 성능 덕분에 다양한 문제 해결에 활용됩니다.

이 글에서는 자바스크립트에서 자주 쓰이는 세 가지 해시 구조(해시오브젝트(Object), 해시맵(Map), 해시셋(Set))의 개념과 차이점, 사용법, 그리고 알고리즘 문제 적용 예제를 함께 정리해보겠습니다.

 

---

1.  해시 구조란?

해시 테이블(Hash Table)은 데이터를 키(key)를 해시 함수로 변환하여 특정 위치에 저장하는 자료구조입니다. 이 방식 덕분에 특정 데이터를 매우 빠르게 찾을 수 있습니다.

자바스크립트에서는 다음 세 가지 주요 객체가 이 구조를 기반으로 작동합니다:

• Object : 가장 기본적인 키-값 저장소
• Map : ES6에서 추가된 확장 가능한 키-값 저장소
• Set  : 고유한 값만 저장하는 컬렉션

// Object 예시
const obj = {};
obj["apple"] = 3;
console.log(obj["apple"]); // 3

// Map 예시
const map = new Map();
map.set("apple", 3);
console.log(map.get("apple")); // 3

// Set 예시
const set = new Set();
set.add("apple");
set.add("banana");
set.add("apple"); // 중복은 무시됨
console.log(set.has("apple")); // true
console.log(set.size); // 2

 

---

2.  각 자료구조의 개념과 사용법

a.  Object - 전통적인 해시 기반 키-값 저장소

• 키는 문자열 또는 심볼만 허용
• 값은 자유롭게 저장 가능
• 반복 및 사이즈 측정이 제한적

const obj = {};
obj["apple"] = 3;
console.log(obj["apple"]); // 3

b.  Map - 키에 제한이 없는 해시맵

• 키로 모든 타입 사용 가능 (숫자, 객체 등)
• 삽입 순서 유지, 반복에 강함
• size 속성으로 항목 수 확인 가능

const map = new Map();
map.set("apple", 3);
map.set(42, "answer");
console.log(map.get("apple")); // 3
console.log(map.get(42)); // answer

c.  Set - 고유한 값의 집합, 해시셋

• 값만 저장 (키 없음)
• 중복된 값은 자동으로 제거됨
• 존재 여부 확인이 매우 빠름

const set = new Set();
set.add("apple");
set.add("banana");
set.add("apple"); // 중복은 무시됨
console.log(set.has("apple")); // true
console.log(set.size); // 2

 

---

3.  Object vs Map vs Set 비교

항목	Object	Map	Set
키 타입	문자열/심볼만 가능	모든 타입 가능	(키 없음) 값만 저장
값 저장 구조	key → value	key → value	value (고유)
중복 허용	키 중복 불가	키 중복 불가	값 중복 불가
삽입 순서 유지	일부 구현체만 유지됨	유지됨	유지됨
반복 방법	for...in 등	for...of, forEach	for...of, forEach
사이즈 확인	Object.keys().length	map.size	set.size
사용 예	기본 키-값 저장	복잡한 키-값 매핑	중복 제거, 존재 확인

 

---

4.  해시맵(HashMap) 예제 - 두 수의 합 (Two Sum)

문제 설명

정수 배열 nums와 정수 target이 주어질 때, 합이 target이 되는 두 수의 인덱스를 반환하시오.

해시맵(Map) 풀이

function twoSum(nums, target) {
  const map = new Map();

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];

    if (map.has(complement)) {
      return [map.get(complement), i];
    }

    map.set(nums[i], i);
  }

  return [];
}

동작 원리

• 현재 숫자의 보충 값(target - 현재 숫자)이 맵에 있는지 확인
• 있다면 두 수의 인덱스를 반환
• 없다면 현재 숫자와 인덱스를 map에 저장

→  시간 복잡도: O(n) 으로 매우 효율적

 

---

5.  해시셋(Set) 예제 - 배열 중복 제거

const nums = [1, 2, 2, 3, 4, 4, 5];
const unique = [...new Set(nums)];
console.log(unique); // [1, 2, 3, 4, 5]

활용 가능 예제들

• 중복 탐색 : containsDuplicate
• 집합 연산 : intersection, union
• 방문 체크 : DFS/BFS 중 방문 노드 추적 등

 

---

6.  해시 기반 자료구조가 빛을 발하는 문제 유형

자바스크립트에서 해시 테이블 구조를 기반으로 하는 Object, Map, Set은 다음과 같은 알고리즘 문제에서 매우 강력한 성능을 발휘합니다. 각각의 구조는 상황에 따라 다르게 활용되며, 특정 유형의 문제에 특히 효과적입니다.

a.  중복 탐색

• Set을 활용하면 중복 제거 및 존재 여부 확인을 O(1)로 처리 가능
• Object나 Map을 활용해 등장 횟수를 세는 방식도 자주 사용됨
• 예시 문제 : containsDuplicate, isAnagram

b.  누적합 / 부분합 추적

• 누적합을 저장할 때 Map을 활용해 특정 합이 몇 번 등장했는지를 기록
• 키를 누적합 값, 값을 등장 횟수로 저장하면 빠른 계산 가능
• 예시 문제: subarraySum, countSubarraysWithSum

c.  빈도수 계산

• Object나 Map을 사용하여 값을 키로, 등장 횟수를 값으로 저장
• 정렬 또는 정렬 없이 우선순위 큐와 함께 자주 사용됨
• 예시 문제 : topKFrequent, majorityElement

d.  문자열/패턴 매핑

• Map으로 문자 간 일대일 대응 관계를 기록
• Set을 함께 사용하면 중복 매핑 여부를 체크할 수 있음
• 예시 문제: wordPattern, isomorphicStrings

 

---

7.  요약

• 자바스크립트에서의 해시 기반 자료구조는 Object, Map, Set 세 가지로 나뉘며, 모두 내부적으로 해시 테이블을 기반으로 작동합니다.
• 이 구조들은 평균적으로 O(1)의 검색, 삽입, 삭제 성능을 제공하여 다양한 알고리즘 문제에서 필수적으로 활용됩니다.
• Set은 중복 제거 및 존재 확인, Map은 복잡한 키-값 매핑, Object는 가벼운 빈도수 계산 등에 효과적입니다.
• 해시 구조는 특히 중복 탐색, 부분합 추적, 빈도수 계산, 패턴 매핑과 같은 문제 유형에서 매우 유용합니다.

함께 보면 좋은 자료

외부 사이트 : 

• MDN Web Docs - Object
• MDN Web Docs - Map
• MDN Web Docs - Set

블로그 글 :

[Object] 자바스크립트의 객체

[Map] 객체보다 더 똑똑한 자료구조

[Set] 중복 없는 데이터 관리하기

 

---

반응형