이름표로 바로 찾기, 해시

이름표가 칸 번호를 정해요

앞에서 값들이
자리 번호로 줄지어 있는 걸 배웠어요.
찾으려면 자리를 하나씩 훑어야 했죠.
그런데 값 자체를 보고
칸 번호를 정할 수 있다면 어떨까요?
이름의 글자로 칸을 정하듯이요.
값을 넣으면 칸 번호가 나오는
작은 계산을 하나 두는 거예요.
그 계산을 해시 함수라고 불러요.

값을 눌러봐요. 계산이 칸 번호를 정하고, 그 칸에 쏙 들어가요.

값마다 칸이 척척 정해졌죠.
어디에 둘지 고민할 필요가 없어요.
계산이 자리를 알려 주니까요.
같은 값을 다시 넣어도
계산 결과는 늘 같은 칸이에요.
그래서 칸이 들쭉날쭉하지 않아요.
그렇다면 찾을 때도
같은 계산을 쓰면 되지 않을까요?

계산해서 바로 그 칸으로

찾을 때도 비밀은 똑같아요.
찾는 값을 같은 계산에 넣어
칸 번호를 구하면
곧장 그 칸으로 가면 돼요.
칸을 하나씩 훑을 필요가 없어요.
넣을 때 쓴 계산과
찾을 때 쓴 계산이 같으니
넣어 둔 칸과 찾는 칸이 딱 맞아요.
그래서 한 번에 도달해요.

찾을 값을 눌러봐요. 같은 계산으로 칸 번호가 나오고, 훑지 않고 그 칸으로 바로 점프해요.

훑지 않고 바로 도착했죠.
칸이 백 개든 만 개든
걸리는 수고는 비슷해요.
계산 한 번, 점프 한 번이면 끝이니까요.
이게 해시가 빠른 이유예요.
그런데 한 가지 걸리는 게 있어요.
서로 다른 값 둘이
계산 결과가 같으면 어떻게 될까요?

둘이 같은 칸으로 가요

계산은 늘 같은 칸을 알려 주지만
값이 다르다고 칸까지 다르진 않아요.
서로 다른 값 둘이
우연히 계산 결과가 같을 수 있어요.
그러면 둘 다 같은 칸으로 가죠.
한 칸에 둘이 들어가려는 거예요.
이렇게 같은 칸을 두고 부딪히는 걸
충돌이라고 불러요.
충돌은 드물지만 분명히 생겨요.

두 값을 차례로 눌러봐요. 계산 결과가 같아 둘이 같은 칸으로 가서 부딪혀요.

같은 칸을 두고 둘이 부딪혔죠.
한 칸에는 보통 하나만 들어가는데
둘이 동시에 오니 문제예요.
그렇다고 해시를 포기할 순 없어요.
충돌은 어쩌다 한 번이고,
나머지는 여전히 한 번에 빠르거든요.
그러니 충돌이 났을 때만
살짝 따로 처리해 주면 돼요.
어떻게 처리하는지 볼까요?

충돌은 따로 처리해요

충돌을 푸는 길은 크게 둘이에요.
하나는 한 칸에 둘을 묶어 담는 거예요.
칸에 작은 묶음을 두고
부딪힌 값들을 거기 나란히 넣어요.
다른 하나는 옆 칸으로 미루는 거예요.
원래 칸이 차 있으면
비어 있는 옆 칸을 찾아 거기 넣죠.
어느 쪽이든 값을 잃지 않고
나중에 다시 찾을 수 있어요.

처리 방법을 골라 눌러봐요. 한 칸에 묶어 담거나, 옆 칸으로 미뤄 충돌을 풀어요.

충돌이 깔끔하게 풀렸죠.
묶어 담든 옆 칸으로 미루든
값은 안전하게 자리를 잡았어요.
찾을 때도 같은 규칙을 따르면
충돌한 값도 잘 찾아낼 수 있어요.
충돌은 가끔이고 처리도 간단하니
해시는 여전히 빠르고 든든해요.
이제 전체를 한 번 정리해봐요.

정리해볼까요

한 줄로 모으면 이래요.
값을 보고 계산으로 칸 번호를 정해요.
넣을 때 그 칸에 넣고,
찾을 때 같은 계산으로 그 칸으로 가요.
그래서 훑지 않고 한 번에 도달하죠.
가끔 다른 값이 같은 칸으로 가는
충돌이 생기면 따로 처리해요.
묶어 담거나 옆 칸으로 미루면 돼요.
계산으로 바로 찾기, 그게 해시예요.

핵심을 차례로 눌러 되짚어봐요. (계산으로 칸 정하기 → 같은 계산으로 바로 찾기 → 같은 칸 충돌 → 충돌은 따로 처리)

이제 값을 계산으로 바로 찾는
똑똑한 방법을 알게 됐어요.
자리를 훑던 답답함이
계산 한 번으로 시원하게 풀렸죠.
넣기와 찾기를 빠르게 하는
이런 솜씨가 데이터를 다루는 힘이에요.
다음엔 또 어떤 방법으로
값을 더 잘 담고 찾을 수 있을지
함께 이어서 살펴봐요.