Hash 1 - 기본 개념과 적용

TLDR: 키가 필터링을 수행할 수 있도록 키-값 저장 구조를 만든다

이번 글에서는 프론트엔드 알고리즘 테스트에 자주 활용되는 해시를 알아본다. 기본 개념과 JS에서 활용하는 방법을 위주로 살펴본다. 이 글은 책을 통해 알게 된 개념과 스스로 학습하는 과정을 기록했다. 특히 JS부터 추론 과정을 글로 표현하는 것에 집중했다.

Hash?

무엇?

키-값value으로 저장하는 자료 구조이다.
키와 값이 일대일로 대응한다.

어떻게?

기본 원리는 동일하다. 키를 해시 함수로 변환하여 인덱스를 얻는다.
저장 공간 해당 인덱스에 값을 저장한다.
해시 함수 구현 방법에 따라 키->인덱스를 만드는 방법이 달라진다.

왜?

핵심은 효과적인 탐색이다. 이유는:

- 키만 알면 값을 바로 얻을 수 있다.

- 0~N의 숫자 인덱스보다 해시 키가 인지하기 쉽다.

언제?

데이터를 키-값 구조로 만들어 효과적인 탐색할 때.
예를 들어 탐색을 O(n)에서 O(1)로 만들 수 있을 때.
실생활에서는 해시 함수의 단방향성으로 보안에 활용된다.

---

특징

간략히 특징을 정리하자면,

1. 키를 인덱스로 활용하려면 적절한 변환 과정(=해시 함수)가 필요하다.

2. 단방향이다. 값을 통해선 키를 찾을 수는 없다. 오로지 '키'를 해시 함수에 넣어야 값을 얻을 수 있다.

3. 키 자체가 인덱스로 기능하여, O(1)로 값을 얻을 수 있다.

해시 함수 종류

해시 함수를 구성하는 여러 전략이 있다. 책에 언급된 모듈러 연산(%)을 중심으로 알아본다.

1. 나누기 : h(x) = x mod K

   • 값 x를 소수 K로 모듈러 연산한다.

   • x의 인덱스는 0~K-1까지 갖을 수 있다.

   • 이 때 소수 K가 해시 전체 크기가 된다. 즉 크기 제한이 생긴다.

2. 곱하기 : h(x) = (((x A) mod 1) M)

   • 나누기의 크기 한계를 개선한다.

   • 값 x에 황금비 A를 곱한다

   • -> 이후 모듈러 연산으로 1을 제외한 소수 자리만 얻은 뒤

   • -> 이 수를 테이블 크기 M에 곱한다.

   • 이때 인덱스는 0~M-1에 배치된다.

3. 문자열 해싱

   • 키 x가 문자열일 때도 해싱을 적용한다.

   • 각 문자를 숫자로 변환하는 해시함수를 사용한다.
     (이 부분은 더 깊은 내용을 다룬다. 그러나 주제에서 벗어나므로, 원문 참조.)

충돌 문제

해시 함수의 문제 상황

1. 해시 함수가 동일한 키(인덱스)를 반환할 때 충돌이 생길 수 있다.

2. 값이 저장되는 해시의 크기 제한이 있다.

모두 저장하려는 키-값이 손상될 수 있는 충돌 문제를 갖고 있다.
문제 해결 위해 다음과 같은 방법들이 제시된다.

• 체이닝: 중복된 인덱스가 생성됐을 때, 그 인덱스에 새로운 값을 다음 노드로 추가한다. (연결 리스트)

  • 탐색 성능 저하 : 중복된 인덱스에서 키에 해당하는 값을 찾을 때까지 연결 노드의 next를 확인해서 O(n)이 된다.

  • 공간 활용성 저하 : 해시에 빈 공간이 있어도 활용하지 못하고 같은 인덱스에 값을 저장한다.

• 개방 주소법: 충돌 시 빈 공간에 값을 저장한다.

  • 선형 탐사 : 충돌 시 특정 간격으로 이동하며 빈 공간을 찾아 저장한다. 이 때 간격 배치로 인해 값이 특정 위치에 몰리는 클러스터가 발생할 수 있다.

  • 이중 해싱 : 해싱 함수를 2개 작성한다. 첫 함수는 값을 키로 변환하고, 두번째는 충돌 발생 시 이동하는 로직으로 구성한다.

---

JS에서 해시

JS 알고리즘 코딩 테스트라는 맥락에선 해시의 효율적인 탐색에 집중한다. key-value의 일대일 대응으로 가능한 O(1) 탐색이 해시 사용의 목적이다. 이어지는맥락에서 '해시'는 셋 모두를 가리킨다. (유사한 구조임에는 인지)

JS는 해시와 유사한 자료구조를 제공한다. 바로 객체(Object)와 Set, Map이다. 그럼 이 세가지 중에서 어떻게 적절한 사용 케이스를 구분할까?

JS 유사 해시 객체 특징

일반 객체(Object)

• object.key 또는 object[key] 로 값을 조회한다.

• 이때 키는 문자열이어야 한다.
  Set

• 중복값이 없는 일급 객체이자 iterator이다.

• Set.has(key) 로 저장 여부를 확인하여 boolean을 반환한다.

• add(x), delete(x) 로 수정할 수 있으며, values(), keys() 등을 활용해 순회할 수 있다.

• intersection(), isSupersetOf(), isSubsetOf()와 같은 집합 관계를 확인할 수 있는 메서드를 제공한다.
  Map

• 키-값으로 구성된 일급 객체이며, Set과 달리 키와 값을 구분하여 저장한다.

• Map의 키는 모든 자료형이 가능하며, 중복된 키에 값을 저장하면 이전 값을 덮어쓰기 한다.

• .get(key) 를 사용해 값을 얻고, .has(key), .set(key, value), .delete(key) 등의 메서드를 제공한다.

• keys(), values(), entries() 등의 메서드를 활용해 iterator로 순회가 가능하다.

이런 특징을 고려하여 문제 조건에 따른 적절한 선택이 필요하다.

차이점들

각 객체들이 어느 상황에 적합한지 살펴보자.

객체 vs Set

// Set 사용
const arr = [1, 2, 3, 3, 4, 5, 1];
const uniqueSet = new Set(arr);
console.log(uniqueSet); // Set { 1, 2, 3, 4, 5 }

// 일반 객체
const uniqueObj = {};
for(num of arr) {
	if(!uniqueObj[num]) {
		uniqueObj[num] = num
	}
}
const uniqueNums = Object.values(uniqueObj)

console.log(uniqueNums); // [1, 2, 3, 4, 5]

• 중복을 허용하지 않는 데이터를 빠르게 체크해야 할 때 Set이 유용하다.

• Set에는 Map.get(key)처럼 직접 값을 조회하는 메서드가 없다.

• 당연하게도 Set은 키 자체가 값인 이터러블이기 때문이다.

• 즉 비교하려는 값 x의 저장 여부를 확인할 때 유용하다.

객체 vs Map

// Map이 더 나은 경우: 객체를 키로 사용해야 할 때
const user1 = { name: "Alice" };
const user2 = { name: "Bob" };
const accessMap = new Map();
accessMap.set(user1, "Admin");
accessMap.set(user2, "User");
console.log(accessMap.get(user1)); // "Admin"
console.log(accessMap.get(user2)); // "User"


// 객체가 더 편리한 경우: 단순한 키-값 저장
const obj = { name: "John", age: 25 };
console.log(obj.name); // "John"
console.log(obj["age"]); // 25

• 객체는 문자열 키를 저장하고 조회할 때 유용하다.

• 그러나 객체의 키가 문자열이 될 수 없어서 값을 불러오지 못할 수 있다.

• Map은 이런 상황에서 효과적이다. 키를 모든 타입의 값으로 사용할 수 있기 때문이다.

• 데이터 추가 및 삭제가 많을 경우 Map이 성능상 유리하다. (고 한다.)

Set vs Map

// Set이 좋은 경우: 중복 없는 데이터 모음이 필요할 때
const visitedPages = new Set();
visitedPages.add("home");
visitedPages.add("about");
visitedPages.add("home"); // 중복 추가 X
console.log(visitedPages.has("home")); // true

// Map이 좋은 경우: 키와 값을 함께 저장해야 할 때
const wordCount = new Map();
wordCount.set("apple", 2);
wordCount.set("banana", 3);
console.log(wordCount.get("apple")); // 2

Set과 Map의 차이는 명확하다.

• Set은 특정 요소가 존재하는지 여부만 필요할 때 사용한다.

• Map은 키와 값이 분리가 필요할 때 사용한다.

정리하자면 다음과 같다.

자료구조	용도	문제 유형	사용 사례	적합한 문제 키워드
일반 객체	단순 키-값 저장	속성 조회, 작은 데이터 관리	문자열, 숫자로 구성된 데이터 저장	JSON 파싱, 키-값 조회, 캐싱
Set	중복 없는 데이터 저장	유일성 검사, 빠른 조회 필요	방문 기록, 중복 체크를 위한 데이터 저장 (문자열, 숫자 등)	중복 제거, 존재 여부 확인, 유니크 값 필터링
Map	키-값 구조 유지	다양한 키 타입 지원, 빈도수 저장	객체 키 사용, 키가 문자열이 아닌 데이터 저장 (객체, 숫자, 불리언 등)	빈도수 계산, 데이터 매핑, 해시 기반 검색

저장 구조를 설계하기

1. JS 해시는 1. 저장 2. 탐색 2단계로 사용된다

2. x -> 해시 함수(x) = 새로운 키 -> 저장소 탐색

Map의 키는 모든 타입을 사용할 수 있어 상당히 유용하다 .set(키, 값) 메서드로 키와 값을 Map에 저장하므로, 저장을 위해 사용자가 직접 해시 함수를 작성할 필요가 없다.

여기서 의문이 든다. Map은 효과적인 탐색을 하려고 쓰는 것이다. 대부분 문제에선 키-값을 Map에 저장하기 전에 .has()로 효율적 탐색이 필요하다. 무언가 빠진 느낌이다. 키 타입을 제외하면 그저 객체랑 다를 바가 없지 않나?

질문을 바꿔보자. 어떻게 해야 키를 탐색에 유리하게 만들지? 여기서 이어지는 가장 중요한 질문은 어떻게 저장 구조를 탐색에 유리하게 만드는가-이다. 즉 키를 사용하기 전에 키가 O(1)로 접근할 수 있도록 해시에 저장이 되어야 한다. 이후 탐색 조건인 키 x를 조건에 따라 적절히 탐색에 쓰는 것이다. 키를 중간 다리처럼 설계하고, 값에는 답이 될 데이터를 저장하도록 '해시'를 구성하는 것에 집중하자.

const map = new Map();
// ...
// 1. 저장 단계 - 보통 O(n) 순회로 키와 값을 저장한다.
for(let [key, value] of info){
	// 반복문 형태는 달라질 수 있다.
	// 보통 문제의 함수 매개변수를 순회하며 저장한다.
	// 탐색 단계에서 바로 얻을 수 있도록, 
	// 저장단계에서 적절한 키-값을 고려한다 
	map.set(key, value)
}

// 2. 탐색 단계 - 보통 반복문 내부이다.
const key = hash(x) 
// hash 함수로 새로운 키로 변경한다.
// 이때 hash()는 조건에 맞는 키를 반환해야 한다.
// 이 변수의 목적은 해시에 '이미 저장된 값인지 확인하는 용도'이다.
if(map.has(key)){
 // 문제 조건에 따라 로직을 추가한다.
} else {
	map.set(x, value) 
	// key는 탐색용이므로, 경우에 따라 x나 key를 넣는다. 
	// 문제 조건에 따라 달라진다.
	// 배열 순회 + 인덱스가 필요한다면 요소 인덱스를 Map의 value로 넣는다.
}

이 추상적 구현체는 저장 공간 활용의 적절한 기반이 된다. 문제 조건에 따라 일반 객체, Map, Set 적절한 객체를 사용한다. 이때 중요한 점은 두가지이다.

키가 필터링된 값에 바로 접근할 수 있도록 1. 저장 단계에서 키가 필터링할 수 있도록 키-값 설계. 2. 가져온 값의 목적

1. key

• hash(x)는 문제 조건을 반영하여 적절하게 새로운 키를 리턴

  • 저장 단계에서 hash(x)로 바로 값을 얻을 수 있는 해시를 설계한다

  • 보통은 map을 탐색하는 단계에서 문제의 매개변수를 순회한다.

    • 매개변수를 순회하면서 바로 해시에서 꺼내올 수 있는 키가 필요하다.

    • 대부분 난이도가 있는 문제에선 키를 얻기 위해 함수를 사용한다.

    • 이 때 함수 hash(x)는 x 기반으로 저장여부를 판별할 수 있는 키를 반환해야한다.

      • 문제 조건을 구현하는 규칙이 적용된다.

• hash(x) 로 반환된 새로운 키는 Map에 먼저 저장된 기존 키를 탐색할 수 있어야 한다.

• hash(x)는 동일한 입력에 항상 동일한 값을 리턴

2. value

• 맵에 어떤 값을 저장했는 지 목적을 인지한다.

• 문제 조건에 맞게 필요한 값을 저장한다.

• 예시 1 : 배열 순회에서 인덱스를 저장해야 한다면 값에는 인덱스 저장.

• 예시 2 : 문자열 빈도수를 계산해야 한다면 값에는 해당 문자열이 등장 횟수를 저장.

---

문제 1 : Two Sum

컨셉은 이해가 되니, 실전에 적용해보자.

문제 링크:https://leetcode.com/problems/two-sum/description/

문제

정수 배열 nums와 정수 target이 주어졌을 때, 두 숫자의 합이 target이 되는 인덱스를 반환하세요. nums에는 반드시 target의 합이 되는 두 숫자가 있으며, 같은 요소를 두 번 사용할 수 없습니다. 정답은 아무 순서로나 반환할 수 있습니다.

제한 사항

• 2 <= nums.length <= 10^4

• -10^9 <= nums[i] <= 10^9

• -10^9 <= target <= 10^9

• 정답은 반드시 하나만 존재합니다.

문제 분석

제한 조건과 단서를 바탕으로 접근법을 찾아가본다. 가장 눈이 가는 부분은

1. nums.length <= 10^4 시간 복잡도 O(n) 혹은 O(NlogN)으로 풀어야 한다.

2. 두 요소 합이 target이 된다

3. 반환은 nums의 인덱스로 구성

4. 정답은 반드시 하나만 존재

여기서 이해한 바는 이렇다.

• 조건 1: 모든 요소를 2개씩 짝짓는 것은 O(n^2)이 되므로, O(n)으로 푸는 방법을 생각한다. 즉 nums.length - 1 이상으로 순회하지 않는다.

• 조건 2 : 모든 요소를 크거나, 작거나 하는 일관된 규칙으로 정렬할 수 없다. 숫자 크기와 상관없이 target이 만들어질 수 있기 때문이다. 따라서 O(NlogN)의 sort 메서드는 사용하지 않는다. target이 nums[i] + nums[j] 이 같을 때 [i, j]를 반환한다.

• 조건 3: 원본 배열 nums의 인덱스를 유지해야 한다.

• 조건 4: nums는 반드시 target을 만들 수 있는 요소를 포함한다. 즉 i, j는 반드시 있다. 예외처리 해야할 부분이 줄어든다.

이를 바탕으로 문제를 이해하기 쉽게 바꿔보면,

O(n)으로 순회하면서 nums[i] + nums[j] = target인 [i, j]를 반환하시오.

모델 추론하기

이제 i , j 를 찾는 가장 적당한 도구를 찾아보자. 이 도구들을 앞으로 일종의 사고 모델로 가정한다.

해시는 '효율적인 탐색'을 위한 모델이다. 키만 있으면 O(1)로 값을 바로 얻을 수 있다. 지금 상황에 맞아 떨어지는 것 같다. 해시를 풀이 과정에 적용해보면,

graph TD
    A["A. O(n)으로 nums를 순회"] --> B["B. 현재 값은 nums[i] (i = 인덱스)"]
    B --> C["C. 해시에서 나머지 한 쌍 nums[j] 탐색 (O(1))"]
    C -->|찾음| D["결과 반환: [i, j]"]
    C -->|못 찾음| E["현재 값 nums[i]를 해시에 저장"]
    E --> A

적절해 보인다. 하지만 어떻게? 구현을 하려니 여러 고민이 생긴다.

1. 해시로 어떤 객체를 쓰지?

2. 어떻게 해시에 저장하지?

3. 어떻게 해시에서 nums[i]를 찾지?

4. 해시에 적당한 객체 찾기
   Object {} || new Set() || new Map()
   문제 조건에 맞는 적당한 객체를 고민하는게 생각보다 많은 단서를 준다.

그래도 감이 안잡히면 이렇게 좁혀간다.

graph TD;     
A["중복을 제거한 해시가 필요한가?"] -->|"Yes"| B["new Set()"]     
A -->|No| C["해시에 저장 여부만 확인하면 되는가?"]     
C -->|Yes| D["new Set()"]     
C -->|No| E[키가 필요한가?]     
E -->|Yes| F[키 타입이 문자?]     
F -->|Yes| G["Object {}"]     
F -->|No| H["new Map()"] 

Two Sum 문제에 적용하면,

graph TD;
  A[중복을 제거해야 하는가?] -->|No| B[해시에 저장된 값을 탐색해야 하는가?]
  B -->|Yes| C[키 타입은?]
C -->|"문자열"| G["Object {}"]     
C -->|"모든 타입"| H["new Map()"] 

일단 Set은 빠지고, object{}나 Map으로 좁혀진다.

2. 해시에 어떻게 저장/탐색하지?
   객체든 Map이든 키-값을 저장하고, 키로 값을 가져온다. Map 활용의 핵심은 키를 활용하는 것. 이런 생각의 과정으로 키를 설계해보았다.

3. 이 문제는 해시에서 현재 값 nums[i]으로 조건에 맞는 대상nums[j]를 찾는 것이다.

4. hash(x)가 떠오른다. 키를 중간 다리로 사용해 탐색한다.

5. hash(nums[i])가 숫자를 반환하는 게 자연스럽다.

6. 두 수의 합을 찾는 조건에서 키가 숫자인 게 자연스럽다. Map을 사용한다.

7. Map.has()를 나머지 한 쌍 "찾음" | "안찾음" 의 분기 조건으로 쓴다.

8. Map.has(찾는 대상의 키). 현재 값으로 찾을 대상의 키를 얻는다.

9. 찾는 대상은 미리 Map에 저장되어야 한다. Map의 값에는 nums의 모든 숫자가 자연스럽다.

10. 찾을 대상(의 키)는 현재 값과 더했을 때 타겟이 되는 값이다.

11. target = nums[i](현재 값) + nums[j](해시에 있는 키)

12. 그러므로 키는 target - nums[i]. 이걸로 해시를 탐색한다. hash()는 필요 없겠다.

  graph TD;
    A["현재 값: nums[i]"] --> B["찾을 대상: nums[j] = target - nums[i]"]
    B --> C["해시에서 찾기: hash(nums[i]) → key"]
    C -->|찾음| D["결과 반환: [i, j]"]
    C -->|못 찾음| E["해시에 저장: 키는 nums[i], 값은 i"]
    E --> A
  

구현하기

function twoSum (nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
  const gap = target - nums[i] // nums[j]를 gap으로 표기
  const isFound = map.has(j);
  if (isFound) {
    return [map.get(gap), i]
  } else {
    map.set(nums[i], i)
  }
}
};

주의할 점: 코드와 각 추론 단계의 개념을 적절히 매칭하기.

아래의 코드는 똑같이 문제를 해결하지만 별로 좋진 않다.
추론 과정에서 Map에 (target - i)가 있는가-로 접근했기 때문에, 코드 작성 중에 혼란이 가장 큰 이유다.
(참고로 아래 코드는 isFound를 제거한 위의 코드와 2ms 런타임 지연도 생긴다.)

function twoSum (nums, target) {
	const map = new Map();
	for (let i = 0; i < nums.length; i++) {
		const gap = target - nums[i]
		if (map.has(nums[i])) {
			return [map.get(nums[i]), i]
		} else {
			map.set(gap, i)
		}
	}
};