해시 테이블

칸이 7개인 표에 47을 넣어 두면, 컴퓨터는 표 전체를 뒤지는 대신 곧장 47 mod 7 = 5번 칸으로 갑니다.

키를 자리 번호로 바꾸기

지금까지 값을 찾으려면 탐색을 해야 했습니다. 정렬되지 않은 배열이나 연결 리스트에서는 최대 n단계입니다. 그런데 배열은 어느 자리든 한 단계에 갈 수 있습니다. 키가 곧장 자리 번호를 알려 준다면 어떨까요? 키가 0부터 99까지의 학번처럼 작은 정수라면 칸 100개짜리 배열을 두고 학생 k를 k번 칸에 넣으면 됩니다. MIT 노트는 이것을 직접 접근 배열이라고 부릅니다. 하지만 전화번호나 낱말처럼 가능한 키가 아주 많으면 키마다 칸을 둘 수 없어서 쓸 수 없습니다.

해시 함수는 어떤 키든 0부터 m − 1까지 작은 범위의 자리 번호로 줄여서 이 문제를 풉니다. 정수에 쓰는 간단한 해시 함수는 h(k) = k mod m으로, m으로 나눈 나머지입니다. m칸짜리 배열이 해시 테이블이고, 칸을 흔히 버킷이라고 부릅니다. m = 7일 때 47을 넣으려면 47 mod 7 = 5를 계산해 5번 칸에 넣습니다. 나중에 47을 찾을 때도 같은 계산을 하고 5번 칸만 봅니다.

충돌과 체이닝

문제가 하나 있습니다. 칸은 7개인데 가능한 키가 7개보다 많으면 몇몇 키는 같은 칸을 써야 합니다. 12, 33, 47은 모두 나머지가 5입니다. 이것을 충돌이라고 하며, MIT 노트는 비둘기집 원리 때문에 충돌을 피할 수 없다고 짚습니다. 흔한 해결책은 체이닝입니다. 칸마다 그 칸으로 해시된 키를 모두 담는 작은 리스트를 두는데, 이것을 사슬이라고 합니다. 그러면 47을 찾는 비용은 해시 계산 1단계에, 5번 사슬에서 확인한 키마다 비교 한 번입니다. 12와 33이 앞에 있다면 1 + 3 = 4단계입니다.

사슬은 얼마나 길까요? 키가 고르게 퍼지면 사슬마다 키가 약 n/m개 들어가는데, 이 값을 적재율이라고 합니다. m을 n과 비슷하게 크게 유지하면 사슬이 짧게 남아서 찾기, 넣기, 지우기가 평균적으로 일정한 단계 수에 끝납니다. 위험한 것은 고르지 못하게 퍼지는 경우입니다. 모든 키가 같은 칸으로 해시되면 사슬 하나에 키 n개가 모두 들어가서 연결 리스트보다 나을 것이 없습니다. 실험실에서 칸을 7개로 두고 14, 21, 28을 넣어 보세요. 모두 0번 칸에 들어갑니다.

불러오는 중

끌어서 돌리고, 휠이나 두 손가락으로 확대하세요.

h(k) = k mod 7인 칸 7개짜리 해시 테이블에 12, 25, 33, 47, 70이 들어 있습니다. 키를 고르고 넣기, 찾기, 지우기를 눌러 보세요. 단계 수는 해시 계산 1에 사슬에서 비교한 키 수를 더한 것입니다.

실제 해시 함수는 키의 모든 비트를 섞고, 잘 만든 라이브러리는 평범한 데이터가 고르게 퍼지도록 함수를 고릅니다. MIT 6.006은 한 걸음 더 나아가 해시 함수를 여러 함수의 묶음에서 무작위로 골라, 어떤 고정된 키 묶음도 매번 나쁘게 나오지 않게 합니다. 실험실의 k mod m은 손으로 확인할 수 있어서 골랐습니다.

자바스크립트의 해시 테이블

해시 테이블을 직접 만들 일은 드뭅니다. 자바스크립트에 Map과 Set이 있기 때문입니다. ECMAScript 명세는 이 둘을 「해시 테이블이나, 평균적으로 원소 수에 대해 선형보다 느리게 늘어나는 접근 시간을 주는 다른 방식으로 구현해야 한다」고 적습니다. 바꿔 말하면 map.get(key)와 set.has(x)는 모음 전체를 뒤지는 것보다 빨라야 합니다. MDN은 Map이 넣은 순서대로 키를 기억하고, 일반 객체와 달리 내 키와 겹칠 수 있는 기본 키가 없다고 덧붙입니다.

const price = new Map();
price.set("apple", 1.2);
price.set("bread", 2.5);
console.log(price.get("bread")); // 2.5, no search through the list
console.log(price.has("milk"));  // false
const seen = new Set([4, 8, 15]);
console.log(seen.has(8));        // true

배경해싱이라는 생각은 IBM의 한스 페터 룬이 처음 냈다고 봅니다. 도널드 커누스가 정리한 탐색의 역사에 따르면 룬은 1953년 1월 IBM 내부 메모에서 기록을 번호 붙은 칸에 나눠 넣고, 충돌하는 기록은 사슬로 잇자고 제안했습니다. 그의 해시 함수는 숫자를 다뤘습니다. 이웃한 숫자 두 개씩 더해서 합의 끝자리만 남기므로 31415926은 4548이 됩니다. IBM 701에서 일하던 다른 IBM 기술자들도 비슷한 때 같은 생각을 했고, 처음 공개된 설명은 1956년 아널드 듀미의 글입니다.

해시 함수	키를 0~m − 1의 칸 번호로 바꿈. 예: k mod m.
충돌	서로 다른 키가 같은 칸을 받음. 키가 칸보다 많으면 피할 수 없음.
체이닝	칸마다 그 칸으로 해시된 키 목록을 둠.
적재율	n/m, 사슬의 평균 길이.
Map과 Set	자바스크립트 내장 키 모음. 평균적으로 선형보다 빨라야 함.

h(k) = k mod 7일 때 47은 몇 번 칸에 들어갈까요?
12, 25, 33, 47, 70을 이 순서로 넣은 m = 7 표에서 47을 찾는 데 몇 단계일까요(해시 1 + 비교한 키 수)?
같은 표에서 12를 찾는 데 몇 단계일까요?
같은 표에 19는 없습니다. 19를 찾으면 몇 단계일까요?
같은 표의 적재율 n/m은 얼마일까요?(소수 둘째 자리까지)
충돌이란 무엇일까요?
- 너무 큰 키
- 서로 다른 두 키가 같은 칸으로 해시되는 것
- 키를 두 번 지우는 것
- 키가 하나도 없는 표
가능한 키가 칸보다 많을 때 어떤 해시 함수도 충돌을 피할 수 없는 까닭은?
- 컴퓨터가 수를 반올림해서
- 비둘기집 원리 때문에
- 키가 늘 짝수라서
- 사슬이 너무 짧아서
모든 키가 같은 칸에 들어가면 키 찾기는 어떻게 될까요?
- 여전히 1단계
- 키 n개짜리 연결 리스트를 뒤지는 것과 같다
- 불가능해진다
- 이진 탐색과 같다
ECMAScript 명세는 Map의 접근 시간에 무엇을 요구할까요?
- 정확히 1단계
- 평균적으로 원소 수에 대해 선형보다 느리게 늘어날 것
- Θ(n log n)
- 아무 요구도 없음
룬의 1953년 해시는 이웃한 숫자 두 개씩 더해 합의 끝자리만 남겼습니다. 31415926은 무엇이 될까요?

핵심 정리

해시 함수는 키를 칸 번호로 바꿉니다. k mod m이 간단한 예입니다.
충돌은 피할 수 없고, 체이닝은 칸마다 리스트를 둡니다.
적재율 n/m을 작게 유지하면 찾기, 넣기, 지우기가 평균적으로 일정한 단계 수입니다.
자바스크립트 Map과 Set은 평균적으로 선형보다 빨라야 합니다.

이 과정의 출처 (5)

MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon), lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append), 4 Hashing (chaining, pigeonhole collisions, chain length n/m), 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
MDN Web Docs, Array.prototype.shift (shifts all values left by 1), Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
ECMAScript 2025 Language Specification (tc39.es/ecma262), 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements"), Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
"A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).

확인한 날: 2026-10-18