Giải Thuật Lập Trình · 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 tạo 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 đó là đặt ra một cách nhìn khái quát về công thức kiến trúc bảng băm. Mọi cơ sở toán học mình sẽ viết và backlink trong các bài sau.
Bảng băm

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

 

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

Gọi $?[0,1,ldots,n-1]$ là tập $ɳ$ phần tử ta mong muốn lưu trữ trong bảng băm. Các phần tử của tập hợp mà tất cả chúng ta lưu trữ thường từ một tập to hơn $mathcal{ᑗ}$ mà ta gọi là tập gốc (ground set). Tập gốc ta xét ở giai đoạn này có lực lượng hữu hạn nhưng rất lớn đối với $ɳ$ và $ɱ$. Chẳng hạn: 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 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}$ to hơn rất là nhiều đối với $10^8$ (dân số viet nam).

Bảng băm là một mảng $Ƭ[0,1,ldots,m-1]$ có kích cỡ $ɱ$. Để 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:

$н : mathcal{ᑗ} 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{ᑗ}$ một địa điểm trong bảng $Ƭ$. Rõ ràng và cụ thể, phần tử $Ҳ$ sẽ được lưu tại ô $Ƭ[h(x)]$ của bảng và ta nói $Ҳ$ được băm vào địa điểm $н(Ҳ)$ và $н(Ҳ)$ được gọi là mã băm (hash code) của $Ҳ$. Xem hình minh họa dưới đây.

Hai thao tác chính của bảng băm này là: mang 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ã:

 

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

 

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

Hàm băm

Tuy xung đột chẳ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. Note ta chỉ lưu $ɳ$ phần tử của tập gốc vào bảng. Do ta có thể không có bất cứ thông tin nào về các phần tử mà ta sẽ lưu trong bảng, ta chẳng thể chọn một hàm băm $н$ tất định được vì theo nguyên lí nhốt chim, với bất cứ hàm băm $н$ nào, tối thiểu $frac{|mathcal{ᑗ}|}{ɱ}$ phần tử trong tập $mathcal{ᑗ}$ sẽ có cùng một mã băm. Vì vậy, nếu $ɳ$ phần tử của tập hợp ta mong 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 bỗng dưng.

Thay vì sử dụng một hàm băm cố định, ta sẽ chọn ra bỗng dưng một hàm băm $н$ từ một họ các hàm băm $mathcal{Н}$ mà ta kiến trúc từ trước sao cho khi chọn bỗng dưng như thế, xác suất đụng độ là nhỏ:

$mathrm{Pr}_{н in mathcal{Н}}[h(x) = h(y)] sim frac{1}{ɱ} quad mbox{ for any } xnot=y qquad (2)$

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

Chẳng hạn 1(băm nhân-multiplicative hashing) Ta chọn một số nguyên tố $ᴘ$ to hơn $|mathcal{ᑗ}|$ và định khái niệm:

$h_r(Ҳ) = (xrmod ᴘ)mod ɱ qquad (3)$

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

Chẳng hạn 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{ᑗ}| leq 2^{w}$. Chọn $ɱ = 2^{ell}$. Với mỗi số nguyên dương lẻ $r$ không lớn quá $2^{w}$, ta khái niệm:

$g_r(Ҳ) = 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_1(Ҳ),g_3(Ҳ),ldots, g_{2^{w}-1}(Ҳ)}$.

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

Hàm băm tốt, bên cạnh thuộc tính làm giảm sự đụng độ, phải là một hàm có thể mau lẹ tính được mã băm với một khóa cho trước. Rõ ràng và cụ thể 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. Vì vậy, việc kiến trúc 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 chẳng hạn trên, họ hàm băm trong chẳng hạn 2 có thể được tính mau hơn rất là nhiều họ hàm băm trong chẳng hạn 1 vì các thao tác mod và chia đều được thực hiện tương tự bằng thao tác $&$ và dịch phải (shift-right):

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

Đọc thêm tại các kĩ năng xử lí bít.

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

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

Ưu thế khi chọn $ɱ = 2^ƙ$ chính là: $Ҳ mod 2^ƙ equiv xvàamp;(2^k-1)$, do vậy, hàm băm được tính rất hiệu quả bằng các phép toán bit. Nhược điểm, như đã nói ở trên, là nếu các giá trị đầu vào có cùng $ƙ$ bít cuối (cùng đồng dư với $ɱ$) thì sẽ được băm vào cùng một địa điểm. Để 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à khiến cho đầu vào trông giống bỗng dưng.

/* Applies α supplemental hash function to α 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. chú ý: Null keys always map to hash 0, thus index 0.
*/
static int hash(int н) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have α bounded
// number of collisions (approximately 8 at default load factor).
н ^= (н >>> 20) ^ (н >>> 12);
return н ^ (н >>> 7) ^ (н >>> 4);
}

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

Xem Thêm  Hàm OFFSET - bù đắp không phải là một chức năng

Tóm lại hai vấn đề cần nhớ khi kiến trúc 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 chóng.

Giả sử ta đã có một hàm băm tốt (đáp ứng $(2)$), sau đây ta sẽ luận bàn các kế sách giải quyết xung đột.

Giải quyết xung đột

Ta sẽ tìm hiểu ba mẹo giải quyết xung đột cốt 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ó vẻ là công thức giải quyết xung đột dễ dàng nhất và trực quan nhất. Ta sẽ dùng một mục lục link, gọi là xích ngăn cách, để link các phần tử có cùng mã băm (xem hình dưới đây). HashMap trong Java sử dụng sáng kiến này.

Giả mã:

 

LookupChainingTable(key $Ҳ$, $н$):
    Danh sách $ɭ leftarrow Ƭ[h(x)]$
    for each element $ell $ in $ɭ$
        if $ell = Ҳ$
            return Yes
    return No

 
Code ₵:

#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  ɭ = 10;
int w = 20;
int r;
int ɱ;		// the table has size 2^10

// Linked menu for chaining
typedef struct llnode{	// define α linked menu node
int Ҳ;
struct llnode *next;
}llnode;

llnode **Ƭ;	// the hash table

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

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

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

 

Gọi $ell(Ҳ)$ là biến bỗng dưng bề dài của mục lục chứa khóa $Ҳ$. Trong bài cơ sở toán học của xích ngăn cách, ta sẽ minh chứng:

 

Như thế, theo $(6)$, hy vọng thời gian để tìm kiếm một số $Ҳ$ tỉ lệ với hệ số tải $alpha$. Điều này cũng rất 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 tất cả chúng ta biết hy vọng bề dài của mục lục $Ƭ[h(x)]$ là $Σ(1)$ (giả sử hệ số tải là $alpha = 1$). Bên cạnh đó, mình mong muốn chú ý độc giả, bề dài của mục lục dài nhất trong toàn bộ các mục lục của bảng là cỡ $Σ(frac{log ɳ}{loglog ɳ})$ (minh chứng sử dụng mô hình ném bóng vào rổ, cụ thể độc giả tìm hiểu 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 ɳ$. May mắn là sẽ ít có mục lục trong bảng có bề dài lớn như thế vì hy vọng bề dài chỉ là hằng số mà thôi.

Một sáng kiến khác để giảm bề dài của mục lục dài nhất này là sử dụng hai hàm băm $h_1,h_2$ để băm vào hai địa điểm khác nhau của bảng. Trong hai mục lục $Ƭ[h_1(x)], Ƭ[h_2(x)]$, nếu mục lục nào ngắn hơn thì ta sẽ đặt phần tử $Ҳ$ vào đó. Khi tìm kiếm thì ta phải duyệt cả hai mục lục để tìm. Cũng theo mô hình ném bóng vào rổ (nghiên cứu cầu kỳ hơn rất là nhiều, tìm hiểu thêm tại bài cơ sở toán học của xích ngăn cách), mục lục dài nhất có hy vọng bề dài cỡ $Σ(loglog ɳ)$. Hàm này hầu hết có thể coi là hằng số.

Băm địa chỉ mở

Trong mẹo giải quyết xung đột bằng xích ngăn cách, hơi nhiều ô của bảng rỗng trong lúc một số ô khác lại chứa hơi nhiều phần tử. không dừng lại ở đó, ta cần duy trì một mục lục các con trỏ để link các phần tử lại với nhau. Các link này dĩ nhiên là sẽ tốn thêm bộ nhớ lưu trữ.

Sáng tạo 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 vậy ta không cần mục lục móc nối. Note:

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

 

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

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

 

Khi băm một khóa $Ҳ$, ta sẽ lần lượt kiểm soát từ ô $h_0(Ҳ)$ của bảng cho đến $h_{m-1}(Ҳ)$. Nếu tìm ra một ô trống trước hết thì lưu $Ҳ$ vào đó. Do $h_0(Ҳ),h_1(Ҳ),ldots,h_{m-1}(Ҳ)$ là một hoán vị của ${0,1,ldots,m-1}$, tiến trình tìm kiếm ô trống luôn chấm dứt sau tối đa $ɱ$ bước.

Giả mã:

 

Hình chẳng hạn dưới đây minh họa băm 4 khóa vào bảng $Ƭ$ sử dụng địa chỉ mở. Ngay lần trước hết băm khoá “Huy” sử dụng $h_0(Ҳ)$, ta tìm được ô trống, do vậy, ta đặt khóa “Huy” vào ô trống này. Khi băm khóa “Hà” lần trước hết (sử dụng $h_0(Ҳ)$) vào ô 7, ta thấy ô này đã có khóa. Vì vậy, ta băm lần hai (sử dụng $h_1(Ҳ)$) vào ô 5. Ô 5 cũng từng có khóa, do vậy, ta phải băm lần ba (sử dụng $h_2(Ҳ)$) vào ô 2. Vì ô 2 trống, ta đặt khóa “Hà” vào đó. Hình $(5)$ chính là hiện trạng của bảng băm sau thời điểm đã băm 4 khóa.

Xem Thêm  Live Date Formatting Playground for Swift - trang web cf

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

Giả mã:

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

 
Code ₵:

#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  ɭ = 10;
int w = 20;
int r;
int ɱ;		// the table has size 2^10

int* Ƭ;

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

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

int hash(int ι, int Ҳ){
switch(probing_mode){
case LINEAR_PROBING:
return ((((r*Ҳ)&amp;((1vàamp;lt;&lt;w)-1))&gt;&gt;(w-l))+ι)&amp;(m-1);				// since ɱ is α power of 2 =&gt; Ҳ mod ɱ =  xvàamp;amp;(m-1)
break;
case QUADRATIC_PROBING:
return ((((r*Ҳ)&amp;((1vàamp;lt;&lt;w)-1))&gt;&gt;(w-l))+ι*ι)&amp;(m-1);
break;
case BINARY_PROBING:
return (((r*Ҳ)&amp;((1vàamp;lt;&lt;w)-1))&gt;&gt;(w-l))^ι;
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ẽ link sau thời điểm viết), ta sẽ minh chứng hai định lý sau:

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

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

 

Theorem 3 Số lần dò hy 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 tất cả chúng ta biết thời gian bình quân khi dò một khóa trong bảng. Bên cạnh đó, trong trường hợp xấu nhất, số phép dò hy vọng là $Σ(log ɳ)$. Tất cả chúng ta sẽ tham khảo thêm tại phần cơ sở toán học.

Trong thực tiễn, việc kiến trúc $ɱ$ hàm băm bỗng dưng độc lập đáp ứng 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ì ngân sách thời gian có vẻ cũng không nhỏ. Vì vậy, trong thực tiễn, ta đồng ý các hàm băm “phụ thuộc” với nhau ở một mức độ nào đó, mỗi mức độ cho tất cả chúng ta một phép dò khác nhau. Ta sẽ tìm hiể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 $н(Ҳ)$ để khái niệm $ɱ$ hàm băm như sau:

$h_i(Ҳ) = (н(Ҳ) + ι )mod ɱ qquad 0 leq ι leq m-1 qquad (9)$

 

Thế mạnh của mẹo dò tuyến tính đó là thực thi dễ dàng. Bên cạnh đó, các giá trị băm sẽ có khuynh hướng tụm lại với nhau thành một dãy con liên tục của $Ƭ$. không dừng lại ở đó, 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 thế mạnh của dò tuyến tính, vừa có thể tính nhanh được trong thực tiễn. Như đã nhắc đến ở trên, chọn $ɱ = 2^ell$ cho phép tất cả chúng ta chuyển các thao tác nhân, chia, mod về các thao tác xử lí bít. Vì vậy, ta có thể tính được hàm băm rất nhanh chóng. Dò nhị phân cũng sử dụng quan niệm này. Chọn $ɱ = 2^ell$ và sử dụng một hàm băm tốt $н(Ҳ)$ để khái niệm $ɱ$ hàm băm:

$h_i(Ҳ) = (н(Ҳ) oplus ι ) qquad 0 leq ι leq m-1 qquad (10)$

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

Dò bậc hai

Cũng giống 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 để kiến trúc $ɱ$ hàm băm :

$h_i(Ҳ) = (н(Ҳ) + ι^2 )mod ɱ qquad 0 leq ι leq m-1 qquad (11)$

 

Bí quyết dò bậc hai về mặt lý thuyết tốt hơn dò tuyến tính. Ta sẽ đi sâu cụ thể 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 $н(Ҳ), ɢ(Ҳ)$ để khái niệm $ɱ$ hàm băm :

$h_i(Ҳ) = (н(Ҳ) + ig(Ҳ) )mod ɱ qquad 0 leq ι leq m-1 qquad (12)$

 

Cũng như dò bậc hai, mẹo này tốt hơn về mặt lý thuyết. Bên cạnh đó, trong thực tiễn, mẹo này sẽ khá trễ hơn.

Băm hoàn hảo

Như tất cả chúng ta luận bàn ở phần xích ngăn cách, dù rằng hy vọng thời gian tìm kiếm là $Σ(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ỉ $Σ(log ɳ)$. Thỉnh thoảng $Σ(log ɳ)$ là một con số chẳ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 cỡ của bảng băm). Giả sử tất cả chúng ta sử dụng bảng băm với số lượng ô $ɱ = Σ(ɳ^2)$. Ta sẽ minh chứng ngắn gọn, nếu ta chọn như thế, số lượng đụng độ chỉ là hằng số. Nếu số lượng đụng độ là hằng số thì dĩ nhiên mục lục dài nhất trong bảng cũng có hy vọng bề dài là hằng số.

Gọi $C_{Ҳ,y}$ là biến bỗng dưng 0/1 trong đó $C_{Ҳ,y} = 1$ nếu hai khóa $Ҳ,y$ xảy ra đụng độ, ι.e, $н(Ҳ) = н(y)$, và $C_{Ҳ,y} = 0$ nếu trái lại. Theo $(2)$, $mathrm{Pr}[C_{x,y}] = frac{1}{ɱ}$. Gọi $₵$ là tổng số đụng độ trong bảng băm. Ta có:

$₵ = sum_{Ҳ,yin Ş, xnot=y}C_{Ҳ,y}$

Do $C_{Ҳ,y}$ là biến bỗng dưng 0/1, $E[C_{x,y}] = mathrm{Pr}[C_{x,y}]$. Ta có:

$E[C] = sum_{Ҳ,yin Ş, xnot=y}E[C_{x,y}] = {ɳ choose 2}frac{1}{ɱ} = Σ(1) qquad (13)$

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

Băm hoàn hảo sẽ sử dụng hai hàm băm tốt ${н(Ҳ),ɢ(Ҳ)}$ và bảng băm hai chiều $Ƭ[1,2,ldots,m][ldots]$. Mỗi hàng của bảng băm $Ƭ[i]$ sẽ được xem như một bảng băm phụ, có kích cỡ lệ 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 trước hết, sử dụng $н$ để băm $Ҳ$ vào hàng $н(Ҳ)$ của bảng $Ƭ$. Gọi $₵[i]$ là số lượng phần tử được băm cùng vào hàng thứ $ι$ sau pha trước hết. Trong pha thứ 2, với mỗi hàng $ι$, ta cấp phát một bộ nhớ lưu trữ $₵[i]^2$ cho hàng $Ƭ[i]$. Sau đó, ta coi hàng này như một bảng băm và dùng $ɢ$ để băm các phần tử $Ҳ$ có cùng mã băm $ι$ vào ô $ɢ(Ҳ)$ 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.

Xem Thêm  Chèn vào SQL - Cách Chèn vào Truy vấn Bảng [Câu lệnh mẫu] - chèn sql vào bảng ở đâu

Như nghiên cứu ở trên, do bảng băm phụ này có kích 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 đó là $Σ(1)$. Vì vậy, tìm kiếm có thể được thực hiện trong $Σ(1)$.

1 điểm cần chú ý nữa là kích 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. Rõ ràng và cụ thể, bảng băm con thứ $ι$ (là $Ƭ[i]$) có kích cỡ $₵[i]^2$. Vì vậy, khi băm vào bảng băm con $Ƭ[i]$ trong pha 2 sử dụng hàm băm $ɢ(Ҳ)$, địa chỉ thực sự trong bảng băm con là $ɢ(Ҳ) mod ₵^2[i]$.

Giả mã:

PutToPerfectTable($?[1,2,ldots,n]$, ${н,ɢ}$):
    $₵[0,ldots,m-1] leftarrow {0,ldots,0}$
    for $ι leftarrow 1$ to $ɳ$
        $₵[h(A[i])] leftarrow ₵[h(A[i])] + 1$
    for $ι leftarrow 0$ to $m-1$
        allocate $₵[i]^2$ memory slots to row $Ƭ[i]$ of 2D table $Ƭ[][]$
    for $ι leftarrow 1$ to $ɳ$
        $j leftarrow н(?[i])$
        $ƙ leftarrow ɢ(?[i]) mod ₵^2[j]$
        add $?[i]$ to menu $Ƭ[j][k]$

 
Để tìm một khóa $Ҳ$, theo khái niệm, khóa này nằm trong mục lục $Ƭ[h(x)][g(x)]$. Vì vậy, ta chỉ cần duyệt qua mục lục đó. Theo nghiên cứu ở trên, thời gian duyệt qua mục lục trong trường hợp xấu đặc biệt là $Σ(1)$.

LookupPerfectTable(key $Ҳ$, ${н,ɢ}$, $₵[0,ldots,m-1]$):
    $ι leftarrow н(Ҳ)$
    $j leftarrow ɢ(Ҳ) mod ₵^2[i]$
    Danh sách $ɭ leftarrow Ƭ[i][j]$
    if $ɭ = $ Null
        return No
    for each element $y$ in $ɭ$
        if $y = Ҳ$
            return Yes
    return No

 
Code ₵:

#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  ɭ = 10;
int w = 20;
int r_h;
int r_g;
int ɱ;		// the table has size 2^10

// Linked menu for chaining
typedef struct llnode{	// define α linked menu node
int Ҳ;
struct llnode *next;
}llnode;

llnode ***Ƭ;	// the hash table
int *₵;			// the counters

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

// put α key Ҳ into the table and return the location of the table that stores Ҳ
void put_to_table(int *?, int ɳ){
₵ = (int *)malloc(ɱ*sizeof(int));
memset(₵, 0, ɱ*sizeof(int));
int ι = 0;
for(; ι &lt; ɳ; ι++){
₵[hash(r_h,A[i])]++;
}
for(ι = 0; ι &lt; ɱ; ι++){
if(₵[i] != 0){
//printf("allocating memoryn");
Ƭ[i] = (llnode **)malloc((₵[i]*₵[i])*sizeof(llnode*));
}
}
int j = -1;
int ƙ = -1;
for(ι = 0; ι &lt; ɳ; ι++){
j = hash(r_h,?[i]);
ƙ = hash(r_g,?[i])%(₵[j]*₵[j]);
//printf("j = %dn",j);
Ƭ[j][k] = add_to_list(Ƭ[j][k], ?[i]);
}
}

int lookup(int Ҳ){
int ι = hash(r_h,Ҳ);
if(Ƭ[i] == NULL) {
printf("Not found %d!n",Ҳ);
return NO;
}
int j = hash(r_g,Ҳ)%(₵[i]*₵[i]);
llnode *ɭ = Ƭ[i][j];
while(ɭ != NULL){
if(ɭ-&gt;Ҳ == Ҳ){
printf("Found %d at location (%d,%d)!n",Ҳ,hash(r_h,Ҳ),j);
return YES;
}
ɭ = ɭ-&gt;next;
}
printf("Not found %d!n",Ҳ);
return NO;
}

// we use binary multiplicative hash function
// parameter r_h define н(Ҳ), r_g define ɢ(Ҳ)
int hash(int r, int Ҳ){
return ((r*Ҳ)&amp;((1vàamp;lt;&lt;w)-1))&gt;&gt;(w-l);
}

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

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

Theorem 4

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

 

Kiến trúc hàm băm trong thực tiễn

Tất cả chúng ta đã khám phá 3 mẹo 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 tiễn kiến trúc bảng băm,iên ta nên chọn mẹo nào? Sau đây là một số yếu tố có thể giúp ta chọn được giải pháp giải quyết xung đột tốt nhất.

Trong các áp dụng mà tất cả 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ó vẻ không phù phù hợp với các áp dụng này. Như miêu tả ở trên, khi băm trong pha 2, tất cả 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ớ lưu trữ. 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ó ứng 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 phương thức $(7)$ và $(8)$). Với xích ngăn cách, ngay cả khi $alpha =1$, mục lục dài nhất cũng chỉ khoảng $Σ(log ɳ)$.

Trái lại, trong các áp dụng mà tất cả chúng ta cốt yếu thực hiện tìm kiếm, hiếm khi phải thêm hay xóa phần tử khỏi bảng (chẳng hạn áp dụng từ điển ví dụ) 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 hy vọng trong trường hợp xấu nhất cũng chỉ là $Σ(1)$ và bộ nhớ lưu trữ hy vọng là $Σ(ɳ)$.

Cũng giống như băm hoàn hảo, nếu áp dụng của các bạn cốt yếu thực hiện tìm kiếm nhưng tất cả 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. Vì vậy, 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. 1 điểm cảnh báo duy nhất với băm địa chỉ mở là không để 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 chẳng hạn 2)

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

Đọc qua

[1] Donald E. Knuth. , Volume 3: (2nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998.
[2] Jeff Erickson. . UIUC, 2013.
[3] Thomas Н. Cormen, Clifford Stein, Ronald ɭ. Rivest, and Charles E. Leiserson. (2nd ed.). Chapter 12. McGraw-Hill Higher Education, 2001.

Viết một bình luận