해시테이블 - 계산해서 자리를 정한다

아파트 우편함을 생각해 보자. 우편함이 200개인데 관리인은 우편물을 넣을 때 한 번도 헤매지 않는다. 호수를 보면 몇 번 칸인지 바로 알기 때문이다.

이름을 계산해 번호를 얻는다

지금까지 본 그릇은 전부 찾았다. 처음부터 훑거나, 반씩 좁히거나, 고리를 따라 걸었다. 해시테이블은 발상이 다르다. 아예 안 찾는다.

이름을 넣으면 숫자가 나오는 계산식을 하나 정해둔다. 그 숫자가 곧 칸 번호다. 넣을 때도 그 칸에 넣고, 찾을 때도 같은 계산을 해서 그 칸만 열어본다.

Map<String, User> users = new HashMap<>();
users.put("kim@example.com", user);   // 계산 → 47번 칸
users.get("kim@example.com");         // 계산 → 47번 칸. 열어보면 있다

핵심은 넣을 때와 찾을 때 같은 계산을 한다는 것뿐이다. 그러면 어디에 뒀는지 기억할 필요가 없다. 계산이 기억을 대신한다.

왜 한 번에 가나

칸이 200개든 200만 개든 하는 일이 똑같다. 계산 한 번, 칸 하나 열기. 앞에서 본 표기로는 O(1)이고, 데이터가 늘어도 그대로다.

앞 글에서 남겨둔 숙제가 이걸로 풀린다. 반복문 안의 contains 한 줄이 O(n²)을 만들던 그 코드는, 목록을 Set으로 바꾸는 것만으로 O(n)이 된다. Set도 속은 해시테이블이라 찾지 않고 계산하기 때문이다.

여기까지만 보면 만능이다. 대가는 지금부터다.

충돌은 반드시 일어난다

우편함은 200칸인데 담을 이름은 몇 개든 될 수 있다. 그러면 다른 이름이 같은 칸으로 계산되는 일이 반드시 생긴다. 이걸 충돌이라고 한다.

“계산식을 잘 만들면 안 생기지 않나” 싶지만 안 된다. 담을 수 있는 이름은 사실상 무한한데 칸은 유한하다. 넣을 것이 칸보다 많으면 겹치는 칸이 생기는 건 계산이 나빠서가 아니라 산수다.

그래서 해시테이블 설계는 “충돌을 없애는” 문제가 아니라 **“충돌이 났을 때 어떻게 하느냐”**의 문제다.

충돌을 다루는 두 방법

한 칸에 여럿을 매단다. 47번 칸에 이미 누가 있으면 그 뒤에 이어 붙인다. 찾을 때는 47번 칸을 열고 그 안을 훑는다. 앞 글에서 본 연결리스트가 여기서 쓰인다.

빈 칸을 찾아 옆으로 간다. 47번이 차 있으면 48번, 49번을 열어본다. 찾을 때도 47번부터 순서대로 열어보며 맞는 것이 나올 때까지 간다.

앞엣것이 이해하기 쉽고 널리 쓰인다. 뒤엣것은 칸이 붙어 있어 덩어리째 읽히는 이점을 그대로 누린다. 어느 쪽이든 충돌이 적을 때만 싸다는 건 같다. 한 칸에 열 개가 매달려 있으면 그 칸을 연 뒤 열 번을 훑어야 한다.

꽉 차면 이사한다

그래서 해시테이블은 너무 차기 전에 미리 넓힌다. 200칸 중 150칸쯤 찼으면 400칸짜리를 새로 만든다.

그런데 여기서 배열의 이사와 결정적으로 다른 일이 벌어진다. 칸 수가 바뀌면 계산 결과도 바뀐다. 200으로 나눈 나머지와 400으로 나눈 나머지는 다른 수다. 그러니 옮겨 담는 게 아니라 전부 다시 계산해서 새로 넣어야 한다.

이게 해시테이블에서 가장 비싼 순간이다. 평소에는 O(1)인데 이때 한 번은 전체를 훑는다. 배열 이사와 마찬가지로 나눠 보면 상수지만, 그 한 번의 튐은 실제로 크다. 담을 개수를 대충 알고 있다면 처음부터 크게 만들어두는 게 이 튐을 없앤다.

순서가 없다는 대가

계산으로 자리를 정하니 넣은 순서와 자리 순서가 아무 상관이 없다. 그래서 해시테이블은 순서를 지키지 못한다.

여기서 실무에 바로 걸리는 제약이 나온다.

• 넣은 순서대로 꺼낼 수 없다.
• “가나다순으로 훑기”를 못 한다. 정렬하려면 전부 꺼내서 따로 정렬해야 한다.
• “20에서 50 사이”를 못 뽑는다. 20과 50이 어느 칸에 있는지는 알아도, 그 사이 값들이 어느 칸에 흩어져 있는지는 계산으로 알 수 없다.

마지막 것이 특히 크다. 범위로 묻는 질문에 해시테이블은 아무 도움이 안 된다. 그 자리를 메우는 그릇이 다음 글의 주제다.

자료구조의 해시와 암호의 해시는 다르다

이름이 같아서 자주 겹쳐 읽히는데, 목적이 다르고 요구 조건도 다르다.

특히 마지막이 정반대다. 비밀번호를 저장할 때는 계산이 느린 것이 안전한데, 해시테이블에서 느린 계산은 그냥 손해다. 같은 낱말이지만 하나를 다른 자리에 쓰면 사고가 난다.

실무에서: 그 O(1)이 깨질 때

해시테이블은 O(1)이라고 배우고 실제로도 거의 그렇다. 문제는 거의다. 깨지는 자리가 셋 있고, 셋 다 실무에서 만난다.

계산이 고르게 안 흩어질 때. 직접 만든 객체를 키로 쓰면서 계산식을 대충 짜면 - 예를 들어 전부 같은 값을 내놓으면 - 모든 것이 한 칸에 몰린다. 그러면 해시테이블이 연결리스트 한 줄이 되고 O(n)으로 떨어진다. 겉보기엔 HashMap인데 성능은 리스트다.

일부러 몰리게 만들 때. 같은 칸으로 계산되는 값들을 잔뜩 만들어 보내면 서버가 그 요청 하나로 마비된다. 해시 충돌 공격이라 부르고, 그래서 요즘 언어들은 실행할 때마다 계산식에 무작위 값을 섞는다. 공격자가 미리 몰릴 값을 계산할 수 없게 하려는 것이다.

키를 넣은 뒤에 고칠 때. 이건 조용해서 더 나쁘다. 객체를 키로 넣고 그 객체의 필드를 바꾸면 계산 결과가 달라진다. 그러면 넣어둔 것이 있는데도 못 찾는다. 에러도 안 나고 그냥 없다고 나온다. 키로 쓸 값은 넣은 뒤에 안 바뀌어야 한다.

같은 성질이 훨씬 큰 규모에서도 쓰인다. 데이터를 여러 대에 나눌 때 어느 서버로 보낼지 정하는 것도, 두 테이블을 붙일 때 한쪽을 미리 칸에 담아두는 것도 같은 계산이다. 한 칸에 몰리면 느려진다는 성질까지 똑같이 따라간다.

정리

• 해시테이블은 찾지 않고 계산한다. 넣을 때와 찾을 때 같은 계산을 하면 자리를 기억할 필요가 없다.
• 충돌은 반드시 난다. 담을 것이 칸보다 많아서 나는 것이라 없앨 수 없고, 매달거나 옆으로 가서 다룬다.
• 넓힐 때는 전부 다시 계산해서 새로 넣는다. 평소 O(1)인데 그때 한 번 크게 튄다.
• 대가는 순서다. 정렬도 범위 조회도 못 한다.
• O(1)이 깨지는 건 셋이다. 계산이 몰릴 때, 몰리게 공격당할 때, 넣은 키를 고칠 때.

다음 글은 해시테이블이 못 하는 그 일을 하는 그릇이다. 순서를 지키면서도 반씩 좁혀 들어가는 방법이 있다.