초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.
연락처 앱에 이름을 치면 전화번호가 곧바로 나옵니다. 이름을 저장한 순서대로 배열에 넣어 두면 찾을 때 하나씩 비교하는 선형 탐색을 해야 합니다. 그런데 배열은 인덱스만 알면 비교 없이 한 번에 읽습니다. 이름을 인덱스로 바꿀 수 있다면 어떨까요?
종이 연락처 수첩은 ㄱ, ㄴ, ㄷ 색인이 있어 ‘서연’을 찾을 때 ㅅ 쪽만 펼칩니다. 이름만 보고 펼칠 쪽을 정합니다.
컴퓨터는 글자도 숫자로 저장합니다. 예를 들어 ‘가’는 44032번입니다. 이 글에서는 이름의 글자 번호를 모두 더하고, 그 합을 칸 수로 나눈 나머지를 칸 번호로 쓰겠습니다. 나머지는 언제나 있는 칸을 가리킵니다.
이처럼 찾는 기준이 되는 값을 키(key)라 하고, 키를 칸 번호로 바꾸는 함수를 해시 함수(hash function)라 합니다. 해시 함수가 정해 준 칸에 키와 값을 함께 넣어 두는 배열을 해시 테이블(hash table)이라 합니다. 연락처라면 키는 이름, 값은 전화번호입니다.
99580 ÷ 5 = 19916 … 나머지 0
이름을 ‘준민’으로 바꿔 봅시다.
‘민준’과 ‘준민’처럼 서로 다른 키가 같은 칸에 배정되는 것을 충돌(collision)이라 합니다. 이름은 셀 수 없이 많은데 칸 수는 정해져 있으니 충돌은 피할 수 없습니다. 생일 문제에서 본 것처럼 칸이 넉넉해도 생각보다 자주 부딪힙니다.
충돌이 나면 어떻게 할까요? 칸마다 연결 리스트를 매달아 같은 칸에 배정된 키들을 줄줄이 붙이는 방법이 있습니다. 이를 체이닝 (chaining)이라 합니다. 찾을 때는 해시 함수로 칸을 고른 뒤 그 칸의 줄만 비교합니다.
같은 일을 C로 옮기면 다음과 같습니다. C 문자열에서 한글은 한 글자가 여러 바이트라 이름을 영어로 적었습니다.
출력 없음target을 바꿔 다른 이름도 찾아봅시다.
칸 수를 이름 수보다 넉넉하게 두면 대부분의 칸에는 이름이 없거나 하나뿐이라, 거의 한 번의 비교로 찾습니다. 대신 빈칸만큼 메모리를 더 씁니다.
칸 수를 늘린다고 늘 고르게 퍼지지는 않습니다. 위 데모에서 칸 수를 5에서 8로 늘리면 이름 12개가 오히려 두 칸에만 몰립니다. 이 이름들은 글자 번호의 합이 모두 4의 배수라 8로 나눈 나머지가 0과 4뿐입니다. 더하기만 하는 해시 함수는 이런 치우침을 그대로 칸에 옮깁니다. 칸 수를 13이나 17 같은 소수로 두면 나머지가 4의 배수로 쏠리지 않습니다. 실제 해시 함수는 글자 순서까지 섞어 키를 칸에 고르게 흩뿌립니다.
이번 파트에서는 값을 한 줄로 담는 자료구조를 다뤘습니다. 배열은 몇 번째 값이든 곧바로 읽고, 연결 리스트는 값을 옮기지 않고 넣고 뺍니다. 스택과 큐는 넣은 순서에 따라 꺼내고, 해시 테이블은 키로 곧바로 찾습니다. 하지만 폴더 안에 폴더가 든 것처럼 위아래가 있는 관계는 한 줄로 담기 어렵습니다. 해시 테이블은 칸 번호가 키의 순서와 상관없어서, 이름을 가나다순으로 늘어놓으려면 모든 칸을 모아 정렬해야 합니다. 그래서 다음 파트에서는 값을 갈래로 뻗게 담는 트리를 다룹니다. 첫 글은 트리와 순회입니다.
이 글의 해시 함수(글자 번호의 합을 칸 수로 나눈 나머지)와 체이닝으로 아래 키 12개를 넣습니다. 칸 수는 1부터 1000 가운데 마음대로 고를 수 있습니다. 칸 수를 가장 잘 골랐을 때, 키가 가장 많이 몰린 칸에는 몇 개가 들어 있을까요? 숫자로 답하세요.
가나 나가 가다 다가 나다 다나 가나다 가다나 나가다 나다가 다가나 다나가