Hàm băm có rất nhiều loại và rất nhiều ứng dụng khác nhau (xem wikipedia), do đó, chúng ta sẽ không có đủ thời gian để thảo luận hết được. Hàm băm trong bài này chúng ta thảo luận đó là hàm băm sử dụng để thiết kế bảng băm. Hai yêu cầu chính trong thiết kế hàm băm:

Ta sẽ nhắc lại một số khái niệm cơ bản trong thiết kế bảng băm. Kí hiệu bảng băm với dung lượng $m$ là $T[0,1,\ldots,m-1]$. Ta thực hiện băm $n$ phần tử từ một tập gốc $\mathcal{U}$ có kích thước $|\mathcal{U}|$ lớn hơn nhiều so với $m,n$. Cho trước hàm băm $h(x)$, hai khóa $x,y$ mà $x \not = y$ được gọi là đụng độ nếu $h(x) = h(y)$. Một hàm băm $h(x)$ được gọi là tốt nếu:

$\mathrm{Pr}[h(x) = h(y)] \leq \frac{2}{m} \qquad \forall x \not= y \qquad (1)$

Số 2 ở đây không phải là số đặc biệt. Bất kì hằng số nào khác 2 đều có thể chấp nhận được trong định nghĩa ở trên. Về mặt trực quan, hàm băm tốt là hàm băm có xác suất đụng độ nhỏ.

Trước khi nói kĩ hơn về hàm băm, có một vấn đề mà bài trước chúng ta chưa đụng đến: cái gì có thể băm được. Dường như chúng ta đang mặc định khóa của chúng ta là các số nguyên. Nếu khóa không phải là số nguyên (ví dụ xâu kí tự) thì ta cần một cơ chế để chuyển về số nguyên trước khi băm. Ta gọi số nguyên đó là mã băm (hashcode),

Mã băm

Phần này ta sẽ tìm cơ chế tìm mã băm cho xâu kí tự. Các dạng dữ liệu cơ bản khác đều có thể quy về xâu (ví dụ số 0.12345 có thể coi như là xâu "0.12345").

Thiết kế cơ chế tìm mã băm có thể quy về tìm một hàm $f(x)$ sao cho với mỗi xâu $x$, $f(x)$ là một số nguyên. Hàm $f(x)$ phải có tính chất nếu đầu vào là hai xâu khác nhau thì đầu ra phải là hai mã băm khác nhau vì nếu nhiều xâu có cùng mã băm thì bất kể hàm băm $h(x)$ chọn thế nào thì số lượng đụng độ cũng rất lớn. Nếu coi $f(x)$ là một hàm băm thì hình như ta lại quay trở lại vấn đề ban đầu: tìm hàm băm có xác suất đụng độ nhỏ và có thể tính được một cách hiệu quả.

May mắn thay, khác biệt cơ bản trong thiết kế hàm băm $f(x)$ so với $h(x)$ khiến cho thiết kế $f(x)$ dễ hơn rất nhiều đó là: không gian mã của $f(x)$ có thể lớn hơn rất nhiều $h(x)$. Ví dụ bảng băm có kích thước $1000$, $h(x)$ chỉ được phép băm một khóa vào một trong các giá trị $\{0,1,\ldots,999\}$ ($10^3$ giá trị khác nhau) còn $f(x)$ có thể băm một khóa vào một trong các giá trị $\{0,1,\ldots, 2^{64}-1\}$ ($10^{20}$ giá trị khác nhau) nếu đầu ra của $f(x)$ là một số nguyên không dấu 64 bít.

Coi số thứ tự trong hệ ASCII mỗi kí tự là một chữ số trong hệ cơ số 256. Ví dụ kí tự 'A' tương ứng với chữ số 65 (65 là mã ASCII của A). Một họ hàm băm khá phổ biến thường dùng để thiết kế $f(x)$ đó là băm đa thức (polynomial hashing):

Nếu chọn $b = 256$ thì $f(s)$ sẽ duy nhất với mọi $s$, i.e, $s_1 \not= s_2 \Leftrightarrow f(s_1) \not= f(s_2)$. Tuy nhiên, $b$ càng lớn thì $f(s)$ sẽ càng lớn. Do đó, thông thường người ta sẽ chọn $b$ là một số nguyên tố không quá lớn. Ngôn ngữ Java mặc định chọn $b = 31$ để tính $f(s)$.

Một điểm mạnh của băm đa thức đó là nó có thể tính được hiệu quả bằng phương pháp Horner.

$f(s) = (\ldots ((s[0]*b + s[1])*b + s[2])*b + \ldots)*b + s[n-1] \qquad (3) $

Mình sẽ không đi sâu thêm vào các hàm băm kiểu này nữa. Một số hàm băm khác bạn đọc có thể tham khảo thêm tại blog khoa học máy tính. Hai điểu mà mình muốn nhấn mạnh trong phần này đó là:

1. Chúng ta có cách để chuyển các kiểu khác về số nguyên trước khi băm, do đó, ta có thể coi như các khóa đầu vào trong thiết kế bảng băm là các số nguyên.
2. Thiết kế hàm băm chuyển kiểu dễ hơn nhiều so với thiết kế hàm băm sử dụng trong bảng băm.

Hàm băm

Như đã nói trong bài trước, một hàm băm tốt không thể là một hàm băm tất định (deterministic) được vì theo nguyên lí nhốt chim, ít nhất $\frac{|U|}{m}$ phần tử sẽ có cùng mã băm. Một hàm băm tốt thường sẽ được chọn ngẫu nhiên (trước khi băm) từ một họ các hàm băm được thiết kế sẵn. Trong phần này mình đi sâu hơn vào hai họ hàm băm đã giới thiệu ở bài trước:

Họ hàm băm nhân (multiplicative hashing): Họ hàm băm nhân được Carter và Wegman [5] giới thiệu năm 1977. Ta chọn một số nguyên tố $p$ lớn hơn $|U|$ và định định nghĩa:

$h_r(x) = (xr \mod p) \mod m \qquad (4)$

Họ $H=\{h_1(x),h_2(x),\ldots,h_{p-1}(x)\}$ được gọi là họ hàm băm nhân. Ta sẽ chứng minh nếu chọn ngẫu nhiên một hàm băm $h_r(x)$ từ họ $\mathcal{H}$ thì xác suất đụng độ là nhỏ.

 
Chứng minh Kí hiệu $\gcd(a,b)$ là ước chung lớn nhất của hai số $a$ và $b$. Do $p$ là một số nguyên tố, $\gcd(x,p) = 1$. Theo thuật toán Euclidean mở rộng, tồn tại duy nhất hai số nguyên dương $y,z$ (modulo $p$) sao cho:

$xy + pz = 1$

Do đó, $xy \equiv 1 \mod p$, dpcm

Giả sử ta chọn ngẫu nhiên $r \in \{1,2,\ldots,p-1\}$. Đụng độ sẽ xảy ra khi và chỉ khi tồn tại hai khóa $x \not = y$ sao cho:

$\begin{array} {l} h_r(x) = h_r(y) & \Leftrightarrow (xr \mod p) \mod m = (yr \mod p) \mod m \\ & \Leftrightarrow ((x-y)r \mod p) \equiv 0 \mod m \\ & \Leftrightarrow (x-y)r = km \mod p \\ & \Leftrightarrow r = km(x-y)^{-1} \mod p \\ \end{array} \qquad (5)$

Ở đây $k$ có thể nhận một trong các giá trị $\{0,1,\ldots, \frac{p}{m}\}$ vì $km \leq p$. Mỗi giá trị của $k$ sẽ tương ứng với một giá trị của $r$. Do đó, đụng độ chỉ xảy ra khi $r$ nhận một trong $\frac{p}{m}+1$ giá trị thỏa mãn $(5)$. Do ta chọn $r$ chọn ngẫu nhiên trong $\{1,\ldots,p-1\}$ và $x,y$ là hai khóa cho trước, xác suất ta chọn được $r$ như vậy là:

$ (\frac{p}{m} ) / (p-1) \leq \frac{2}{m} \qquad (6)$

Họ hàm băm nhân nhị phân Họ hàm băm nhân này được giới thiệu bởi Martin, Hagerup, Katajainen và Penttonen [6] năm 1977 để giải quyết bài toán cặp điểm gần nhất (closest pair). Ưu điểm của họ hàm băm này so với họ hàm băm nhân ở trên là: không cần đến số nguyên tố lớn và mã bă có thể tính được chỉ sử dụng các thao tác bít đơn giản.

Gọi $w$ là số nguyên dương nhỏ nhất sao cho $|\mathcal{U}| \leq 2^{w}$. Chọn $m = 2^{\ell}$. Với mỗi số nguyên dương lẻ $r$ không lớn quá $2^{w}$, ta định nghĩa:

$g_r(x) = \lfloor \frac{(rx) \mod 2^{w}}{2^{w-\ell}} \rfloor \qquad (7)$

Họ hàm băm ta xây dựng là $\mathcal{G}= \{g_1(x),g_3(x),\ldots, g_{2^{w}-1}(x)\}$.

Chứng minh xác suất đụng độ là nhỏ nếu ta chọn ngẫu nhiên một hàm băm $g_r$ từ $\mathcal{G}$ phức tạp hơn so với chứng minh ở trên một chút. Trước hết ta sẽ chứng minh:

 
Chứng minh: Giả sử $xr \mod 2^w = yr\mod 2^w$, ta suy ra $(x-y)r \mod 2^w = 0$. Do $r$ lẻ và $-2^w + 1 \leq x-y \leq 2^w-1$, đẳng thức chỉ xảy ra khi $x = y$. Điều này trái với giả thiết $x \not= y$, dpcm.

Về mặt trực quan, Lemma 2 cho chúng ta biết hàm $f(x) = xr \mod 2^w$ với $r$ cho trước là một đơn ánh (injective map) từ tập $\{0,1,\ldots, 2^w-1\}$ vào chính nó. Do miền xác định và miền giá trị bằng nhau, ta suy ra hàm $f(x)$ là một song ánh (bijective map). Ý nghĩa của tính chất này đó là với một khóa $x$ cố định, việc chọn $r$ ngẫu nhiên tương đương với việc chọn $f(x)$ ngẫu nhiên trong tập $\{0,1,\ldots, 2^w-1\}$. Ta sẽ sử dụng tính chất này để chứng minh xác suất đụng độ của $g_r(x)$ là nhỏ.

Theo hình minh họa ở trên, mã băm đầu sẽ là $\ell$ bít cao nhất của $f(x)$. Nhắc lại $f(x) = xr \mod 2^w$. Giả sử xảy ra đụng độ giữa hai khóa $x,y$. Không mất tính tổng quát, ta giả sử $x$ > $y$. Ta có $g_r(x) = g_r(y)$ khi và chỉ khi $\ell$ bít cao nhất của $f(x)$ và $f(y)$ là giống nhau. Từ đó ta suy ra $\ell$ bít cao nhất của $f(x) - f(y)$ phải là một dãy $\ell$ số $0$ hoặc một dãy $\ell$ số $1$. Ta có:

$f(x) - f(y) = (x-y)r \mod 2^w \qquad (8)$

Với $x,y$ cho trước, theo nhận xét ở đoạn trước, việc chọn $r$ ngẫu nhiên tương đương với chọn $(x-y)*r$ ngẫu nhiên trong $\{0,1,\ldots,2^w\}$. Do đó, xác suất ta chọn được ngẫu nhiên một số $w$ bít có $\ell$ bít cao nhất là toàn $0$ hoặc toàn $1$ là $2/2^\ell$. Nhắc lại $m = 2^\ell$. Như vậy:

$\mathrm{Pr}_{g_r(x) \in \mathcal{G}}[x = y] \leq \frac{2}{m} \quad \forall x \not= y \qquad (9)$

Tham khảo

[1] Donald E. Knuth. The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998.
[2] Jeff Erickson. Lecture Notes on Hashing . UIUC, 2013.
[3] Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson. Introduction to Algorithms (2nd ed.). Chapter 12. McGraw-Hill Higher Education, 2001.
[4] Procul.org: http://www.procul.org/blog/2012/04/18/ham-bam-fnv/, accessed 20/04/2016.
[5] J.L. Carter and M.N. Wegman. 1977. Universal classes of hash functions (Extended Abstract). In STOC' 77, 106-112.
[6] D. Martin, T. Hagerup, J. Katajainen, and M. Penttonen. A reliable randomized algorithm for the closest-pair problem. Journal of Algorithms 25, No. 1 (1997): 19-51.