[비트 가지고 놀기]이미지로 Hash Table 만들어보기 — 1
글의 순서는 먼저 Hash Table이 무엇인지 알고 이미지의 구조를 파악한 다음 이미지에 Hash Table을 구현하는 순서로 진행하고자 한다.
글쓰는 솜씨가 영 못 미덥겠지만 간단한 수학적 유희에 기반한 내용이니 전산학의 기초가 없어도 흥미롭게 읽을 수 있기를 희망한다. 일단 이해하기 쉽도록 아주 단순하게 만들어 원리부터 알아보고 그 다음에 확장해 볼 생각이다.
다들 종이로 된 사전을 써 본 경험이 있을 것이다. 우리들이 사전에서 원하는 단어를 찾는 과정은 대체로 이렇다.
- 단어의 첫 글자를 떠올린다.
- 사전의 두께를 본다.
- 단어의 첫 글자가 있을 위치를 두께로 어림잡아 짐작하여 사전을 편다.
- 단어의 다음 글자를 찾기 위해 알파벳 순서에 따라서 위치를 조정한다.
- 원하는 단어를 찾을 때까지 4를 반복한다.
컴퓨터는 미리 위치를 알려주지 않는 이상 흔히 다음과 같은 과정으로 단어를 찾는다.
- 첫번째 단어를 찾는 단어랑 비교한다.
- 다음 단어를 찾는 단어랑 비교한다.
- 2를 반복한다.
단어를 통해 뜻을 찾는걸 컴퓨터하게 말하면 Key를 통해 Value를 찾는다고 한다. (‘컴퓨터한’, ‘컴퓨터하게’ 등등 따위의 단어는 이 뒤에 뭔가 고급진 단어가 나타날 수 있다는 걸 의미한다…)
컴퓨터에서도 단어와 뜻을 Key와 Value를 한 쌍으로 저장해서, Key를 통해 Value를 찾을 수 있다. 이걸 Map 혹은 Dictionary라고 한다.
컴퓨터는 우리보다 빨라서 대부분의 경우에 컴퓨터가 먼저 단어를 찾겠지만, 사전에 있는 단어의 개수가 무수히 많을 경우 우리가 먼저 찾을 수도 있다.
가령 무한한 두께를 가진 사전에서 “99999999”(사전의 마지막 단어라고 가정하자)를 찾는다면, 우리는 사전의 마지막 부분을 바로 확인할 수 있지만 컴퓨터는 첫 단어부터 하나씩 비교해나간다. 물론 컴퓨터를 보다 더 똑똑하게 만들 수 있지만 여기선 멍청한 컴퓨터로 하자.
여기 또 다른 사전이 하나가 있다. 역시 Key와 Value를 이용한다.
“1”부터 “99999999”까지 각 숫자단어는 특별한 뜻이 있는데, 이 사전은 각 숫자단어가 어떤 뜻이 있는지 적혀있다. 그리고 한 페이지당 하나의 숫자단어가 설명되어 있다. 1페이지에는 “1”, 333페이지에는 “333”, 739페이지에는 “739”의 내용이 적혀 있다.
만약 우리가 “365”의 의미를 알고 싶으면 365페이지를 펼치면 된다.
컴퓨터도 “365”의 의미를 알고 싶으면 365페이지를 펼치면 된다.
이 사전은 찾고자하는 단어가 어디에 설명되어 있는지 바로 알 수 있다.
좀 컴퓨터하게 말하자면 Key만 보고 Value가 저장된 위치를 알 수 있다.
위에 사전보다 두께는 더 두꺼워질 수 있겠지만, 컴퓨터가 찾는 속도는 훨씬 빨라졌다.
이런 구조를 Hash table라고 한다. 이제 멍청한 컴퓨터로도 빠르게 단어를 찾을 수 있게 되었다.
