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	키-값 구조 유지	다양한 키 타입 지원, 빈도수 저장	객체 키 사용, 키가 문자열이 아닌 데이터 저장 (객체, 숫자, 불리언 등)...