확률: 23명이면 생일이 겹친다

주문 id를 만드는 코드가 한 줄 있다.

const orderId = crypto.randomUUID()

리뷰에서 질문이 나온다. "DB에 이미 있는 id인지 확인하지 않아도 되나요?" 무작위로 고른 값이니 언젠가는 겹칠 수 있다. 『한입 알고리즘』 1장의 해시 테이블에서도 키를 key % 칸 수로 칸(버킷)에 나눠 담다가 서로 다른 키가 같은 칸에 떨어지는 충돌(collision)을 봤다. 그런데 UUID는 다들 확인 없이 쓴다. 얼마나 드물기에 그럴까? 이 Unit은 "겹칠 확률"을 세는 법을 주사위부터 쌓아 올려, 해시 값이 몇 개쯤에서 겹치기 시작하는지 직접 계산한다.

확률: 원하는 경우 ÷ 전체 경우

확률(probability)은 어떤 일이 일어날 가능성을 0부터 1 사이 수로 적은 것이다. 0이면 절대 안 일어나고 1이면 반드시 일어난다. 경우가 모두 똑같이 일어날 만하면, 확률은 이렇게 센다.

$P = \frac{\text{원하는 경우의 수}}{\text{전체 경우의 수}}$

"전체 경우 중에서 원하는 경우가 차지하는 몫"이라고 읽는다. P는 probability의 첫 글자다. 주사위를 한 번 던져 6이 나올 확률은 전체 6가지 중 1가지라서 1/6, 약 0.167이다.

세어 보는 대신 쓸 수 있는 규칙이 둘 있다.

규칙 1. 서로 영향을 주지 않는 일은 곱한다. 첫 번째 주사위 결과가 두 번째에 아무 영향을 주지 않으면 두 일은 독립(independent)이다. 독립인 두 일이 함께 일어날 확률은 각 확률의 곱이다.

$P(A \text{ 그리고 } B) = P(A) \times P(B)$

"A와 B가 둘 다 일어날 확률은 A의 확률 곱하기 B의 확률"이라고 읽는다. 두 번 다 6일 확률은 1/6 × 1/6 = 1/36이다. 36가지 중 (6, 6) 하나와 맞는다.

규칙 2. "적어도 하나"는 "하나도 없음"을 1에서 뺀다. 어떤 일이 일어나거나 안 일어나거나 둘 중 하나이므로, 두 확률을 더하면 1이다. 어떤 일이 일어나지 않는 경우를 그 일의 여사건(complement)이라고 한다.

$P(\text{적어도 한 번}) = 1 - P(\text{한 번도 없음})$

주사위 두 번에서 6이 한 번도 안 나오려면 두 번 다 6이 아니어야 한다. 한 번에 5/6이고 독립이니 곱해서 5/6 × 5/6 = 25/36이다. 그래서 적어도 한 번 나올 확률은 1 − 25/36 = 11/36, 약 0.306이다. 아래 표의 ≈는 "거의 같다", 곧 "약"이라고 읽는다.

"적어도 하나"를 직접 세면 "하나만", "둘 다"처럼 갈래가 많고 겹쳐 세기 쉽다. "하나도 없음"은 갈래가 하나라서 곱셈 한 번으로 끝난다. 다음 절의 생일 문제도 이 길로 푼다.

생일 역설: 23명이면 50%를 넘는다

이 확률은 앞 절의 규칙 2로 구한다. "적어도 두 사람이 겹침"을 직접 세지 않고, "아무도 안 겹침"을 구해 1에서 뺀다. 아무도 안 겹치려면 사람이 한 명씩 들어올 때마다 앞사람들이 쓴 날을 피해야 한다.

$P(\text{23명이 아무도 안 겹침}) = \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \cdots \times \frac{343}{365} \approx 0.493$

"첫 사람은 아무 날이나 괜찮고(365일 중 365일), 둘째는 첫 사람의 날을 피해 364일, 셋째는 363일, …, 스물셋째는 343일 중 하나여야 한다"고 읽는다. k번째 사람이 피할 날은 앞사람 k − 1명이 쓴 날이라서, 남은 날은 365 − k + 1일이다. 코드로는 사람마다 한 항씩 곱해 간다.

1const people = 232let none = 1 // 아무도 안 겹칠 확률3for (let k = 1; k <= people; k++) none *= (365 - k + 1) / 365

이 곱이 0.493이니 겹칠 확률은 1 − 0.493 = 0.507이다.

왜 이렇게 빨리 넘을까? 직관은 "나와 같은 생일인 사람"을 떠올린다. 하지만 문제는 "아무나 둘"이다. 23명이 만드는 두 사람 짝은 253개다(Unit 6의 조합으로, 23명 중 두 명을 고르는 가짓수 23 × 22 ÷ 2). 짝 하나하나가 1/365의 확률로 겹칠 기회이고, 그 기회가 253번 있다. 다만 1/365를 253번 더하면 약 0.69라 앞에서 구한 0.507보다 크다. 세 사람이 같은 날이면 짝 셋이 한꺼번에 겹치듯 짝의 겹침끼리 겹쳐서, 더하면 겹쳐 센다(1절의 주사위에서 (6, 6)을 두 번 센 것과 같은 일). 그래서 짝마다 안 겹칠 확률 364/365를 253번 곱해 1에서 빼는 1 − (364/365)²⁵³ ≈ 0.50으로 어림한다. 정확한 값은 위 곱셈으로 구한 0.507이다. 사람 수가 늘 때 짝의 수는 그보다 훨씬 빨리 는다. 사람이 2배가 되면 짝은 약 4배가 된다.

해시 충돌: 버킷 m개에 키 √m개

생일 문제에서 365일을 버킷으로, 사람을 키로 바꾸면 해시 테이블(hash table)의 충돌(collision) 문제가 된다. 해시 함수(hash function)가 키마다 버킷 번호를 고른다. 좋은 해시 함수는 버킷을 고르게, 마치 무작위로 고르는 것처럼 퍼뜨린다. 그러면 "키 n개 중 두 개가 같은 버킷에 떨어질 확률"은 생일 문제와 같은 계산이다.

몇 개쯤에서 겹치는지는 짝의 수로 어림할 수 있다. 키 n개가 만드는 짝은 약 n²/2개이고, 짝 하나가 같은 버킷에 떨어질 확률은 1/m이다. 짝의 수가 버킷 수와 비슷한 규모가 되면 충돌은 흔한 일이 된다. 어림으로 n²/2 ≈ m이면 n ≈ √(2m), 곧 약 1.4√m이다. 한 항씩 정확히 곱해 50%가 되는 지점을 찾으면 그보다 조금 작다.

$n \approx 1.18\sqrt{m}$

√m은 m의 제곱근(square root)으로, 제곱해서 m이 되는 수다. √100 = 10이고 √365 ≈ 19.1이다. 그래서 식은 "키 수가 버킷 수의 제곱근의 약 1.2배쯤 되면 충돌 확률이 반"이라고 읽는다. 버킷 100개면 1.18 × 10 ≈ 11.8이라 키 12개 안팎이다. 하나씩 정확히 곱해 보면 키 12개에서 0.497, 13개에서 0.557이라 13번째 키에서 50%를 넘는다. 어림식은 이만큼 가깝다. 365개면 1.18 × 19.1 ≈ 22.5라서 23명이다. 생일 역설의 23이 이 식에서 나온다. 1.18은 기준을 50%로 잡았을 때 나오는 상수다. 외울 필요 없이 "√m의 1.2배쯤"으로 기억하면 된다.

비트가 많아야 하는 이유: 32비트, UUID, SHA-256

해시 값이 b비트면 나올 수 있는 값은 2ᵇ가지다(Unit 1). 해시 값을 그대로 id로 쓰면, 나올 수 있는 값 2ᵇ가지가 곧 버킷 2ᵇ개인 셈이다(해시 테이블이 키를 key % 칸 수로 나눠 담는 버킷과는 다른 말이다). 32비트 해시는 2³² ≈ 43억 가지다. 43억이면 넉넉해 보이지만 앞 절의 식에 넣으면 이렇다.

$1.18\sqrt{2^{32}} = 1.18 \times 2^{16} = 1.18 \times 65536 \approx 77000$

"2³²의 제곱근은 지수를 반으로 나눈 2¹⁶(2¹⁶ × 2¹⁶ = 2³²이니), 곧 65,536이고 그 1.18배"라고 읽는다. 키가 약 7.7만 개면 두 키의 해시 값이 겹칠 확률이 50%다. 사용자 10만 명을 32비트 해시로 구별하면 서로 다른 사람을 같은 사람으로 볼 확률이 반이 넘는다. 제곱근을 씌우면 지수가 반이 되므로, b비트 해시는 대략 2의 (b ÷ 2)제곱 개에서 겹치기 시작한다고 기억하면 쉽다.

표의 "1.8 × 10¹⁹" 같은 표기는 1.8 뒤에 0이 19개쯤 붙는 수라는 뜻이다(약 a × 10ᵏ은 a 뒤에 0이 k개쯤 붙는 수).

crypto.randomUUID()가 만드는 UUID v4는 128비트 중 6비트가 버전·변형 표시로 고정이고 나머지 122비트가 무작위다(RFC 9562 §5.4, MDN: Crypto.randomUUID). Python의 uuid.uuid4()도 같은 v4 UUID를 만든다(Python 문서: uuid). 겹칠 확률이 50%가 되려면 약 2.7 × 10¹⁸개, 270경 개를 만들어야 한다. 1초에 10억 개씩 만들어도 86년쯤 걸리는 수다. 그래서 처음의 리뷰 질문에는 "확인하지 않아도 된다"고 답할 수 있다. 단, 무작위 비트가 정말 무작위일 때 이야기다. randomUUID는 암호학적으로 안전한 난수 생성기를 쓰지만, Math.random()은 그런 보장이 없다(MDN: Math.random). SHA-256 같은 256비트 해시를 파일의 지문으로 믿고 쓰는 것도 같은 계산 덕분이다. 우연히 겹치려면 약 4 × 10³⁸개의 입력이 필요하다.

이 Unit이 쓰이는 곳

• 『한입 알고리즘』 1장 해시: 2절 "충돌"에서 서로 다른 키가 같은 버킷에 몰리는 장면과, 키가 늘면 버킷 수를 키우는 리해시가 나온다. 버킷이 남아 있어도 충돌이 일찍 생기는 까닭을 이 Unit의 계산으로 알 수 있다.
• 『한입 CS』 10장 해시·암호화·인코딩: 2절 "해시: 되돌릴 수 없는 지문"에서 SHA-256이 늘 256비트를 낸다. 256비트면 우연히 겹치는 데 약 4 × 10³⁸개가 필요해서 지문으로 쓸 수 있다.
• 해시 테이블 노트: 버킷과 충돌 처리 방식 정리.

나와 같은 사람이 있을 확률 > 0.5 → n = ?
아무나 두 사람이 겹칠 확률 > 0.5 → 23명