Bảng băm và các cơ chế giải quyết xung đột cơ bản -- Hashing and collision handling

Bài này mình lượt qua cấu trúc dữ liệu bảng băm (hash table), hàm băm (hash functions) và một số cơ chế giải quyết xung đột (collision handling). Mục tiêu của bài này là đưa ra một cách nhìn tổng quan về cách thức thiết kế bảng băm. Mọi cơ sở toán học mình sẽ viết và link trong các bài sau.
Bảng băm

Bảng băm là một cấu trúc dữ liệu lưu trữ một tập hợp cho phép ta có thể nhanh chóng xác định xem một phần tử nào đó có nằm trong tập hợp hay không.

 

Một cấu trúc dữ liệu mà chúng ta cũng thường xuyên áp dụng cho thao tác tìm kiếm đó là cây cân bằng (ví dụ cây AVL hoặc cây Red-Black). TreeMap trong Java chính là sử dụng cây Red-Black để hỗ trợ tìm kiếm. Do tính cân bằng, cấu trúc dữ liệu cây này sẽ cho phép chúng ta thực hiện tìm kiếm trong thời gian $O(\log n)$. Bảng băm chúng ta sẽ thảo luận trong bài này sẽ cho phép chúng ta thực hiện thao tác tìm kiếm trong thời gian kì vọng $O(1)$.

Gọi $A[0,1,\ldots,n-1]$ là tập $n$ phần tử ta muốn lưu trữ trong bảng băm. Các phần tử của tập hợp mà chúng ta lưu trữ thường từ một tập lớn hơn $\mathcal{U}$ mà ta gọi là tập gốc (ground set). Tập gốc ta xét ở đây có lực lượng hữu hạn nhưng rất lớn so với $n$ và $m$. Ví dụ: nếu tập gốc là tập các tên người với tối đa là $30$ kí tự thì kích thước tối đa của tập gốc là $29^{30}$ (ta sử dụng bảng chữ cái tiếng Việt). Nếu giả sử tập dữ liệu trong bảng băm là tên của người thực thì con số $29^{30}$ lớn hơn rất nhiều so với $10^8$ (dân số Việt Nam).

Bảng băm là một mảng $T[0,1,\ldots,m-1]$ có kích thước $m$. Để lưu trữ dữ liệu vào bảng băm, ta sẽ dùng một hàm băm (hash function). Một hàm băm:

$h : \mathcal{U} \rightarrow \{0,1,\ldots,m-1\} \qquad (1)$

là một ánh xạ gán cho mỗi phần tử của tập $\mathcal{U}$ một vị trí trong bảng $T$. Cụ thể, phần tử $x$ sẽ được lưu tại ô $T[h(x)]$ của bảng và ta nói $x$ được băm vào vị trí $h(x)$ và $h(x)$ được gọi là mã băm (hash code) của $x$. Xem hình minh họa dưới đây.

hash-example

Hai thao tác chính của bảng băm đó là: đưa một phần tử mới vào bảng băm và tìm xem một phần tử có nằm ở trong bảng băm hay không. Giả mã:

PutToTable(key $x$, $h$):
    $T[h(x)] \leftarrow x$

 

Lookup(key $x$, $h$):
    if $T[h(x)] = x$
        return Yes
    return No

 

Do $\mathcal{U}$ lớn hơn $m$, theo nguyên lí nhốt chim, một hoặc nhiều phần tử của tập $\mathcal{U}$ có thể sẽ được băm vào cùng một vị trí của bảng. Ta gọi hiện tượng đó là xung đột (collision). Do xung đột làm quá trình tìm kiếm trở nên phức tạp hơn, ta sẽ cần một chiến lược để đối phó với nó mà ta gọi là chiến lược giải quyết xung đột. Trước khi thảo luận các cách chiến lược này, ta sẽ thảo luận về cách chọn hàm băm trước vì xung đột nhiều hay ít đều phụ thuộc vào hăm băm mà ta chọn.

Hàm băm

Tuy xung đột không thể tránh được, ta có thể làm giảm được xung đột bằng cách chọn một hàm băm tốt. Chú ý ta chỉ lưu $n$ phần tử của tập gốc vào bảng. Do ta có thể không có bất kì thông tin nào về các phần tử mà ta sẽ lưu trong bảng, ta không thể chọn một hàm băm $h$ tất định được vì theo nguyên lí nhốt chim, với bất kì hàm băm $h$ nào, ít nhất $\frac{|\mathcal{U}|}{m}$ phần tử trong tập $\mathcal{U}$ sẽ có cùng một mã băm. Do đó, nếu $n$ phần tử của tập hợp ta muốn lưu trong bảng đều có cùng mã băm thì sẽ là một điều vô cùng tồi tệ. Đây chính là lúc ta cần đến ngẫu nhiên.

Thay vì sử dụng một hàm băm cố định, ta sẽ chọn ra ngẫu nhiên một hàm băm $h$ từ một họ các hàm băm $\mathcal{H}$ mà ta thiết kế từ trước sao cho khi chọn ngẫu nhiên như vậy, xác suất đụng độ là nhỏ:

$\mathrm{Pr}_{h \in \mathcal{H}}[h(x) = h(y)] \sim \frac{1}{m} \quad \mbox{ for any } x\not=y \qquad (2)$

Ta dùng dấu xấp xỉ ở trên vì các phân tích dưới đây sẽ không thay đổi nhiều nếu thay 1 bằng một hằng số $c$ bất kì.

Ví dụ 1(băm nhân-multiplicative hashing) Ta chọn một số nguyên tố $p$ lớn hơn $|\mathcal{U}|$ và định định nghĩa:

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

Họ hàm băm ta xây dựng là $\mathcal{H}= \{h_1(x),h_2(x),\ldots, h_{p-1}(x)\}$.

Ví dụ 2 (băm nhân nhị phân-binary multiplicative hashing) Gọi $w$ là số nguyên dương nhỏ nhấ tsao 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 (4)$

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)\}$.

Trong bài cơ sở toán học của bàm băm, nếu chọn ngẫu nhiên một hàm băm $h_r(x)$ (hoặc $g_r(x)$) từ $\mathcal{H}$ ( hoặc từ $\mathcal{G}$) để thực hiện băm thì xác suất đụng độ sẽ là cỡ $\frac{1}{m}$.

Hàm băm tốt, bên cạnh tính chất làm giảm sự đụng độ, phải là một hàm có thể nhanh chóng tính được mã băm với một khóa cho trước. Rõ ràng một hàm băm có xác xuất đụng độ nhỏ nhưng mỗi lần tính mã băm của một khóa mất đến vài giây thì ta không nên chọn. Do đó, việc thiết kế hàm băm tốt sẽ là một bài toán cực kì khó. Trong hai họ hàm băm ở hai ví dụ trên, họ hàm băm trong ví dụ 2 có thể được tính nhanh hơn rất nhiều họ hàm băm trong ví dụ 1 vì các thao tác mod và chia đều được thực hiện tương đương bằng thao tác $\&$ và dịch phải (shift-right):

$g_r(x) = \lfloor \frac{(rx) \mod 2^{w}}{2^{w-\ell}} \rfloor = ((rx) \&((1 \ll w)-1)) \gg (1 \ll (w - \ell))$

Xem thêm tại các kĩ thuật xử lí bít.

Remark. Có lẽ nhiều bạn đọc biết một cách chọn hàm băm rất phổ biến đó là $h(x) = x \mod m$. Như đã nói ở trên, đây là một ý tưởng tồi tệ vì hàm băm này là một hàm băm tất định. Nếu các khóa đều có cùng đồng dư với $m$ thì đụng độ sẽ rất lớn. HashMap của Java jdk-7 sử dụng hàm băm này $h(x) = x \mod m$ với $m=2^k$.

// Returns index for hash code h.
static int indexFor(int h, int length) {
return h & (length-1);
}

Ưu điểm khi chọn $m = 2^k$ chính là: $x \mod 2^k \equiv x\&(2^k-1)$, do đó, hàm băm được tính rất hiệu quả bằng các phép toán bit. Điểm yếu, như đã nói ở trên, là nếu các giá trị đầu vào có cùng $k$ bít cuối (cùng đồng dư với $m$) thì sẽ được băm vào cùng một vị trí. Để tránh điều này, trước khi băm, HashMap của java sẽ dùng một hàm để "băm lại" hashcode đầu vào. Mục đích của băm lại là làm cho đầu vào trông giống ngẫu nhiên.

/* Applies a supplemental hash function to a given hashCode, which
* defends against poor quality hash functions.  This is critical
* because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

Dù như vậy thì về mặt lý thuyết, đây cũng không phải cách tốt. Bạn đọc nếu có sử dụng HashMap của Java thì cũng nên biết rõ những vấn đề này.

Tóm lại hai điều cần nhớ khi thiết kế hàm băm tốt:

  1. Xác suất đụng độ nhỏ.
  2. Hàm băm có thể tính được rất nhanh.

Giả sử ta đã có một hàm băm tốt (thỏa mãn $(2)$), sau đây ta sẽ thảo luận các chiến lược giải quyết xung đột.

Giải quyết xung đột

Ta sẽ nghiên cứu ba phương pháp giải quyết xung đột chủ yếu: xích ngăn cách (separate chaining), băm địa chỉ mở (open addressing) và băm hoàn hảo (perfect hashing).

Xích ngăn cách

Đây có lẽ là cách thức giải quyết xung đột đơn giản nhất và trực quan nhất. Ta sẽ dùng một danh sách liên kết, gọi là xích ngăn cách, để liên kết các phần tử có cùng mã băm (xem hình dưới đây). HashMap trong Java sử dụng ý tưởng này.

chaining-table

Giả mã:

PutToChainingTable(key $x$, $h$):
    add $x$ to list $T[h(x)]$

 

LookupChainingTable(key $x$, $h$):
    List $L \leftarrow T[h(x)]$
    for each element $\ell $ in $L$
        if $\ell = x$
            return Yes
    return No

 
Code C:

#define YES 1
#define NO 0

// Hash function specification
// We use binary multiplicative hash function
// See see http://www.giaithuatlaptrinh.com/?p=967 for more details.
int  l = 10;
int w = 20;
int r;
int m;		// the table has size 2^10

// Linked list for chaining
typedef struct llnode{	// define a linked list node
int x;
struct llnode *next;
}llnode;

llnode **T;	// the hash table

void put_to_table(int x){
T[hash(x)] = add_to_list(T[hash(x)],x);
}

int lookup(x){
llnode *L = T[hash(x)];
while(L != NULL){
if(L->x  == x) {
printf("%d is at location %d of the table\n", x, hash(x));
return YES;
}
L = L->next;
}
printf("%d Not found!\n",x);
return NO;
}

// we use binary multiplicative hash funciton.
int hash(int x){
return ((r*x)&((1<<w)-1))>>(w-l);
}
// add an element to the head of a linked list
llnode* add_to_list(llnode *head, int a){
llnode *node = (llnode *)malloc(sizeof(llnode));
node->x = a;
node->next = head;
head = node;
return head;
}

Hệ số tải: (load factor) Ta đinh nghĩa hệ số tải $\alpha$ như sau:

$\alpha = \frac{n}{m} \qquad (5)$

 

Gọi $\ell(x)$ là biến ngẫu nhiên chiều dài của danh sách chứa khóa $x$. Trong bài cơ sở toán học của xích ngăn cách, ta sẽ chứng minh:

Theorem 1:

$ E[\ell(x)] = \frac{n}{m} = \alpha \qquad (6)$

 

Như vậy, theo $(6)$, kì vọng thời gian để tìm kiếm một số $x$ tỉ lệ với hệ số tải $\alpha$. Điều này cũng khá trực quan vì nếu bảng càng lớn thì khả năng đụng độ càng nhỏ. Hệ số tải mặc định trong HashMap của Java là 0.75.


Remark: Phương trình $(6)$ cho chúng ta biết kì vọng chiều dài của danh sách $T[h(x)]$ là $O(1)$ (giả sử hệ số tải là $\alpha = 1$). Tuy nhiên, mình muốn lưu ý bạn đọc, chiều dài của danh sách dài nhất trong tất cả các danh sách của bảng là cỡ $O(\frac{\log n}{\log\log n})$ (chứng minh sử dụng mô hình ném bóng vào rổ, chi tiết bạn đọc xem thêm tại bài cơ sở toán học của xích ngăn cách). Điều đó cho thấy trong trường hợp xấu nhất, ta có thể phải trả một thời gian tìm kiếm xấp xỉ $\log n$. May mắn là sẽ không có nhiều danh sách trong bảng có chiều dài lớn như vậy vì kì vọng chiều dài chỉ là hằng số mà thôi.

Một ý tưởng khác để giảm chiều dài của danh sách dài nhất đó là sử dụng hai hàm băm $h_1,h_2$ để băm vào hai vị trí khác nhau của bảng. Trong hai danh sách $T[h_1(x)], T[h_2(x)]$, nếu danh sách nào ngắn hơn thì ta sẽ đặt phần tử $x$ vào đó. Khi tìm kiếm thì ta phải duyệt cả hai danh sách để tìm. Cũng theo mô hình ném bóng vào rổ (phân tích phức tạp hơn rất nhiều, xem thêm tại bài cơ sở toán học của xích ngăn cách), danh sách dài nhất có kì vọng chiều dài cỡ $O(\log\log n)$. Hàm này gần như có thể coi là hằng số.

Băm địa chỉ mở

Trong phương pháp giải quyết xung đột bằng xích ngăn cách, khá nhiều ô của bảng rỗng trong khi một số ô khác lại chứa khá nhiều phần tử. Ngoài ra, ta cần duy trì một danh sách các con trỏ để liên kết các phần tử lại với nhau. Các liên kết này đương nhiên là sẽ tốn thêm bộ nhớ.

Ý tưởng của băm địa chỉ mở (open addressing) là mỗi ô của bảng chỉ lưu duy nhất một phần tử, do đó ta không cần danh sách móc nối. Chú ý:

Trong băm địa chỉ mở, ta giả sử số hệ số tải $\alpha$ luôn nhỏ hơn $1$ (hay nói cách khác, $n$ < $m$).

 

Xung đột sẽ được băm địa chỉ mở giải quyết bằng cách sử dụng $m$ hàm băm độc lập $h_0,h_1,\ldots,h_{m-1}$, sao cho:

Với bất kì phần tử $x$ nào, $m$ giá trị $h_0(x),h_1(x),\ldots,h_{m-1}(x)$ đôi một khác nhau; do đó, $\{h_0(x),h_1(x),\ldots,h_{m-1}(x)\}$ là một hoán vị của $\{0,1,\ldots,m-1\}$.

 

Khi băm một khóa $x$, ta sẽ lần lượt kiểm tra từ ô $h_0(x)$ của bảng cho đến $h_{m-1}(x)$. Nếu tìm thấy một ô trống đầu tiên thì lưu $x$ vào đó. Do $h_0(x),h_1(x),\ldots,h_{m-1}(x)$ là một hoán vị của $\{0,1,\ldots,m-1\}$, quá trình tìm kiếm ô trống luôn kết thúc sau tối đa $m$ bước.

Giả mã:

PutToOpenAddressingTable(key $x$, $\{h_0,\ldots,h_{m-1}\}$):
    $i \leftarrow 0$
    while $T[h_i(x)] \not= $ Null
        $i \leftarrow i+1$
    $T[h_i(x)] \leftarrow x$

 

Hình ví dụ dưới đây minh họa băm 4 khóa vào bảng $T$ sử dụng địa chỉ mở. Ngay lần đầu tiên băm khoá "Huy" sử dụng $h_0(x)$, ta tìm được ô trống, do đó, ta đặt khóa "Huy" vào ô trống này. Khi băm khóa "Hà" lần đầu tiên (sử dụng $h_0(x)$) vào ô 7, ta thấy ô này đã có khóa. Do đó, ta băm lần hai (sử dụng $h_1(x)$) vào ô 5. Ô 5 cũng đã có khóa, do đó, ta phải băm lần ba (sử dụng $h_2(x)$) vào ô 2. Vì ô 2 trống, ta đặt khóa "Hà" vào đó. Hình $(5)$ chính là trạng thái của bảng băm sau khi đã băm 4 khóa.

open-addressing

Để tìm kiếm bảng băm địa chỉ mở ta sẽ thực hiện dò bảng (probing): bắt đầu từ vị trí $h_0(x)$ cho đến vị trí $h_{m-1}(x)$. Nếu $x$ có trong bảng thì ta sẽ tìm được $x$ ở một ô $T[h_i(x)]$ nào đó. Nếu $x$ không chứa trong bảng, trong quá trình dò, ta sẽ bắt gặp một ô rỗng hoặc duyệt qua đến $h_{m-1}(x)$ mà vẫn chưa tìm được $x$.

Giả mã:

LookupOpenAddressingTable(key $x$, $\{h_0,\ldots,h_{m-1}\}$):
    $i \leftarrow 0$
    while $T[h_i(x)] \not= x$
        if $T[h_i(x)] = $ Null
            return No
        $i \leftarrow i+1$
    if $i \leq m-1$
        return $h_i(x)$        $\ll$ found $x$ in the hash table $\gg$
    return No

 
Code C:

#define YES 1
#define NO 0

#define LINEAR_PROBING 1
#define QUADRATIC_PROBING 2
#define BINARY_PROBING 3

int probing_mode = LINEAR_PROBING;
// Hash function specification
// We use binary multiplicative hash function
// See http://www.giaithuatlaptrinh.com/?p=967 for more details.
int  l = 10;
int w = 20;
int r;
int m;		// the table has size 2^10

int* T;

// put a key x into the table
void put_to_table(int x){
int i = 0;
while(T[hash(i,x)] != -1){
i++;
}
T[hash(i,x)]  = x;
}

int lookup(x){
int i = 0;
while(T[hash(i,x)] != x){
if(T[hash(i,x)] == -1){
printf("%d is not in the table\n",x);
return NO;
}else i++;
}
if(i &lt;= m-1){
printf("%d is at location %d of the table\n", x, hash(i,x));
printf("the number of probing is %d \n", (i+1));
return hash(i,x);
}
return NO;
}

int hash(int i, int x){
switch(probing_mode){
case LINEAR_PROBING:
return ((((r*x)&amp;((1&lt;&lt;w)-1))&gt;&gt;(w-l))+i)&amp;(m-1);				// since m is a power of 2 =&gt; x mod m =  x&amp;(m-1)
break;
case QUADRATIC_PROBING:
return ((((r*x)&amp;((1&lt;&lt;w)-1))&gt;&gt;(w-l))+i*i)&amp;(m-1);
break;
case BINARY_PROBING:
return (((r*x)&amp;((1&lt;&lt;w)-1))&gt;&gt;(w-l))^i;
break;
default:
printf("No default provided!\n");
break;
}
}

Trong phần cơ sở toán học của băm địa chỉ mở (sẽ liên kết sau khi viết), ta sẽ chứng minh hai định lý sau:

Theorem 2 Số lần dò kì vọng để tìm kiếm một khóa không có trong bảng là:

$ \frac{1}{1-\alpha} \qquad (7)$

 

Theorem 3 Số lần dò kì vọng để tìm kiếm một khóa có trong bảng là:

$ \frac{1}{\alpha}(1 + \ln \frac{1}{1-\alpha} ) \qquad (8)$

 
Remark: Hai định lý trên cho chúng ta biết thời gian trung bình khi dò một khóa trong bảng. Tuy nhiên, trong trường hợp xấu nhất, số phép dò kì vọng là $O(\log n)$. Chúng ta sẽ tìm hiểu thêm tại phần cơ sở toán học.

Trong thực tế, việc thiết kế $m$ hàm băm ngẫu nhiên độc lập thỏa mãn mã băm đôi một khác nhau với một khóa cho trước là việc vô cùng khó. Cho dù ta có thực hiện được thì chi phí thời gian có lẽ cũng không nhỏ. Do đó, trong thực tế, ta chấp nhận các hàm băm "phụ thuộc" với nhau ở một mức độ nào đó, mỗi mức độ cho chúng ta một phép dò khác nhau. Ta sẽ nghiên cứu: dò tuyến tính, dò nhị phân, dò bậc hai và băm kép.

Dò tuyến tính

Trong phép dò tuyến tính (linear probing), ta sẽ chỉ sử dụng một hàm băm tốt $h(x)$ để định nghĩa $m$ hàm băm như sau:

$h_i(x) = (h(x) + i )\mod m \qquad 0 \leq i \leq m-1 \qquad (9)$

 

Điểm mạnh của phương pháp dò tuyến tính này là thực thi đơn giản. Tuy nhiên, các giá trị băm sẽ có xu hướng tụm lại với nhau thành một dãy con liên tục của $T$. Ngoài ra, khi hệ số tải gần bằng 1 thì tìm kiếm với dò tuyến tính cực kì kém hiệu quả.

Dò nhị phân

Dò nhị phân (binary probing) vừa lợi dụng điểm mạnh của dò tuyến tính, vừa có thể tính nhanh được trong thực tế. Như đã nhắc đến ở trên, chọn $m = 2^\ell$ cho phép chúng ta chuyển các thao tác nhân, chia, mod về các thao tác xử lí bít. Do đó, ta có thể tính được hàm băm rất nhanh. Dò nhị phân cũng sử dụng tư tưởng này. Chọn $m = 2^\ell$ và sử dụng một hàm băm tốt $h(x)$ để định nghĩa $m$ hàm băm:

$h_i(x) = (h(x) \oplus i ) \qquad 0 \leq i \leq m-1 \qquad (10)$

 
Trong đó $\oplus$ là phép XOR bít.

Dò bậc hai

Tương tự như trong phép dò tuyến tính, nhưng thay vì sử dụng hàm tuyến tính, trong phép dò bậc hai (quadratic probing), ta sẽ dùng hàm bậc 2 để thiết kế $m$ hàm băm :

$h_i(x) = (h(x) + i^2 )\mod m \qquad 0 \leq i \leq m-1 \qquad (11)$

 

Phương pháp dò bậc hai về mặt lý thuyết tốt hơn dò tuyến tính. Ta sẽ đi sâu chi tiết trong bài sau.

Băm kép

Băm kép (double hashing) sử dụng hai hàm băm độc lập $h(x), g(x)$ để định nghĩa $m$ hàm băm :

$h_i(x) = (h(x) + ig(x) )\mod m \qquad 0 \leq i \leq m-1 \qquad (12)$

 

Cũng như dò bậc hai, phương pháp này tốt hơn về mặt lý thuyết. Tuy nhiên, trong thực tế, phương pháp này sẽ hơi chậm hơn.

Băm hoàn hảo

Như chúng ta thảo luận ở phần xích ngăn cách, mặc dù kì vọng thời gian tìm kiếm là $O(1)$ (giả sử hệ số tải là hằng số), trong trường hợp xấu nhất, thời gian tìm kiếm có thể lên tới gần xấp xỉ $O(\log n)$. Đôi khi $O(\log n)$ là một con số không hề nhỏ.

Ta có thể làm giảm hiệu ứng xấu nhất đó bằng cách giảm hệ số tải (tăng kích thước của bảng băm). Giả sử chúng ta sử dụng bảng băm với số lượng ô $m = O(n^2)$. Ta sẽ chứng minh ngắn gọn, nếu ta chọn như vậy, số lượng đụng độ chỉ là hằng số. Nếu số lượng đụng độ là hằng số thì đương nhiên danh sách dài nhất trong bảng cũng có kì vọng chiều dài là hằng số.

Gọi $C_{x,y}$ là biến ngẫu nhiên 0/1 trong đó $C_{x,y} = 1$ nếu hai khóa $x,y$ xảy ra đụng độ, i.e, $h(x) = h(y)$, và $C_{x,y} = 0$ nếu ngược lại. Theo $(2)$, $\mathrm{Pr}[C_{x,y}] = \frac{1}{m}$. Gọi $C$ là tổng số đụng độ trong bảng băm. Ta có:

$C = \sum_{x,y\in S, x\not=y}C_{x,y}$

Do $C_{x,y}$ là biến ngẫu nhiên 0/1, $E[C_{x,y}] = \mathrm{Pr}[C_{x,y}]$. Ta có:

$E[C] = \sum_{x,y\in S, x\not=y}E[C_{x,y}] = {n \choose 2}\frac{1}{m} = O(1) \qquad (13)$

Tuy nhiên, $O(n^2)$ là một con số quá lớn và không thực tế. Tưởng tượng ta chỉ băm 1000 phần tử mà cần tới 1 triệu bộ nhớ. Băm hoàn kết hợp cả nhận xét trên và ý tưởng của xích ngăn cách để làm giảm thời gian tìm kiếm xấu nhất xuống $O(1)$ mà bảng chỉ cần bộ nhớ $O(n)$ (nó được gọi là băm hoành hảo là vì thế).

Băm hoàn hảo sẽ sử dụng hai hàm băm tốt $\{h(x),g(x)\}$ và bảng băm hai chiều $T[1,2,\ldots,m][\ldots]$. Mỗi hàng của bảng băm $T[i]$ sẽ được coi như một bảng băm phụ, có kích thước phụ thuộc vào đầu vào. Khi băm vào bảng, ta thực hiện băm theo 2 pha: Pha đầu tiên, sử dụng $h$ để băm $x$ vào hàng $h(x)$ của bảng $T$. Gọi $C[i]$ là số lượng phần tử được băm cùng vào hàng thứ $i$ sau pha đầu tiên. Trong pha thứ 2, với mỗi hàng $i$, ta cấp phát một bộ nhớ $C[i]^2$ cho hàng $T[i]$. Sau đó, ta coi hàng này như một bảng băm và dùng $g$ để băm các phần tử $x$ có cùng mã băm $i$ vào ô $g(x)$ của hàng này. Đụng độ lần 2 này sẽ được giải quyết sử dụng xích ngăn cách. Xem hình minh họa dưới đây.

perfect-hash

Như phân tích ở trên, do bảng băm phụ này có kích thước là bình phương số lượng phần tử được lưu trong hàng, đụng độ khi băm lần 2 này là $O(1)$. Do đó, tìm kiếm có thể được thực hiện trong $O(1)$.

Một điểm cần lưu ý nữa là kích thước của các bảng băm con tương ứng với các hàng khác nhau có thể khác nhau. Cụ thể, bảng băm con thứ $i$ (là $T[i]$) có kích thước $C[i]^2$. Do đó, khi băm vào bảng băm con $T[i]$ trong pha 2 sử dụng hàm băm $g(x)$, địa chỉ thực sự trong bảng băm con là $g(x) \mod C^2[i]$.

Giả mã:

PutToPerfectTable($A[1,2,\ldots,n]$, $\{h,g\}$):
    $C[0,\ldots,m-1] \leftarrow \{0,\ldots,0\}$
    for $i \leftarrow 1$ to $n$
        $C[h(A[i])] \leftarrow C[h(A[i])] + 1$
    for $i \leftarrow 0$ to $m-1$
        allocate $C[i]^2$ memory slots to row $T[i]$ of 2D table $T[][]$
    for $i \leftarrow 1$ to $n$
        $j \leftarrow h(A[i])$
        $k \leftarrow g(A[i]) \mod C^2[j]$
        add $A[i]$ to list $T[j][k]$

 
Để tìm một khóa $x$, theo định nghĩa, khóa này nằm trong danh sách $T[h(x)][g(x)]$. Do đó, ta chỉ cần duyệt qua danh sách đó. Theo phân tích ở trên, thời gian duyệt qua danh sách trong trường hợp xấu nhất là $O(1)$.

LookupPerfectTable(key $x$, $\{h,g\}$, $C[0,\ldots,m-1]$):
    $i \leftarrow h(x)$
    $j \leftarrow g(x) \mod C^2[i]$
    List $L \leftarrow T[i][j]$
    if $L = $ Null
        return No
    for each element $y$ in $L$
        if $y = x$
            return Yes
    return No

 
Code C:

#define YES 1
#define NO 0

// Hash function specification
// We use binary multiplicative hash function
// For more details see http://www.giaithuatlaptrinh.com/?p=967
int  l = 10;
int w = 20;
int r_h;
int r_g;
int m;		// the table has size 2^10

// Linked list for chaining
typedef struct llnode{	// define a linked list node
int x;
struct llnode *next;
}llnode;

llnode ***T;	// the hash table
int *C;			// the counters

int n;	// the number of items to be stored in the table is 2^9; the load factor is 50%

// put a key x into the table and return the location of the table that stores x
void put_to_table(int *A, int n){
C = (int *)malloc(m*sizeof(int));
memset(C, 0, m*sizeof(int));
int i = 0;
for(; i &lt; n; i++){
C[hash(r_h,A[i])]++;
}
for(i = 0; i &lt; m; i++){
if(C[i] != 0){
//printf("allocating memory\n");
T[i] = (llnode **)malloc((C[i]*C[i])*sizeof(llnode*));
}
}
int j = -1;
int k = -1;
for(i = 0; i &lt; n; i++){
j = hash(r_h,A[i]);
k = hash(r_g,A[i])%(C[j]*C[j]);
//printf("j = %d\n",j);
T[j][k] = add_to_list(T[j][k], A[i]);
}
}

int lookup(int x){
int i = hash(r_h,x);
if(T[i] == NULL) {
printf("Not found %d!\n",x);
return NO;
}
int j = hash(r_g,x)%(C[i]*C[i]);
llnode *L = T[i][j];
while(L != NULL){
if(L-&gt;x == x){
printf("Found %d at location (%d,%d)!\n",x,hash(r_h,x),j);
return YES;
}
L = L-&gt;next;
}
printf("Not found %d!\n",x);
return NO;
}

// we use binary multiplicative hash function
// parameter r_h define h(x), r_g define g(x)
int hash(int r, int x){
return ((r*x)&amp;((1&lt;&lt;w)-1))&gt;&gt;(w-l);
}

// add an element to the head of a linked list
llnode* add_to_list(llnode *head, int a){
llnode *node = (llnode *)malloc(sizeof(llnode));
node-&gt;x = a;
node-&gt;next = head;
head = node;
return head;
}

Vấn đề quan tam còn lại của chúng ta là bảng băm hoàn hảo sẽ cần dùng đến bao nhiêu bộ nhớ. Trong phần cơ sở toán học của băm hoàn hảo (To-do), chúng ta sẽ chứng minh kì vọng bộ nhớ của băm hoàn hảo là $O(n)$ khi $\alpha =1$:

Theorem 4

$ E[\sum_{i=0}^{n-1} C^2[i]] \sim 2n \qquad (14)$

 

Thiết kế hàm băm trong thực tế

Chúng ta đã tìm hiểu 3 phương pháp chính để giải quyết xung đột: xích ngăn cách, địa chỉ mở và băm hoàn hảo. Trong thực tế thiết kế bảng băm,iên ta nên chọn phương pháp nào? Sau đây là một số yếu tố có thể giúp ta chọn được phương án giải quyết xung đột tốt nhất.

Trong các ứng dụng mà chúng ta phải thường xuyên thêm và xóa phần tử khỏi bảng, xích ngăn cách sẽ là một lựa chọn tốt. Băm hoàn hảo, bên cạnh việc khó thực thi, có lẽ không phù hợp với các ứng dụng này. Như mô tả ở trên, khi băm trong pha 2, chúng ta cần phải biết trước số lượng phần tử xung đột trong một ô để cấp phát bộ nhớ. Việc cấp phát này sẽ rất mất thời gian nếu ta liên tục thêm và xóa phần tử khỏi bảng. Định địa chỉ mở cũng khó áp dụng trong trường hợp này vì nếu hệ số tải lên tới xấp xỉ 1 thì tìm kiếm trong định địa chỉ mở cực kì chậm (xem công thức $(7)$ và $(8)$). Với xích ngăn cách, ngay cả khi $\alpha =1$, danh sách dài nhất cũng chỉ khoảng $O(\log n)$.

Ngược lại, trong các ứng dụng mà chúng ta chủ yếu thực hiện tìm kiếm, ít khi phải thêm hay xóa phần tử khỏi bảng (ví dụ ứng dụng từ điển chẳng hạn) thì băm hoàn hảo sẽ là một lựa chọn tốt. Như đã nhắc đến ở trên, băm hoàn hảo có thời gian kì vọng trong trường hợp xấu nhất cũng chỉ là $O(1)$ và bộ nhớ kì vọng là $O(n)$.

Tương tự như băm hoàn hảo, nếu ứng dụng của chúng ta chủ yếu thực hiện tìm kiếm nhưng chúng ta lại có thêm thông tin về tần suất truy nhập khóa, thì ta có thể sử dụng băm địa chỉ mở. Cơ chế của băm địa chỉ mở cho ta thấy các khóa băm càng sớm thì số bước dò trong tìm kiếm càng ngắn. Do đó, ta có thể băm các khóa theo thứ tự giảm dần của tần suất truy nhập. Một điểm chú ý duy nhất với băm địa chỉ mở là không nên để hệ số tải vượt qúa $0.8$.

Trong code dưới đây, mình sử dụng hàm băm nhân nhị phân (họ hàm băm trong ví dụ 2)

Code: hashtable-chaining, hashtable-open-addressing, perfect-hashing.

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.

Facebook Comments

Tags: , , , , , , ,

  1. Trung Đức’s avatar

    Trong phần băm địa chỉ mở, theo em hiểu đoạn "bắt đầu từ vị trí h0(x) cho đến vị trí h0(x)" đúng ra sẽ phải là "bắt đầu từ vị trí h0(x) cho đến vị trí hm-1(x)".

    Reply

    1. Hung Le’s avatar

      Đúng rồi, cám ơn bạn! Mình đã sửa!

      Hùng

      Reply

Reply

Your email address will not be published. Required fields are marked *