어떻게 이름표로 바로 찾기, 해시

이름표가 칸 번호를 정한다

앞 레슨에서는 줄지어 놓인 값을 찾으려면 하나씩 훑거나 정렬된 색인을 써야 했다. 그런데 값 자체를 보고 칸 번호를 정할 수 있다면 어떨까? 이름의 글자로 칸을 정하는 것처럼 말이다.
값을 넣으면 칸 번호가 나오는 작은 계산을 하나 정해 두는 것이다. 이 계산을 해시 함수라고 불러요. 첫 레슨에서 본 딕셔너리도 속을 들여다보면 이 방법으로 움직인다.

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

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

계산해서 바로 그 칸으로

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

찾을 값을 눌러 보자. 같은 계산으로 칸 번호가 나오고, 훑지 않고 그 칸으로 바로 건너가요.

훑지 않고 바로 도착했다. 칸이 백 개든 만 개든 드는 수고는 거의 같다. 계산 한 번, 건너가기 한 번이면 끝나기 때문이다.
이것이 해시가 빠른 까닭이에요. 정렬된 색인이 스무 번 남짓 들여다봐야 했다면, 해시는 대개 한 번에 끝난다. 그런데 걸리는 점이 하나 있다. 서로 다른 값 둘의 계산 결과가 같으면 어떻게 될까?

둘이 같은 칸으로 간다

계산은 언제나 같은 값에 같은 칸을 알려 주지만, 값이 다르다고 칸까지 꼭 다르지는 않다. 칸의 수는 정해져 있는데 값은 훨씬 많을 수 있기 때문이다.
그래서 서로 다른 값 둘이 우연히 같은 칸을 받는 일이 생겨요. 한 칸에 둘이 들어가려는 것이다. 이렇게 같은 칸을 두고 부딪히는 것을 충돌이라고 한다.

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

같은 칸을 두고 둘이 부딪혔다. 한 칸에는 보통 하나만 들어가는데 둘이 한꺼번에 왔으니 문제다.
그렇다고 해시를 버릴 수는 없어요. 계산을 잘 고르면 충돌은 드물고, 나머지는 여전히 한 번에 빠르다. 그러니 충돌이 났을 때만 따로 처리해 주면 된다. 어떻게 처리하는지 살펴보자.

충돌은 따로 처리한다

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

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

충돌이 깔끔하게 풀렸다. 묶어 담든 옆 칸으로 미루든 값은 안전하게 자리를 잡았다.
찾을 때도 같은 규칙을 따르면 충돌한 값도 잘 찾아낸다. 다만 칸이 거의 다 차면 충돌이 잦아지므로, 많이 차기 전에 칸을 늘려 다시 배치해요. 충돌은 가끔이고 처리도 간단하니 해시는 여전히 빠르고 든든하다.

정리

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

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

이제 값을 계산으로 바로 찾는 방법을 알았다. 자리를 훑던 답답함이 계산 한 번으로 풀렸다.
그런데 해시에도 못 하는 일이 있어요. 칸이 값의 크기와 상관없이 흩어져 있어서 '가'부터 '다'까지처럼 범위로 찾거나 순서대로 늘어놓는 데는 쓸 수 없다. 다음 레슨에서는 순서를 지키면서도 빨리 찾는 그릇, 트리를 만난다.