Chương 9: Bảng băm (Hash table)

9.1. Giới thiệu cơ bản về bảng băm

9.1.1. Giới thiệu sơ lược

Vào những năm 50 của thế kỷ 20, thuật ngữ bảng băm bất đầu xuất hiện và phát triển một cách nhanh chóng. Và đến những năm 70, cuốn sách “The Art of Computer Programming” do nhà khoa học nổi tiếng Donald Knuth viết giới thiệu về các khái niệm và thuật toán liên quan đến bảng băm, đã đánh dấu một trong những bước phát triển mạnh mẽ của bảng băm. Từ khi xuất hiện đến nay, bảng băm đã trở thành một công cụ quan trọng và phổ biến trong việc lưu trữ và tìm kiếm dữ liệu nhanh chóng và hiệu quả.

Bảng băm là một Cấu trúc dữ liệu được sử dụng dưới dạng một từ điển: mỗi phần tử trong bảng băm là một cặp khóa - giá trị (key - value). Bảng băm thông qua một cơ chế đặc biệt để biến đổi khóa thành một giá trị chỉ số và sử dụng chỉ số đó để truy xuất giá trị tương ứng, được lưu trữ tại chỉ số đó.

9.1.2. Các khái niệm

• Key (khóa): Là giá trị duy nhất được sử dụng để xác định vị trí lưu trữ và tìm kiếm trong bảng băm.

• Hash table (bảng băm): thường có dạng mạng có kích thước cố định, trong đó mỗi phần tử của mảng là một bucket (ngăn) hoặc một danh sách liên kết đơn, ký hiệu HT, có N vị trí được đánh chỉ mục từ 0 đến $N-1$, $N$ là kích thước của bảng băm.

• Hash function (hàm băm): Là một hàm được sử dụng để chuyển đổi khóa thành một chỉ số trong mảng lưu trữ của bảng băm. Hàm băm cần phải có tính chất phân tán tốt để tránh xung đột khóa và giúp phân tán dữ liệu đều trong bảng.

• Collision (đụng độ): Xảy ra khi hai khóa được ánh xạ đến cùng một vị trí trong mảng. Điều này có thể xảy ra do hàm băm không phân tán tốt hoặc do kích thước mảng không đủ lớn để chứa tất cả các khóa.

• Collision resolution (giải quyết đụng độ): Là quá trình giải quyết xung đột khi hai khóa ánh xạ đến cùng một vị trí. Có nhiều phương pháp để giải quyết xung đột, bao gồm sử dụng danh sách liên kết (chaining), băm kép (double hashing) và băm mở (open addressing).

• Load factor (Hệ số tải): Là tỷ lệ giữa số lượng phần tử hiện có trong bảng băm và kích thước của mảng. Tải cao có thể dẫn đến hiện tượng xung đột tăng và làm giảm hiệu suất của bảng băm.

• Dynamic hashing (Băm động): Là kỹ thuật điều chỉnh kích thước của mảng dựa trên tải của bảng băm, để đảm bảo rằng không gian lưu trữ được sử dụng hiệu quả và tránh tình trạng quá tải hoặc lãng phí.

9.2. Hàm băm

9.2.1. Định nghĩa

Hàm băm là một ánh xạ biến đổi từ các khóa thành các địa chỉ trong bảng.

Để bảng băm đạt được mức hiệu quả cao nhất thì hàm băm phải tốt. Trong điều kiện lý tưởng, một hàm băm tốt là một hàm băm có thể phân bố đều trên miền giá trị của địa chỉ, tuy nhiên điều này là rất khó xảy ra.

Hàm băm hoàn hảo: Với một tập hợp các phần tử, hàm băm ánh xạ từng khóa vào 1 địa chỉ duy nhất trong bảng được gọi là hàm băm hoàn hảo.

Một số cách chọn hàm băm tốt:

• Hàm băm phải đơn giản để tính toán
• Số lần xử lý va chạm phải ít hơn khi đặt bản ghi vào bảng băm. Tốt nhất là không nên để đụng độ (Đụng độ và cách giải quyết đụng độ xem ở mục 9.3.)

9.2.2. Một số hàm băm thường sử dụng

Phương pháp chia

Giả sử gọi $N$ là các phần tử được chứa trong bộ nhớ ($N$ là kích thước bảng băm), hàm băm sẽ biến đổi các khóa (thường là số nguyên hoặc là các chuỗi ký tự ngắn) thành các đoạn số nguyên trong khoảng từ $0$ đến $N-1$. Khi đó, ta có công thức hàm băm là:

$H(k) = k \% N$ (với $k$ là khóa, $H(k)$ là hàm lấy dư của $k$ chia cho $N$)

Ví dụ 1: $N = 11$, $k = 197$. $H(197) = 197 \% 11 = 10$

Ví dụ 2: Xét bảng băm có $N = 12$ và hai khóa 44, 68.

$H(44) = 44 \% 12 = 8$ và $H(68) = 68 \% 12 = 8$.

Ở Ví dụ 2, ta thấy 2 khóa cùng 1 địa chỉ, điều này xảy ra va chạm giữa các khóa với nhau, cách xử lí trường hợp này sẽ được trình bày sau ở phần 9.3.

Phương pháp nhân

Trong phương pháp nhân, ta nhân khóa $k$ với một hằng số $A (0 < A < 1)$. Sau đó, nhân phần thập phân của số thực kết quả với $N$

$H(k) = [(k * A) \% 1] * N$

Trong đó phép $\mod 1$ là lấy phần thập phân của số thực

Ví dụ 3: $N = 11$, $k = 197$, $A = 0.167$. $H(197) = [(197 * 0.167) \mod 1] * 11 = 0.899 * 11 = 9.889$ $\Rightarrow$ Chèn giá trị vào vị trí số 9 của bảng băm.

Hàm băm mật mã (Hàm băm tổng quát)

Các hàm băm mật mã được thiết kế để bảo mật và được sử dụng trong mật mã. Ví dụ bao gồm MD5, SHA-1 và SHA-256. Các hàm băm này nổi bật với tính bảo mật cao và khả năng chống va chạm trong bảng băm tốt

$H(k) = [(ak + b) \% p] \% N$

Trong đó:

$p$: Số nguyên tố lớn hơn tất cả các khóa trong bảng băm

$a$, $b$: Hai hằng số bất kì

$N$: kích thước bằng băm

9.3. Sự đụng độ

9.3.1. Khái niệm đụng độ

Đụng độ là hiện tượng các khóa khác nhau nhưng khi băm cho ra cùng địa chỉ như nhau.

Khi $key1 \ne key2$ mà $f(key1) = f(key2)$, chúng ta nói nút có khóa $key1$ đụng độ với nút có khóa $key2$.

Thực tế, người ta giải quyết đụng độ theo 2 phương pháp:

• Phương pháp nối kết

• Phương pháp băm lại

9.3.2. Phương pháp nối kết

9.3.2.1. Nối kết trực tiếp

Hướng giải quyết: Các nút bị băm cùng địa chỉ (đụng độ/ xung đột) sẽ được gom thành một danh sách liên kết

Ví dụ 4: Cho bảng băm có $N = 5$ là số vị trí trống chứa khóa như hình bên dưới. Hàm băm: $H(k) = (k \% M)$, xử lý đụng độ bằng phương pháp nối kết trực tiếp. Lần lượt thêm các khóa 25, 7, 2, 10, 40, 12, 27, 9, 28, 3 vào bảng. Ta sẽ được kết quả như sau:

	Key
0	25 $\rightarrow$ 10 $\rightarrow$ 40
1
2	7 $\rightarrow$ 2 $\rightarrow$ 12 $\rightarrow$ 27
3	28 $\rightarrow$ 3
4	9

9.3.2.2. Nối kết hợp nhất

Bảng băm trong trường hợp này được cài đặt bằng danh sách liên kết dùng mảng, có $N$ nút. Các nút bị xung đột địa chỉ được kết nối với nhau qua một danh sách liên kết.

Mỗi nút của bảng băm là một mẫu tin có 2 trường:

• Trường key: chứa các khóa của nút
• Trường next: con trỏ trỏ đến nút kết tiếp nếu có xung đột.

Chi tiết cách thực hiện

Khi khởi tạo bảng băm thì tất cả trường key được gán bằng NULL, tất cả trường next được gán bằng -1.

Khi thêm một nút có khóa key vào bảng băm, hàm băm $H(key)$ sẽ xác định địa chỉ $i$ trong khoảng từ 0 đến $M-1$, nếu chưa bị xung đột thì thêm nút mới vào địa chỉ này. Nếu xung đột thì nút mới được cấp phát là nút trống phía cuối mảng. Và địa chỉ của nút trống cuối mảng này sẽ được lưu vào trường next của nút vừa bị xung đột.

Khi tìm một nút có khóa $key$ trong bảng băm, hàm băm $H(key)$ sẽ xác định địa chỉ $i$ trong khoảng từ $0$ đến $N-1$, tìm nút khóa key trong danh sách liên kết xuất phát từ địa chỉ $i$.

Ví dụ 5: Cho bảng băm như hình bên dưới

	Key	Next
0	NULL	-1
1	NULL	-1
2	NULL	-1
3	NULL	-1
4	NULL	-1
5	NULL	-1

Thực hiện các yêu cầu sau:

• Lần lượt thêm các khóa 12, 18, 24, 1, 49 vào bảng.
• Sử dụng hàm băm: $H(k) = (k \% N)$
• Giải quyết đụng độ bằng phương pháp nối kết hợp nhất.

Ta có Bảng băm cuối cùng sau khi thực hiện các yêu cầu

	Key	Next
0	12	5
1	1	3
2	NULL	-1
3	49	-1
4	24	-1
5	18	4

9.3.3. Phương pháp băm lại

9.3.2.1. Dò tuyến tính

Bảng băm trong trường hợp này được cài đặt bằng một danh sách kề có $M$ nút, mỗi nút của bảng băm là một mẫu tin có trường $key$ để chứa khóa. Khi khởi tạo bảng băm thì tất cả trường $key$ được gán bằng NULL.

Khi thêm nút có khóa $key$ vào bảng, hàm băm $H(key)$ sẽ xác định địa chỉ $i$ trong khoảng từ $0$ đến $N – 1$.

Nếu chưa bị đụng độ thì thêm nút mới vào địa chỉ này.

Nếu xảy ra đụng độ thì sẽ tiến hành duyệt tuyến tính, hàm băm lại lần 1 – $f1$ sẽ xét địa chỉ kế tiếp, nếu lại bị xung đột thì hàm băm lại lần 2 – $f2$ sẽ xét địa chỉ kế tiếp, quá trình duyệt cứ tiếp tục cho đến khi nào tìm được địa chỉ trống và thêm nút vào địa chỉ này. Khi tìm một nút có khoá $key$ vào bảng băm, hàm băm $f(key)$ sẽ xác định địa chỉ $i$ trong khoảng từ $0$ đến $N-1$, tìm nút khoá $key$ trong khối đặt chứa các nút xuất phát từ địa chỉ $i$.

Hàm băm lại của phương pháp dò tuyến tính là truy xuất địa chỉ kế tiếp. Hàm băm lại lần $i$ được biểu diễn bằng công thức sau:

$h(k , i) = [ H(k) + i ] \% M$

Ví dụ 6: Cho bảng băm ở trạng thái vừa khởi tạo có $M = 5$ nút, lần lượt thêm các khóa 27, 32, 46, 14 vào bảng.

Hàm băm: $H(key) = (key \% M)$

Xử lý đụng độ bằng phương pháp dò tuyến tính.

	Key
0	NULL
1	NULL
2	NULL
3	NULL
4	NULL

Thêm khóa 27:

	Key
0	NULL
1	NULL
2	27
3	NULL
4	NULL

Thêm khóa 32:

• $H(32) = (32 \% 5) = 2$ $\Rightarrow$ Xảy ra đụng độ. Ta tiến hành băm lại lần 1:
• $h_1(32 , 1) = (32 + 1) \% 5 = 3$ $\Rightarrow$ Vị trí trống, điền khóa 32 vào vị trí này.

	Key
0	NULL
1	NULL
2	27
3	32
4	NULL

Thêm khóa 46:

• $H(46) = (46 \% 5) = 1$ $\Rightarrow$ Vị trí trống, điền khóa 46 vào vị trí này.

	Key
0	NULL
1	46
2	27
3	32
4	NULL

Thêm khóa 51

• $H(51) = (51 \% 5) = 1$ $\Rightarrow$ Xảy ra đụng độ, ta tiến hành băm lại lần 1:
• $h_1(51) = (51+1) \% 5 = 2$ $\Rightarrow$ Xảy ra đụng độ, ta tiến hành băm lại lần 2:
• $h_2(51) = (51+2) \% 5 = 3$ $\Rightarrow$ Xảy ra đụng độ, ta tiến hành băm lại lần 3.
• $h_3(51) = (51+3) \% 5 = 4$ $\Rightarrow$ Vị trí trống. Ta điền khóa 51 vào vị trí này.

	Key
0	NULL
1	46
2	27
3	32
4	51

Thêm khóa 14

• $H(14)=14 \% 5$ = 4 $\Rightarrow$ Xảy ra đụng độ, ta tiến hành băm lại lần 1:
• $h_1(14) = (14+1) \% 5 = 0$ $\Rightarrow$ Vị trí trống, ta tiến hành điền khóa vào vị trí này.

	Key
0	14
1	46
2	27
3	32
4	51

9.3.2.2. Dò bậc hai

Hạn chế của bảng băm dùng phương pháp dò tuyến tính bị hạn chế do rải các nút không đều, nếu liên tục xảy ra đụng độ thì các khóa sẽ được phân bố nối tiếp nhau theo thứ tự từ trên xuống. Dẫn đến việc truy xuất chậm.

Phương pháp dò bậc hai sẽ rải các nút đều hơn.

Bảng băm sử dụng phương pháp dò bậc hai có cấu trúc tương tự với bảng băm sử dụng phương pháp dò tuyến tính, tuy nhiên hàm băm lại khi xảy ra đụng độ lần thứ $i$ sẽ là:

$h(k , i) = [ H(k) + i^2 ] \% M$

Khi sử dụng phương pháp băm bậc 2 nên chọn số địa chỉ $M$ là số nguyên tố

Sẽ có trường hợp bảng băm còn trống vị trí để chứa khóa, nhưng khi băm sẽ không tìm ra được vị trí để điền khóa vào bảng băm. Vì phương pháp dò bậc hai khi áp dụng với một số số nguyên $M$ sẽ không duyệt được hết các vị trí của bảng băm.

Ví dụ 7: Cho bảng băm ở trạng thái vừa khởi tạo có $M = 11$ nút, lần lượt thêm các khóa 31, 19, 2, 13, 25, 24, 21, 9 vào bảng. Hàm băm: $H(key) = (key \% M)$.

Xử lý đụng độ bằng phương pháp dò bậc hai. Hàm băm lại khi xảy ra đụng độ lần thứ $i$ sẽ là: $h(k , i) = [ H(k) + i^2 ] \% M$ với $h(key)$ là hàm băm chính của bảng băm.

	Key
0	NULL
1	NULL
2	NULL
3	NULL
4	NULL
5	NULL
6	NULL
7	NULL
8	NULL
9	NULL
10	NULL

Thêm khóa 31:

• $H(31) = 31 \% 11 = 9$ $\Rightarrow$ Vị trí trống, ta tiến hành điền khóa 31 vào vị trí này.

	Key
0	NULL
1	NULL
2	NULL
3	NULL
4	NULL
5	NULL
6	NULL
7	NULL
8	NULL
9	31
10	NULL

Thêm khóa 19:

• $H(19) = 19 \% 11 = 8$ $\Rightarrow$ Vị trí trống, ta tiến hành điền khóa 19 vào vị trí này.

	Key
0	NULL
1	NULL
2	NULL
3	NULL
4	NULL
5	NULL
6	NULL
7	NULL
8	19
9	31
10	NULL

Thêm khóa 2:

• $H(2) = 2 \% 11 = 2$ $\Rightarrow$ Vị trí trống, ta tiến hành điền khóa 2 vào vị trí này.

	Key
0	NULL
1	NULL
2	2
3	NULL
4	NULL
5	NULL
6	NULL
7	NULL
8	19
9	31
10	NULL

Thêm khóa 13:

• $H(13) = 13 \% 11 = 2$ $\Rightarrow$ Xảy ra đụng độ, ta tiến hành băm lại lần 1:
• $h_1(13) = (H(13) + 12) \% 11 = 3$ $\Rightarrow$ Vị trí trống, ta tiến hành điền khóa 13 vào vị trí này.

	Key
0	NULL
1	NULL
2	2
3	13
4	NULL
5	NULL
6	NULL
7	NULL
8	19
9	31
10	NULL

Thêm khóa 25:

• $H(25) = 25 \% 11 = 3$ $\Rightarrow$ Xảy ra đụng độ, ta tiến hành băm lại lần 1:
• $h_1(25) = (H(25) + 12) \% 11 = 4$ $\Rightarrow$ Vị trí trống, ta tiến hành điền khóa 25 vào vị trí này.

	Key
0	NULL
1	NULL
2	2
3	13
4	25
5	NULL
6	NULL
7	NULL
8	19
9	31
10	NULL

Thêm khóa 24:

• $H(24) = 24 \% 11 = 2$ $\Rightarrow$ Xảy ra đụng độ, ta tiến hành băm lại lần 1:
• $h_1(24) = (H(24) + 12) \% 11 = 3$ $\Rightarrow$ Xảy ra đụng độ, ta tiến hành băm lại lần 2:
• $h_2(24) = (H(24) + 22) \% 11 = 6$ $\Rightarrow$ Vị trí trống, ta tiến hành điền khóa 24 vào vị trí này.

	Key
0	NULL
1	NULL
2	2
3	13
4	25
5	NULL
6	24
7	NULL
8	19
9	31
10	NULL

Thêm khóa 21:

• $H(21) = 21 \% 11 = 10$ => Vị trí trống, ta tiến hành điền khóa 21 vào vị trí này.

	Key
0	NULL
1	NULL
2	2
3	13
4	25
5	NULL
6	24
7	NULL
8	19
9	31
10	21

Thêm khóa 9:

• $H(9) = 9 \% 11 = 9$ $\Rightarrow$ Xảy ra đụng độ, ta tiến hành băm lại lần 1:
• $h_1(9) = (H(9) + 12) \% 11 = 10$ $\Rightarrow$ Xảy ra đụng độ, ta tiến hành băm lại lần 2:
• $h_2(9) = (H(9) + 22) \% 11 = 2$ $\Rightarrow$ Xảy ra đụng độ, ta tiến hành băm lại lần 3:
• $h_3(9) = (H(9) + 32) \% 11 = 7$ $\Rightarrow$ Vị trí trống, ta tiến hành điền khóa 9 vào vị trí này.

	Key
0	NULL
1	NULL
2	2
3	13
4	25
5	NULL
6	24
7	9
8	19
9	31
10	21

9.3.2.3. Dò kép

Bảng băm này dùng hai hàm băm khác nhau với mục đích rải đều các phần tử trên bảng băm. Chúng ta có thể sử dụng hai hàm băm bất kỳ, ví dụ chọn hai hàm băm như sau:

$H1(key) = key \% M$ (1)

$H2(key) = (M-2) – key \% (M-2)$ (2)

• Băm lần thứ $i$: $h(key, i) = (H1(key) + i * H2(key)) \% M$

• Bảng băm trong trường hợp này được cài đặt bằng danh sách kề có $M$ phần tử tương tự như ở phương pháp dò tuyến tính và dò bậc hai.

• Khi khởi tạo bảng băm, tất cả trường key được gán bằng NULL

• Khi thêm phần tử có khóa key vào bảng băm, đặt $i = h_1(key)$ và $j = h_2(key)$ ($i$ và $j$ trong khoảng từ 0 đến $M – 1$):

  • Nếu chưa bị xung đột thì thêm phần tử mới tại địa chỉ $i$ này.
  • Nếu bị xung đột thì hàm băm lại lần 1, $h_1$ sẽ xét địa chỉ mới $i+j$, nếu lại bị xung đột thì hàm băm lại lần 2, $h_2$ sẽ xét địa chỉ $i+2j$,… quá trình cứ thế cho đến khi tìm được địa chỉ trống và thêm phần tử và địa chỉ này.

9.3.4. Bài tập tham khảo

---

(Đề thi CTDLGT 2018 – 2019)

Bài toán: Truy vấn mật khẩu từ cơ sở dữ liệu tài khoản

Cho một cơ sở dữ liệu lưu trữ tài khoản và mật khẩu của các người dùng.
Hãy viết chương trình nhập vào tài khoản và mật khẩu của từng user và xuất ra mật khẩu theo yêu cầu (sử dụng bảng băm).

Input:

• Dòng đầu tiên là m (số lượng người dùng trong cơ sở dữ liệu) và n (số lượng truy vấn tài khoản).
• m dòng tiếp theo: mỗi dòng gồm hai chuỗi Tai_Khoan và Mat_Khau.
• n dòng cuối: mỗi dòng là một chuỗi tên tài khoản muốn truy vấn.

Output:

• Gồm n dòng: Mỗi dòng là mật khẩu tương ứng với tên tài khoản đã nhập.
• Nếu tài khoản không tồn tại, in ra dòng:

  Tai khoan khong ton tai!

Lưu ý:

• Nếu có 2 dòng trong cơ sở dữ liệu chứa cùng một tài khoản, chỉ lấy mật khẩu của dòng sau.
• Dữ liệu nên được lưu trữ và truy vấn bằng bảng băm (hash table).

Hàm băm tham khảo:

$$H(key) = key \mod 13$$

Hàm băm lại sử dụng phương pháp dò tuyến tính:

$$h(key, i) = (H(key) + i) \mod 13$$

	Khởi tạo	Thêm 10	Thêm 26	Thêm 52	Thêm 76	Thêm 13	Thêm 8	Thêm 3	Thêm 33	Thêm 60	Thêm 42
0	NULL		26	26	26	26	26	26	26	26	26
1	NULL			52	52	52	52	52	52	52	52
2	NULL					13	13	13	13	13	13
3	NULL							3	3	3	3
4	NULL										42
5	NULL
6	NULL
7	NULL								33	33	33
8	NULL						8	8	8	8	8
9	NULL									60	60
10	NULL	10	10	10	10	10	10	10	10	10	10
11	NULL				76	76	76	76	76	76	76
12	NULL

Chi tiết từng bước thêm khóa vào bảng băm (Linear Probing)

Thêm khóa 10

• $H(10) = 10 \mod 13 = 10$. Vị trí 10 trống $\Rightarrow$ Thêm khóa 10 vào vị trí này

Thêm khóa 26

• $H(26) = 26 \mod 13 = 0$. Vị trí 0 trống $\Rightarrow$ Thêm khóa 26 vào vị trí này

Thêm khóa 52

• $H(52) = 52 \mod 13 = 10$. Vị trí 10 đã có khóa $\Rightarrow$ Xảy ra đụng độ, tiến hành băm lại:

• Với $i = 1$: $h(52, 1) = (H(52) + 1) \mod 13 = (10 + 1) \mod 13 = 11$. Vị trí 11 trống $\Rightarrow$ Thêm khóa 52 vào vị trí 11

Thêm khóa 76

• $H(76) = 76 \mod 13 = 11$. Vị trí 11 đã có khóa $\Rightarrow$ Xảy ra đụng độ, tiến hành băm lại:

  • Với $i = 1$: $h(76, 1) = (H(76) + 1) \mod 13 = (11 + 1) \mod 13 = 12$. Vị trí 12 trống $\Rightarrow$ Thêm khóa 76 vào vị trí 12

Thêm khóa 13

• $H(13) = 13 \mod 13 = 0$. Vị trí 0 đã có khóa $\Rightarrow$ Xảy ra đụng độ, tiến hành băm lại:

  • Với $i = 1$: $h(13, 1) = (H(13) + 1) \mod 13 = (0 + 1) \mod 13 = 1$. Vị trí 1 trống $\Rightarrow$ Thêm khóa 13 vào vị trí 1

Thêm khóa 8

• $H(8) = 8 \mod 13 = 8$. Vị trí 8 trống $\Rightarrow$ Thêm khóa 8 vào vị trí này

Thêm khóa 3

• $H(3) = 3 \mod 13 = 3$. Vị trí 3 trống $\Rightarrow$ Thêm khóa 3 vào vị trí này

Thêm khóa 33

• $H(33) = 33 \mod 13 = 7$. Vị trí 7 trống $\Rightarrow$ Thêm khóa 33 vào vị trí này

Thêm khóa 60

• $H(60) = 60 \mod 13 = 8$. Vị trí 8 đã có khóa $\Rightarrow$ Xảy ra đụng độ, tiến hành băm lại:

• Với $i = 1$: $h(60, 1) = (H(60) + 1) \mod 13 = (8 + 1) \mod 13 = 9$. Vị trí 9 trống $\Rightarrow$ Thêm khóa 60 vào vị trí 9

Thêm khóa 42

• $H(42) = 42 \mod 13 = 3$. Vị trí 3 đã có khóa $\Rightarrow$ Xảy ra đụng độ, tiến hành băm lại:

• Với $i = 1$: $h(42, 1) = (H(42) + 1) \mod 13 = (3 + 1) \mod 13 = 4$. Vị trí 4 trống $\Rightarrow$ Thêm khóa 42 vào vị trí 4

Đoạn code tham khảo

#include <iostream>
using namespace std;

#define MAXTABLESIZE 10000
const int TableSize = 10000;

struct NODE {
    string username;
    string password;
};
typedef NODE* HASHTABLE[MAXTABLESIZE];

unsigned int HF(const string& key) {
    unsigned int hashVal = 0;

    for (char ch : key)
        hashVal = 37 * hashVal + ch;

    return hashVal % TableSize;
}

int HF_LinearProbing(string key, int i) {
    return (HF(key) + i) % TableSize;
}

int isFull(HASHTABLE H, int CurrentSize) {
    if (CurrentSize == TableSize - 1)
        return 1;
    return 0;
}

void CreateHash(HASHTABLE& H, int& CurrentSize, int n) {
    CurrentSize = 0;
    for (int i = 0; i < TableSize; i++)
        H[i] = NULL;
    for (int i = 0; i < n; i++) {
        if (isFull(H, CurrentSize) == 1)
            return;
        NODE* p = new NODE;
        cin >> p->username;
        cin >> p->password;
        int b = HF(p->username);
        int j = 0;
        while (b < TableSize && H[b] != NULL && H[b]->username != p->username)
            b = HF_LinearProbing(p->username, ++j);
        if (H[b] == NULL) {
            H[b] = p;
            CurrentSize++;
            continue;
        }
        H[b]->password = p->password;
    }
}

int Search(HASHTABLE H, int CurrentSize, string key) {
    int b = HF(key);
    int i = 0;
    if (H[b] == NULL)
        return -1;
    while (H[b]->username != key && H[b] != NULL)
        b = HF_LinearProbing(key, ++i);
    if (H[b]->username == key)
        return b;
}

void PrintPass(HASHTABLE H, int CurrentSize, int m) {
    int a[TableSize];
    int n = 0;
    for (int i = 0; i < m; i++) {
        string str;
        cin >> str;
        int b = Search(H, CurrentSize, str);
        if (b != -1)
            a[n++] = b;
        else
            a[n++] = -1;
    }
    for (int i = 0; i < n; i++) {
        if (a[i] == -1)
            cout << "Khong ton tai tai khoan." << endl;
        else
            cout << H[a[i]]->password << endl;
    }
}

int main() {
    HASHTABLE H;
    int CurrentSize;
    int n, m;
    cin >> n >> m;
    CreateHash(H, CurrentSize, n);
    PrintPass(H, CurrentSize, m);
    return 0;
}

Ngoài ra, các bạn có thể tìm hiểu thêm về một thuật toán ứng dụng Hàm băm - Rolling Hash tại đây

9.4. Ứng dụng

9.4.1. Nhận xét, đánh giá

Điểm mạnh

• Tốc độ truy cập nhanh: Trong trường hợp lý tưởng (ít hoặc không có đụng độ), các thao tác tìm kiếm, chèn và xóa đều có độ phức tạp trung bình là $O(1)$.
• Truy cập dữ liệu trực tiếp thông qua khóa: Không cần duyệt qua toàn bộ dữ liệu, chỉ cần tính toán hàm băm.
• Hiệu quả khi xử lý dữ liệu lớn: Với khả năng truy xuất nhanh, bảng băm rất phù hợp cho các bài toán cần tra cứu nhanh trong tập dữ liệu lớn.
• Dễ triển khai cho các bài toán ánh xạ giữa khóa và giá trị (ví dụ: lưu trữ thông tin người dùng, đếm tần suất xuất hiện...).

Hạn chế

• Đụng độ khóa (collision): Khi nhiều khóa có cùng giá trị băm, cần xử lý bằng các kỹ thuật như dò tuyến tính, băm kép hoặc danh sách liên kết, gây giảm hiệu năng.
• Tốn bộ nhớ: Để giảm đụng độ, thường cần cấp phát một bảng có kích thước lớn hơn nhiều so với số lượng phần tử thực tế.
• Không duy trì thứ tự: Dữ liệu trong bảng băm không có thứ tự cụ thể như trong danh sách hay cây nhị phân.
• Phụ thuộc vào hàm băm: Hiệu quả của bảng băm phụ thuộc lớn vào chất lượng của hàm băm. Hàm băm kém sẽ gây ra nhiều đụng độ, làm giảm hiệu suất.

9.4.2. Ứng dụng

• Tìm kiếm và tra cứu: Bảng băm được sử dụng trong các hệ quản trị cơ sở dữ liệu để tìm kiếm nhanh dữ liệu, giúp tìm kiếm nhanh các phần tử trong tập dữ liệu lớn. Ví dụ, trong các công cụ tìm kiếm web, bảng băm được sử dụng để lưu trữ và tìm kiếm các từ khóa.

• Xác thực và bảo mật: Mật khẩu người dùng thường được lưu trữ dưới dạng giá trị băm trong cơ sở dữ liệu để đảm bảo tính an toàn và riêng tư.

• Bảo mật thông tin: Bảng băm được sử dụng trong các thuật toán mã hóa để tạo chữ ký số và băm các thông tin nhạy cảm. Ví dụ, thuật toán SHA-256 sử dụng bảng băm để tạo giá trị băm 256-bit cho dữ liệu đầu vào. Các bạn có thể đọc thêm về vụ rò rỉ thông tin bảo mật của LinkedIn tại đây

• Tối ưu hóa và tìm kiếm trong đồ thị: Các thuật toán như Dijkstra và A* sử dụng bảng băm để lưu trữ và truy xuất các đỉnh và cạnh trong đồ thị.

---

Bài viết tham khảo

• https://wiki.vnoi.info/algo/data-structures/hash-table
• https://viblo.asia/p/tim-hieu-ve-hash-table-RnB5p0gY5PG
• https://www.geeksforgeeks.org/hash-table-data-structure/