Hacker News 2026.04.13 38

해시 함수, 가장 단순한 형태부터 이해해보기 — 원리를 알면 선택이 쉬워진다

해시 함수가 뭔지는 아는데, 어떻게 만들어지는지는 모르겠다면

개발하다 보면 해시 함수를 정말 자주 쓰잖아요. HashMap, HashSet 같은 자료구조는 거의 매일 쓰고, 비밀번호 저장할 때도 해시하고, 파일 무결성 검증할 때도 해시하고요. 그런데 해시 함수가 내부적으로 어떻게 동작하는지, 왜 어떤 해시 함수는 빠르고 어떤 건 느린지, 왜 특정 상황에서는 충돌이 많이 나는지 — 이런 건 의외로 깊이 파보지 않은 분들이 많을 거예요.

purplesyringa.moe 블로그에 올라온 이 글은 가장 단순한 형태의 해시 함수부터 시작해서, 점점 더 좋은 해시 함수로 발전시켜 나가는 과정을 보여줘요. 마치 레고 블록을 하나씩 쌓아가면서 "아, 그래서 이런 구조가 되는구나"를 이해하게 해주는 방식이라 정말 교육적이에요.

가장 단순한 해시 함수는 이렇게 생겼어요

해시 함수의 본질은 간단해요. 임의의 크기의 데이터를 받아서 고정된 크기의 값을 내놓는 거예요. 예를 들어, "Hello"라는 문자열을 넣으면 42 같은 숫자가 나오고, "World"를 넣으면 17이 나오는 식이죠. 여기서 중요한 건, 같은 입력에는 항상 같은 출력이 나와야 한다는 거예요.

그러면 가장 단순한 해시 함수는 뭘까요? 글에서 처음 소개하는 건 문자열의 각 바이트를 그냥 전부 더하는 거예요. "abc"라면 97 + 98 + 99 = 294, 이런 식으로요. 이게 실제로 동작하는 해시 함수예요! 다만 문제가 있어요. "abc"와 "bac"와 "cab"가 전부 같은 해시값을 갖거든요. 순서가 바뀌어도 합계는 같으니까요. 이런 걸 해시 충돌(collision)이라고 해요.

충돌을 줄이려면 어떻게 해야 할까

그래서 한 단계 발전시킨 방법이 나와요. 단순히 더하는 대신, 각 위치에 가중치를 주는 거예요. 첫 번째 글자는 1을 곱하고, 두 번째 글자는 31을 곱하고, 세 번째 글자는 31의 제곱을 곱하고... 이런 식으로요. 이렇게 하면 글자의 순서가 달라지면 해시값도 달라지게 돼요.

여기서 31이라는 숫자가 나왔는데, 이게 바로 자바의 String.hashCode()에서 실제로 사용하는 방식이에요. 자바 개발자라면 한 번쯤 본 적 있을 텐데, s[0]31^(n-1) + s[1]31^(n-2) + ... + s[n-1] 이 공식이 바로 위에서 설명한 "가중치를 곱해서 더하기"를 수학적으로 표현한 거예요. 왜 하필 31이냐고요? 홀수이면서 소수(prime number)이고, 31 곱하기는 컴퓨터가 비트 시프트와 뺄셈으로 빠르게 계산할 수 있어서(x * 31 = x << 5 - x) 선택된 거예요.

좋은 해시 함수의 조건

글에서 단순한 해시부터 발전시켜 나가면서 자연스럽게 드러나는 좋은 해시 함수의 조건이 있어요.

균일 분포(uniform distribution)가 첫 번째예요. 해시값이 특정 범위에 몰리지 않고 골고루 퍼져야 해요. HashMap을 생각해보면, 해시값이 한쪽에 몰리면 특정 버킷에만 데이터가 쌓여서 성능이 O(1)이 아니라 O(n)으로 떨어지거든요.

눈사태 효과(avalanche effect)도 중요해요. 이게 뭐냐면, 입력이 아주 조금만 바뀌어도 출력이 완전히 달라지는 성질이에요. "Hello"와 "Hellp"처럼 한 글자만 달라도 해시값이 완전히 다른 숫자가 나와야 해요. 단순 덧셈 해시에서는 한 글자가 바뀌면 해시값도 살짝만 바뀌는데, 이러면 해시 테이블에서 비슷한 키들이 같은 영역에 몰리는 문제가 생겨요.

속도도 당연히 중요해요. 아무리 완벽한 분포를 가진 해시 함수라도 계산하는 데 1초가 걸리면 HashMap에 쓸 수 없겠죠. 용도에 따라 속도와 품질 사이의 트레이드오프가 달라져요.

실무에서의 해시 함수 선택 — 용도가 다르면 해시도 달라야 한다

이 글을 읽고 나면 자연스럽게 이해가 되는 건데, 해시 함수는 용도에 따라 완전히 다른 걸 써야 해요.

HashMap 같은 자료구조에 쓰는 해시 함수는 속도가 최우선이에요. 약간의 충돌은 감수하더라도 빠르게 계산되는 게 중요하죠. 여기에 쓰이는 대표적인 해시 함수가 xxHash, FNV-1a, MurmurHash 같은 것들이에요.

반면 비밀번호 저장이나 디지털 서명에 쓰는 암호학적 해시 함수(cryptographic hash function)는 완전히 다른 세계예요. 여기서는 역추적이 불가능해야 하고(해시값으로부터 원본을 알아낼 수 없어야 하고), 의도적으로 충돌을 만들어내는 것도 불가능에 가까워야 해요. SHA-256, bcrypt, Argon2 같은 것들이 이 범주에 속해요. 이런 함수들은 일부러 느리게 만들어져 있어요 — 무차별 대입 공격을 막기 위해서요.

한국 개발자에게 주는 시사점

해시 함수의 원리를 이해하면 실무에서 겪는 여러 상황이 명확해져요. 예를 들어, "왜 Java의 HashMap에서 특정 패턴의 키를 쓰면 성능이 급격히 떨어질까?" 같은 문제를 디버깅할 때, 해시 충돌과 분포의 원리를 알면 원인을 훨씬 빨리 찾을 수 있어요.

또 코딩 인터뷰에서도 해시 관련 문제가 자주 나오는데, 단순히 "해시맵을 쓰면 O(1)"이라고만 외우는 것보다 내부 원리를 이해하고 있으면 심화 질문에도 자신있게 답할 수 있어요. 특히 대기업 면접에서 "좋은 해시 함수의 조건이 뭐냐", "해시 충돌이 나면 어떻게 처리하냐" 같은 질문은 정말 단골이에요.