해시: 찾기를 한 번에

주문 목록 화면을 만든다. 사용자별로 주문을 묶어야 하고, 같은 상품 코드가 여러 번 나오면 한 번만 보여 줘야 한다. 장바구니에는 "예산에 딱 맞는 상품 두 개 추천" 기능도 붙는다. 세 가지 모두 같은 질문으로 줄어든다. 이 값을 전에 본 적이 있나, 있다면 어디에 있나?

const byUser = new Map<number, Order[]>()
for (const o of orders) {
  const list = byUser.get(o.userId) ?? []
  list.push(o)
  byUser.set(o.userId, list)
}
const uniqueSkus = new Set(orders.map(o => o.sku))

0장에서는 includes를 Set으로 바꿔 상품 하나당 비교를 고른 id 수만큼에서 한 번으로 줄였다. 이 장은 그 "한 번"이 어떻게 가능한지, 그리고 그 한 번이 깨지는 경우가 언제인지 본다. 개념 정리는 해시 테이블 노트에 있다.

해시 함수와 버킷: 계산으로 자리를 정한다

해시 테이블(hash table)은 키를 해시 함수(hash function)에 넣어 나온 수로 저장할 칸 번호를 정한다. 이 칸을 버킷(bucket)이라고 부른다. 찾을 때도 같은 계산을 다시 해서 그 버킷만 열어 본다. 배열 전체를 앞에서부터 훑지 않는다.

서로 다른 키가 같은 버킷 번호를 받으면 그 버킷의 배열 뒤에 이어 붙인다. 이 방식을 체이닝(chaining)이라고 한다.

실제 Map·Set·dict는 문자열, 객체 같은 키도 받는다. 언어 런타임이 키마다 정수 해시 값을 계산하고, 그 값으로 버킷을 고른다는 뼈대는 같다. ECMAScript 명세는 Map이 원소를 평균적으로 원소 수보다 느리게 자라는(sublinear) 시간에 찾도록 구현하라고만 정한다. 해시 테이블이 대표적인 구현이다(MDN: Map).

충돌: 평균 O(1), 최악 O(n)

키 2, 7, 12, 17은 5로 나눈 나머지가 모두 2다. 네 키가 2번 버킷 하나에 줄지어 서고, 17을 찾을 때 4번 비교한다. 버킷 배열이 있어도 한 버킷에 몰리면 결국 배열을 앞에서부터 훑는 것과 같다. 키 n개가 모두 한 버킷에 몰리면 찾기는 O(n)이다.

그래서 해시 테이블의 비용은 평균과 최악 두 가지로 적는다. Python Wiki의 시간 복잡도(time complexity) 표도 dict의 값 꺼내기를 평균 O(1), 최악 O(n)으로 적는다(Python Wiki: TimeComplexity). 평균이 O(1)이 되려면 두 가지가 필요하다.

• 해시 함수가 키를 버킷에 고르게 퍼뜨린다. key % 5 해시는 5의 배수 간격으로 오는 키(2, 7, 12, 17)를 한 버킷에 모은다. 실제 런타임은 비트(2진수 자리, 『개발 수학』 Unit 1)를 잘 섞는 해시 함수를 쓴다.
• 키가 늘어나면 버킷 수도 늘린다. 버킷 수를 그대로 두면 버킷마다 키가 쌓인다. 일반적인 구현은 키 수가 버킷 수에 비해 일정 비율(키 수 ÷ 버킷 수)을 넘으면 버킷 배열을 키우고 모든 키를 새 버킷 번호로 다시 나눠 담는다. 이것을 리해시(rehash)라고 한다. 리해시는 키 n개를 모두 옮기니 O(n)이 걸린다. 하지만 버킷 수를 두 배처럼 일정 비율로 키우면 리해시는 점점 드물게 일어난다. 버킷 4개에서 시작해 키 수가 버킷 수를 넘을 때마다(앞의 일정 비율을 1로 둔 경우) 두 배(4 → 8 → 16)로 키우며 키 16개를 넣으면 리해시는 두 번, 옮긴 키는 4 + 8 = 12개뿐이다. 그 비용을 사이사이의 넣기 여러 번에 나눠 보면 넣기 한 번의 평균 비용은 상수다(분할 상환 분석, 『개발 수학』 Unit 4. 0장 보너스에 같은 계산이 있다).

실무에서 최악이 나오는 일은 드물다. 그래도 "해시맵(hash map)이니까 늘 한 번"이라고 외우기보다 "버킷이 고르게 나뉘는 동안 한 번"이라고 기억해 두면, 키를 잘못 골랐을 때 생기는 일을 설명할 수 있다.

두 수의 합(two sum): 본 값을 적어 두며 한 번 훑기

예산 12원에 딱 맞는 상품 두 개를 고르는 문제다. 모든 쌍을 비교하면 상품 n개에 n(n − 1)/2쌍, O(n²)이다. 상품 4개면 (0, 1)(0, 2)(0, 3)(1, 2)(1, 3)(2, 3)의 6쌍 = 4 × 3 ÷ 2이고, 대략 n²/2다(두 개 고르는 경우의 수는 『개발 수학』 Unit 6, 합이 n²/2에 가까운 이유는 Unit 4). 해시맵(Map·dict처럼 해시 테이블로 만든 맵)을 쓰면 한 번 훑기로 줄어든다. 지금 상품 가격이 prices[i]라면 짝은 budget - prices[i]원짜리다. 앞에서 본 가격을 seen(가격 → 상품 번호)에 적어 두면, 짝이 있었는지 한 번에 물을 수 있다.

1const prices = [5, 9, 3, 7]2const budget = 123const seen = new Map<number, number>()4let answer = '없음'5for (let i = 0; i < prices.length; i++) {6  const need = budget - prices[i]7  if (seen.has(need)) {8    answer = `${seen.get(need)}번 + ${i}번`9    break10  }11  seen.set(prices[i], i)12}13console.log(answer)

1번 + 2번

Map은 키를 넣은 순서대로 꺼낸다(MDN: Map). Python dict도 3.7부터 넣은 순서를 지키는 것이 언어 규칙이 되었다(Python 문서: dict). 그래서 사용자별로 묶은 결과를 다시 화면에 그릴 때 처음 나온 순서가 유지된다. 단, 해시 테이블은 크기 순서를 모른다. 가격순으로 보여 주려면 따로 정렬해야 한다.

키 고르기: 무엇이 같은 키인가

해시 테이블은 "같은 키"를 찾는다. 무엇을 같다고 보는지가 언어마다 다르고, 여기서 버그가 난다.

1const cache = new Map<object, string>()2cache.set({ userId: 1 }, '배송 중')3cache.get({ userId: 1 }) // undefined4cache.set('user:1', '배송 중')5cache.get('user:1') // '배송 중'

JavaScript Map은 원시 값(primitive, 문자열·숫자)은 값으로 비교하지만 객체 키는 참조로 비교한다. 내용이 같은 { userId: 1 }이라도 새로 만든 객체는 다른 키다(MDN: Map). 배열도 객체라서 Set에 [1, 2]를 두 번 넣으면 원소가 2개가 된다. 내용으로 묶고 싶으면 'user:1'처럼 문자열 키를 만든다.

Python은 키가 해시 가능(hashable)해야 한다. 값이 바뀔 수 있는 list·dict는 해시 가능하지 않아서 키로 넣으면 TypeError가 난다. 내용이 바뀌는 값을 키로 받아 주면 바뀐 뒤에 해시 값이 달라져 엉뚱한 버킷을 보게 되기 때문이다. 튜플은 원소가 모두 해시 가능하면 키가 된다(Python 용어집: hashable).

일반 객체 {}를 맵 대신 쓸 때도 함정이 둘 있다.

1const counts: Record<string, number> = {}2for (const w of ['a', 'b', 'a']) counts[w]++3console.log(counts) // { a: NaN, b: NaN }4console.log('constructor' in counts) // true5 6const safe = new Map<string, number>()7for (const w of ['a', 'b', 'a']) safe.set(w, (safe.get(w) ?? 0) + 1)

첫째, JavaScript 객체에서 없는 키를 읽으면 undefined이고 undefined + 1은 NaN이다. Python은 없는 키를 읽으면 KeyError가 난다. 둘 다 "없으면 0"을 직접 적어야 한다(?? 0, .get(w, 0)). 둘째, 일반 객체에는 프로토타입에서 물려받은 키(constructor, toString 등)가 이미 있다. 사용자가 입력한 단어를 키로 쓰면 이 키와 부딪힐 수 있다. Map은 넣은 것만 들어 있다(MDN: Map).

실무 코드에서 찾아보기

정리하면 틀린 줄은 두 종류다. 없는 키를 읽는 줄(push는 TypeError, ++는 NaN)과 배열·객체를 키로 쓰는 줄(참조로 비교해 겹침이 안 걸러지고 get으로 못 꺼낸다)이다. 없으면 기본값을 먼저 넣고, 키는 문자열이나 id로 쓴다.

nums = [1, -1, 2, 1, -2, 3], k = 3 → 4
([1, -1, 2, 1], [-1, 2, 1, -2, 3], [2, 1], [3])