Chương 9: Bảng Băm (Hash Table) trong Cấu trúc dữ liệu và Thuật toán

Chuyên khảo toán học phân tích Cấu trúc dữ liệu và thuật toán dsa ch9 hash 1, đánh giá các khía cạnh quan trọng, đề xuất hướng nghiên cứu tiếp theo.

• Đề tài: Cấu Trúc Dữ Liệu Và Thuật Toán DSA Ch9 Hash 1

Mục lục chi tiết

• 9. CHƯƠNG 9: BẢNG BĂM
• 9.1. Khái niệm cơ bản
• 9.2. Các hàm băm
• 9.2.1. Băm trực tiếp
• 9.2.2. Phép chia modulo
• 9.2.3. Rút trích chữ số
• 9.2.4. Bình phương giữa
• 9.2.5. Phương pháp gấp
• 9.2.6. Phương pháp xoay
• 9.2.7. Số giả ngẫu nhiên
• 9.3. Giải quyết xung đột
• 9.3.1. Địa chỉ mở
• 9.3.1.1. Dò tuyến tính
• 9.3.1.2. Dò bậc hai
• 9.3.1.3. Băm kép
• 9.3.1.4. Độ lệch khóa
• 9.3.2. Danh sách liên kết
• 9.3.3. Băm thùng

Tóm tắt

I. Hướng dẫn toàn diện về Cấu trúc dữ liệu và thuật toán Hash

Trong lĩnh vực khoa học máy tính, việc truy xuất dữ liệu nhanh chóng là một yêu cầu cốt lõi. Các phương pháp tìm kiếm truyền thống như tìm kiếm tuần tự (O(n)) hay tìm kiếm nhị phân (O(log n)) đều đòi hỏi nhiều phép so sánh trước khi tìm thấy phần tử mục tiêu. Cấu trúc dữ liệu và thuật toán Hash (còn gọi là Bảng băm hay Hash Table) ra đời như một giải pháp đột phá, hứa hẹn giảm độ phức tạp của thao tác tìm kiếm xuống mức lý tưởng là O(1). Về cơ bản, kỹ thuật hashing ánh xạ một khóa (key) có giá trị lớn vào một địa chỉ (address) nhỏ hơn trong một bảng. Địa chỉ này được gọi là địa chỉ gốc (home address), và vùng bộ nhớ chứa tất cả các địa chỉ gốc được gọi là vùng chính (prime area). Quá trình ánh xạ này được thực hiện bởi một hàm băm (hash function). Mục tiêu của một hàm băm lý tưởng là phân bố các khóa một cách đều đặn trên toàn bộ bảng, giảm thiểu khả năng nhiều khóa khác nhau cùng được ánh xạ vào một địa chỉ. Tuy nhiên, trong thực tế, hiện tượng này vẫn xảy ra và được gọi là xung đột (collision). Việc hiểu rõ các khái niệm nền tảng này là bước đầu tiên để làm chủ một trong những cấu trúc dữ liệu hiệu quả và được ứng dụng rộng rãi nhất hiện nay, từ quản lý cơ sở dữ liệu, bộ nhớ đệm (cache) cho đến các ứng dụng mật mã học.

1.1. Định nghĩa Bảng băm Hash Table và các thuật ngữ cơ bản

Một Bảng băm (Hash Table) là một cấu trúc dữ liệu sử dụng một hàm băm để tính toán một chỉ số, còn được gọi là "mã băm", từ một khóa. Chỉ số này được dùng để xác định vị trí lưu trữ giá trị tương ứng. Theo tài liệu của Lương Thế Nhân và Trần Giang Sơn, các khái niệm cơ bản cần nắm vững bao gồm: Địa chỉ gốc (home address) là địa chỉ được tạo ra bởi hàm băm. Tập hợp các khóa được băm đến cùng một vị trí được gọi là từ đồng nghĩa (synonyms). Khi một vị trí trong bảng đã bị chiếm bởi một dữ liệu đồng nghĩa và có một phần tử mới cần chèn vào, hiện tượng xung đột (collision) xảy ra. Một hệ thống hashing lý tưởng sẽ không có xung đột và không gian địa chỉ được sử dụng một cách nhỏ gọn, hiệu quả. Tuy nhiên, việc đạt được điều này là cực kỳ khó khăn trong thực tế. Do đó, việc thiết kế một hàm băm tốt và một cơ chế giải quyết xung đột hiệu quả là hai yếu tố then chốt quyết định hiệu suất của một Bảng băm. Cấu trúc này cho phép truy cập dữ liệu gần như tức thời, trung bình đạt độ phức tạp O(1).

1.2. So sánh hiệu năng Hashing so với tìm kiếm nhị phân và tuần tự

Hiệu năng là yếu tố quyết định khi lựa chọn cấu trúc dữ liệu. So với tìm kiếm tuần tự, vốn yêu cầu duyệt qua trung bình n/2 phần tử, và tìm kiếm nhị phân, yêu cầu một danh sách đã được sắp xếp và có độ phức tạp O(log n), hashing mang lại một lợi thế vượt trội. Tài liệu gốc đã chỉ ra rằng, với một tập dữ liệu 1.000.000 phần tử, tìm kiếm nhị phân cần khoảng 20 phép so sánh trong trường hợp xấu nhất, trong khi tìm kiếm tuần tự cần đến 1.000.000 phép so sánh. Ngược lại, một Bảng băm được thiết kế tốt có thể tìm thấy phần tử chỉ trong một phép tính duy nhất, đạt được độ phức tạp O(1). Điều này có nghĩa là thời gian tìm kiếm không phụ thuộc vào số lượng phần tử trong tập dữ liệu. Sự khác biệt này đặc biệt quan trọng trong các hệ thống yêu cầu xử lý và truy vấn dữ liệu lớn trong thời gian thực. Mặc dù hashing có chi phí ban đầu cho việc tính toán mã băm và xử lý xung đột, lợi ích về tốc độ truy xuất trong dài hạn là không thể phủ nhận, biến nó thành lựa chọn ưu việt cho nhiều ứng dụng.

II. Cách nhận diện thách thức lớn nhất của bảng băm Xung đột

Mặc dù kỹ thuật băm mang lại hiệu suất vượt trội, nó không phải là không có thách thức. Vấn đề lớn nhất và không thể tránh khỏi trong hashing chính là xung đột (collision). Xung đột xảy ra khi hai hoặc nhiều khóa khác nhau được hàm bâm ánh xạ vào cùng một địa chỉ trong bảng. Ngoại trừ phương pháp băm trực tiếp (direct hashing), hầu hết các hàm băm đều không phải là ánh xạ một-một, dẫn đến việc xung đột là điều tất yếu. Khi xung đột xảy ra, hiệu suất của Bảng băm có thể suy giảm nghiêm trọng, vì hệ thống phải thực hiện thêm các bước để tìm một vị trí trống hoặc quản lý các phần tử bị trùng địa chỉ. Một hệ quả tiêu cực của việc giải quyết xung đột không tốt là hiện tượng phân cụm (clustering), nơi dữ liệu có xu hướng tụ tập lại ở một số khu vực nhất định trong bảng. Điều này làm tăng số lần dò (probes) cần thiết để tìm một phần tử, khiến độ phức tạp tiệm cận O(n) trong trường hợp xấu nhất. Để kiểm soát tình hình, các chuyên gia thường khuyến nghị rằng một Bảng băm không nên đầy quá 75%. Việc hiểu rõ bản chất của xung đột và các hệ quả của nó là yếu tố tiên quyết để lựa chọn và triển khai các phương pháp giải quyết xung đột phù hợp.

2.1. Hiện tượng xung đột Collision và từ đồng nghĩa Synonyms

Hiện tượng xung đột (collision) là trọng tâm của các thách thức trong cấu trúc dữ liệu và thuật toán Hash. Nó xảy ra khi hàm băm h(k) tạo ra cùng một chỉ số cho hai khóa k1 và k2 khác nhau. Các khóa này, k1 và k2, được gọi là từ đồng nghĩa (synonyms). Ví dụ, nếu sử dụng hàm băm là phép chia lấy dư h(k) = k mod 10, cả hai khóa 23 và 133 đều sẽ được băm đến địa chỉ 3, trở thành các từ đồng nghĩa. Khi chèn khóa 23 vào vị trí 3, nếu sau đó chèn tiếp 133, hệ thống sẽ phát hiện vị trí 3 đã bị chiếm, gây ra một xung đột. Tần suất xảy ra xung đột phụ thuộc rất nhiều vào chất lượng của hàm băm và hệ số tải của bảng. Một hàm băm tốt sẽ phân tán các khóa một cách ngẫu nhiên và đồng đều trên toàn bộ không gian địa chỉ, giảm thiểu số lượng từ đồng nghĩa. Việc không xử lý xung đột sẽ dẫn đến mất mát dữ liệu, vì giá trị mới sẽ ghi đè lên giá trị cũ tại cùng một địa chỉ.

2.2. Phân tích các loại phân cụm Clustering trong bảng băm

Khi các xung đột được giải quyết, dữ liệu có xu hướng nhóm lại với nhau, gây ra hiện tượng phân cụm (clustering). Theo tài liệu nghiên cứu, có hai loại phân cụm chính cần quan tâm. Phân cụm sơ cấp (Primary clustering) xảy ra khi dữ liệu bị dồn lại xung quanh một địa chỉ gốc (home address). Điều này thường là hệ quả của các phương pháp giải quyết xung đột đơn giản như dò tuyến tính (linear probing), khi các vị trí trống liên tiếp được tìm kiếm. Phân cụm thứ cấp (Secondary clustering) xảy ra khi dữ liệu tập trung dọc theo một đường dẫn giải quyết xung đột chung. Nghĩa là, nếu hai khóa có cùng địa chỉ gốc, chúng sẽ đi theo cùng một chuỗi các vị trí dò để giải quyết xung đột. Mức độ phân cụm cao làm tăng đáng kể số lần dò trung bình cần thiết để định vị một phần tử, làm suy giảm hiệu suất lý tưởng O(1) của Bảng băm. Mục tiêu chính khi thiết kế thuật toán giải quyết xung đột là phải giảm thiểu cả hai loại phân cụm này để duy trì sự phân bố đồng đều của dữ liệu.

2.3. Tầm quan trọng của hệ số tải Load Factor trong hashing

Hệ số tải (Load Factor), ký hiệu là α, là một chỉ số quan trọng để đo lường mức độ đầy của một Bảng băm. Nó được định nghĩa bằng công thức α = (k/n) * 100, trong đó k là số lượng phần tử đã được lấp đầy và n là kích thước của bảng. Hệ số tải có ảnh hưởng trực tiếp đến xác suất xảy ra xung đột và hiệu suất của các thao tác. Khi α thấp, có nhiều ô trống trong bảng, xác suất xung đột thấp và các thao tác diễn ra nhanh chóng. Ngược lại, khi α tăng cao, bảng trở nên đông đúc, xác suất xung đột tăng vọt, và chi phí cho việc giải quyết xung đột cũng tăng theo. Theo một quy tắc kinh nghiệm được đề cập trong tài liệu, một Bảng băm không nên được phép đầy quá 75% (α ≤ 75). Vượt qua ngưỡng này, hiệu suất sẽ bắt đầu suy giảm đáng kể. Do đó, việc theo dõi và duy trì hệ số tải ở mức hợp lý, có thể bằng cách thay đổi kích thước bảng (rehashing) khi cần, là một chiến lược quan trọng để đảm bảo Bảng băm hoạt động hiệu quả.

III. Top 7 phương pháp tạo Hàm băm Hash Function hiệu quả nhất

Trái tim của mọi cấu trúc dữ liệu và thuật toán Hash là hàm băm (hash function). Chất lượng của hàm băm quyết định trực tiếp đến hiệu suất của toàn bộ hệ thống bằng cách giảm thiểu số lượng xung đột. Một hàm băm tốt cần phải nhanh để tính toán và phân phối các khóa một cách đồng đều trên toàn bộ không gian địa chỉ của bảng. Có nhiều phương pháp để xây dựng một hàm băm, mỗi phương pháp có ưu và nhược điểm riêng, phù hợp với các loại dữ liệu và ứng dụng khác nhau. Các phương pháp phổ biến bao gồm các kỹ thuật dựa trên số học như phép chia lấy dư (Modulo division) hay bình phương đoạn giữa (Mid-square), và các kỹ thuật xử lý chuỗi hoặc số như trích xuất chữ số (Digit extraction), gấp (Folding), và xoay vòng (Rotation). Ngoài ra còn có phương pháp đơn giản nhất là băm trực tiếp (Direct Hashing) và phương pháp phức tạp hơn sử dụng số nguyên tố là giả ngẫu nhiên (Pseudo-random). Việc lựa chọn phương pháp phù hợp đòi hỏi sự phân tích về đặc điểm của tập khóa đầu vào và kích thước của bảng băm để đạt được sự cân bằng tối ưu giữa tốc độ tính toán và khả năng phân tán dữ liệu.

3.1. Kỹ thuật băm số học Phép chia lấy dư và Bình phương đoạn giữa

Phép chia lấy dư (Modulo division) là một trong những hàm băm đơn giản và phổ biến nhất. Địa chỉ được tính bằng công thức: Address = Key mod listSize. Kỹ thuật này hoạt động hiệu quả khi listSize (kích thước bảng) là một số nguyên tố, giúp giảm thiểu số lượng xung đột. Ví dụ, để băm mã nhân viên 121267 vào một bảng có kích thước 307, ta có hash(121267) = 121267 mod 307 = 2. Một kỹ thuật khác là Bình phương đoạn giữa (Mid-square). Phương pháp này lấy bình phương của khóa, sau đó trích xuất các chữ số ở giữa để làm địa chỉ. Ví dụ, với khóa 9452, bình phương của nó là 89340304, ta có thể lấy các chữ số ở giữa là 3403 làm địa chỉ. Phương pháp này có xu hướng tạo ra sự phân bố tốt vì hầu hết các chữ số của khóa đều góp phần vào kết quả. Tuy nhiên, một nhược điểm là bình phương của khóa có thể trở nên quá lớn, đòi hỏi phải xử lý số lớn.

3.2. Kỹ thuật băm xử lý chuỗi Trích xuất Gấp và Xoay vòng

Các kỹ thuật này thường áp dụng cho các khóa dạng chuỗi số. Trích xuất chữ số (Digit extraction) chọn ra một số chữ số từ khóa để tạo thành địa chỉ. Ví dụ, từ khóa 379452, ta có thể chọn các chữ số ở vị trí 1, 3, 4 để tạo địa chỉ 394. Gấp (Folding) chia khóa thành nhiều phần, sau đó cộng các phần này lại với nhau. Ví dụ, khóa 123456789 có thể được chia thành 123, 456, và 789. Tổng của chúng là 1368, và ta có thể lấy 368 làm địa chỉ. Cuối cùng, Xoay vòng (Rotation) được sử dụng để khắc phục tình trạng các khóa chỉ khác nhau ở ký tự cuối, dễ tạo ra từ đồng nghĩa (synonyms). Kỹ thuật này xoay vòng ký tự cuối cùng của khóa lên đầu trước khi băm. Ví dụ, khóa 600101 sẽ trở thành 160010. Theo tài liệu, kỹ thuật này giúp phân tán dữ liệu đều hơn trên không gian địa chỉ, đặc biệt khi kết hợp với các phương pháp khác như Gấp.

3.3. Phương pháp băm trực tiếp Direct Hashing và Giả ngẫu nhiên

Băm trực tiếp (Direct Hashing) là phương pháp đơn giản nhất, trong đó địa chỉ chính là khóa: hash(Key) = Key. Ưu điểm lớn nhất của nó là hoàn toàn không có xung đột. Tuy nhiên, nhược điểm chí mạng là không gian địa chỉ (kích thước lưu trữ) phải lớn bằng không gian khóa. Điều này làm cho nó không thực tế đối với hầu hết các ứng dụng có không gian khóa lớn. Ngược lại, phương pháp Giả ngẫu nhiên (Pseudo-random) sử dụng một công thức để tạo ra một chuỗi địa chỉ có vẻ ngẫu nhiên. Ví dụ, Address = (a * Key + c) mod listSize. Để đạt hiệu quả tối đa, tài liệu gốc khuyến nghị rằng các hằng số a và c nên là các số nguyên tố. Phương pháp này có khả năng phân tán khóa rất tốt và là một lựa chọn mạnh mẽ khi các phương pháp đơn giản hơn không mang lại hiệu quả như mong đợi, giúp giảm thiểu đáng kể tỷ lệ xung đột trong Bảng băm.

IV. Bí quyết giải quyết xung đột trong bảng băm hiệu quả nhất

Khi một hàm băm tạo ra xung đột, cần phải có một chiến lược hiệu quả để xử lý nó. Đây là nhiệm vụ của các phương pháp giải quyết xung đột (collision resolution methods). Nếu không có cơ chế này, dữ liệu mới sẽ ghi đè lên dữ liệu cũ và gây mất mát thông tin. Hiệu suất của Bảng băm không chỉ phụ thuộc vào hàm băm mà còn phụ thuộc rất nhiều vào cách nó xử lý các tình huống va chạm. Mục tiêu là tìm một vị trí mới cho phần tử cần chèn một cách nhanh chóng và giảm thiểu khả năng gây ra phân cụm (clustering) trong tương lai. Có ba họ phương pháp chính để giải quyết xung đột: Địa chỉ mở (Open addressing), Giải pháp danh sách liên kết (Linked list resolution), và Băm theo nhóm (Bucket hashing). Mỗi phương pháp tiếp cận vấn đề theo một cách khác nhau. Địa chỉ mở tìm một ô trống ngay trong bảng chính, trong khi Danh sách liên kết tạo ra một chuỗi các phần tử tại vị trí bị xung đột. Lựa chọn phương pháp phù hợp là một quyết định quan trọng trong việc thiết kế một cấu trúc dữ liệu và thuật toán Hash hiệu quả và ổn định.

4.1. Giới thiệu phương pháp Địa chỉ mở Open Addressing và các biến thể

Địa chỉ mở (Open Addressing) là một nhóm các kỹ thuật giải quyết xung đột bằng cách tìm một vị trí trống khác ngay trong chính Bảng băm khi địa chỉ gốc đã bị chiếm. Thay vì sử dụng các cấu trúc dữ liệu phụ, tất cả các phần tử đều được lưu trữ trong mảng chính. Khi một xung đột xảy ra, thuật toán sẽ "dò" (probe) một chuỗi các vị trí thay thế theo một quy tắc xác định cho đến khi tìm thấy một ô trống. Chuỗi các vị trí này được xác định bởi một hàm băm và thăm dò hp(k, i), trong đó k là khóa và i là số lần dò (bắt đầu từ 0). Các biến thể phổ biến của phương pháp này bao gồm Dò tuyến tính (Linear probing), Dò bậc hai (Quadratic probing), và Băm kép (Double hashing). Ưu điểm của Địa chỉ mở là không cần bộ nhớ phụ, giúp tận dụng tốt bộ nhớ đệm (cache locality). Tuy nhiên, nó nhạy cảm với hệ số tải và có thể bị ảnh hưởng bởi hiện tượng phân cụm.

4.2. Tìm hiểu về Dò tuyến tính Linear Probing và Dò bậc hai

Dò tuyến tính (Linear Probing) là kỹ thuật đơn giản nhất trong họ Địa chỉ mở. Khi một xung đột xảy ra tại địa chỉ h(k), nó sẽ kiểm tra tuần tự các vị trí tiếp theo: h(k)+1, h(k)+2,... (modulo kích thước bảng) cho đến khi tìm thấy một ô trống. Công thức tổng quát là hp(k, i) = (h(k) + i) mod m. Mặc dù dễ thực hiện, nhược điểm lớn của nó là gây ra phân cụm sơ cấp (primary clustering), làm tăng đáng kể thời gian tìm kiếm. Để khắc phục điều này, Dò bậc hai (Quadratic Probing) được đề xuất. Thay vì tăng tuyến tính, khoảng cách dò sẽ tăng theo bình phương của số lần dò: hp(k, i) = (h(k) + i^2) mod m. Phương pháp này giúp phân tán các phần tử tốt hơn và loại bỏ phân cụm sơ cấp. Tuy nhiên, nó có thể dẫn đến phân cụm thứ cấp (secondary clustering), nơi các khóa có cùng địa chỉ gốc sẽ đi theo cùng một chuỗi dò.

4.3. Các phương pháp thay thế Giải pháp danh sách liên kết và Băm theo nhóm

Bên cạnh Địa chỉ mở, có hai phương pháp phổ biến khác. Giải pháp danh sách liên kết (Linked list resolution), còn được gọi là Separate Chaining, xử lý xung đột bằng cách coi mỗi vị trí trong Bảng băm là một con trỏ đến đầu một danh sách liên kết. Tất cả các khóa băm đến cùng một địa chỉ sẽ được lưu trữ trong danh sách liên kết tương ứng. Phương pháp này có ưu điểm là hệ số tải có thể lớn hơn 1 và ít bị ảnh hưởng bởi phân cụm. Tuy nhiên, nó yêu cầu bộ nhớ phụ để lưu các con trỏ và có thể làm giảm hiệu suất cache. Băm theo nhóm (Bucket hashing) là một biến thể, trong đó mỗi vị trí trong bảng không phải là một ô đơn lẻ mà là một "bucket" (một mảng nhỏ) có thể chứa nhiều phần tử. Khi một bucket đầy, một cơ chế xử lý tràn (overflow) sẽ được kích hoạt, có thể là một bucket liên kết. Cả hai phương pháp này đều là những lựa chọn mạnh mẽ để xây dựng các hệ thống hashing linh hoạt và có khả năng mở rộng.

V. Phân tích độ phức tạp thuật toán và cách triển khai bảng băm

Việc hiểu và phân tích độ phức tạp là yếu tố cốt lõi khi đánh giá hiệu quả của bất kỳ cấu trúc dữ liệu và thuật toán nào. Đối với Bảng băm, mục tiêu chính là đạt được độ phức tạp thời gian trung bình O(1) cho các thao tác chèn, xóa và tìm kiếm. Độ phức tạp này là một cải tiến vượt bậc so với các cấu trúc dữ liệu dựa trên so sánh như cây tìm kiếm nhị phân (O(log n)) hay mảng (O(n)). Tuy nhiên, độ phức tạp O(1) chỉ là trường hợp lý tưởng hoặc trung bình. Trong trường hợp xấu nhất, khi tất cả các khóa đều bị xung đột và băm vào cùng một vị trí, hiệu suất của Bảng băm có thể suy giảm xuống O(n). Việc triển khai một Bảng băm đòi hỏi phải viết mã cho hàm băm và cơ chế giải quyết xung đột. Tài liệu gốc cung cấp các thuật toán giả mã cho việc chèn (hashInsert) và tìm kiếm (hashSearch) sử dụng phương pháp Địa chỉ mở, làm cơ sở cho việc triển khai thực tế bằng các ngôn ngữ như C/C++. Phân tích thực nghiệm thông qua các chương trình là cần thiết để đánh giá và so sánh hiệu suất của các hàm băm và phương pháp giải quyết xung đột khác nhau trong các điều kiện tải khác nhau.

5.1. Đánh giá độ phức tạp O 1 của thuật toán tìm kiếm bằng Hashing

Sức mạnh chính của cấu trúc dữ liệu và thuật toán Hash nằm ở độ phức tạp tìm kiếm trung bình là O(1). Điều này có nghĩa là thời gian cần thiết để tìm một phần tử không phụ thuộc vào tổng số phần tử trong bảng. Cơ chế hoạt động của nó không dựa trên việc so sánh các khóa với nhau. Thay vào đó, nó sử dụng một phép tính toán học (thông qua hàm băm) để trực tiếp xác định vị trí của phần tử. Trong trường hợp lý tưởng không có xung đột, chỉ cần một thao tác duy nhất: tính toán mã băm và truy cập vào chỉ số tương ứng trong mảng. Ngay cả khi có xung đột, nếu hệ số tải được giữ ở mức thấp và hàm băm phân phối khóa tốt, số lần dò trung bình để tìm một phần tử vẫn là một hằng số nhỏ. Điều này trái ngược hoàn toàn với tìm kiếm tuần tự (O(n)) và nhị phân (O(log n)), nơi số phép so sánh tăng lên khi kích thước dữ liệu tăng. Khả năng truy cập gần như tức thời này làm cho Bảng băm trở thành một công cụ vô giá trong các ứng dụng đòi hỏi hiệu suất cao.

5.2. Hướng dẫn triển khai thuật toán chèn và tìm kiếm bằng Địa chỉ mở

Tài liệu của Lương Thế Nhân và Trần Giang Sơn cung cấp giả mã chi tiết cho việc triển khai các thuật toán cơ bản trên Bảng băm sử dụng Địa chỉ mở. Thuật toán hashInsert(T, k) để chèn khóa k vào bảng T hoạt động bằng cách lặp qua các số lần dò i từ 0 đến m-1. Ở mỗi bước, nó tính toán địa chỉ j = hp(k, i). Nếu vị trí T[j] trống, nó sẽ chèn k vào đó và trả về chỉ số j. Nếu không, nó sẽ tăng i và thử lại. Nếu vòng lặp kết thúc mà không tìm thấy ô trống, điều đó có nghĩa là bảng đã đầy. Tương tự, thuật toán hashSearch(T, k) cũng lặp và tính toán j = hp(k, i). Nếu T[j] bằng k, nó trả về j. Nếu T[j] trống, điều đó có nghĩa là k không có trong bảng. Nếu T[j] đã bị chiếm bởi một khóa khác, nó sẽ tiếp tục dò. Các giả mã này cung cấp một khuôn mẫu rõ ràng để sinh viên và lập trình viên có thể triển khai cấu trúc dữ liệu và thuật toán Hash bằng các ngôn ngữ lập trình thực tế.

VI. Tóm lược ưu điểm và xu hướng phát triển của kỹ thuật băm

Cấu trúc dữ liệu và thuật toán Hash đã chứng tỏ là một trong những công cụ mạnh mẽ và linh hoạt nhất trong khoa học máy tính. Ưu điểm chính của nó là tốc độ truy cập dữ liệu trung bình cực nhanh, đạt độ phức tạp O(1), vượt trội so với nhiều cấu trúc dữ liệu khác. Điều này làm cho Bảng băm trở thành lựa chọn lý tưởng cho các ứng dụng như xây dựng bộ chỉ mục cơ sở dữ liệu, bộ đệm hệ thống (caching), kiểm tra sự tồn tại của phần tử trong một tập hợp, và thậm chí trong các thuật toán mật mã. Tuy nhiên, hashing cũng có những nhược điểm cần lưu ý, bao gồm hiệu suất suy giảm trong trường hợp xấu nhất (O(n)), sự phức tạp trong việc chọn hàm băm và cơ chế giải quyết xung đột tốt, và chi phí cho việc thay đổi kích thước bảng khi hệ số tải quá cao. Trong tương lai, các nghiên cứu tiếp tục tập trung vào việc phát triển các hàm băm mới có khả năng chống va chạm tốt hơn, đặc biệt là trong lĩnh vực an ninh mạng (cryptographic hash functions), và các thuật toán hashing động có khả năng tự điều chỉnh kích thước một cách hiệu quả để duy trì hiệu suất ổn định khi dữ liệu thay đổi liên tục. Sự phát triển không ngừng này đảm bảo rằng kỹ thuật băm sẽ tiếp tục đóng một vai trò trung tâm trong công nghệ phần mềm.

6.1. Tổng kết những ưu và nhược điểm chính của Bảng băm

Ưu điểm nổi bật nhất của Bảng băm là tốc độ. Các thao tác chèn, xóa và tìm kiếm trung bình chỉ mất thời gian không đổi O(1), làm cho nó cực kỳ hiệu quả cho các tập dữ liệu lớn. Nó cũng tương đối đơn giản để triển khai các phiên bản cơ bản. Tuy nhiên, nhược điểm của nó cũng rất đáng kể. Hiệu suất của Bảng băm phụ thuộc rất lớn vào chất lượng của hàm băm. Một hàm băm tồi có thể gây ra nhiều xung đột, dẫn đến hiệu suất suy giảm xuống O(n). Việc xử lý xung đột cũng thêm một lớp phức tạp vào việc triển khai. Hơn nữa, Bảng băm không duy trì bất kỳ thứ tự nào của các phần tử, vì vậy các thao tác yêu cầu dữ liệu được sắp xếp (như tìm phần tử nhỏ nhất/lớn nhất hoặc duyệt theo thứ tự) sẽ không hiệu quả. Cuối cùng, việc xác định kích thước bảng tối ưu và xử lý việc thay đổi kích thước (rehashing) khi cần thiết có thể tốn kém về mặt tính toán.

6.2. Tương lai của Hashing trong khoa học máy tính và ứng dụng

Kỹ thuật hashing sẽ tiếp tục là một nền tảng không thể thiếu trong khoa học máy tính. Các xu hướng phát triển tập trung vào nhiều lĩnh vực. Trong hệ thống phân tán, các thuật toán như Consistent Hashing giúp giảm thiểu việc di chuyển dữ liệu khi thêm hoặc bớt các nút máy chủ, rất quan trọng cho các hệ thống CSDL NoSQL và mạng phân phối nội dung (CDN). Trong lĩnh vực an ninh, các hàm băm mật mã (như SHA-256) ngày càng trở nên phức tạp hơn để chống lại các cuộc tấn công và đảm bảo tính toàn vẹn dữ liệu. Các cấu trúc dữ liệu dựa trên hashing như Bloom filters và Cuckoo hashing cũng đang được nghiên cứu và áp dụng để giải quyết các vấn đề cụ thể như kiểm tra thành viên tập hợp một cách hiệu quả về không gian. Với sự bùng nổ của dữ liệu lớn (Big Data), vai trò của cấu trúc dữ liệu và thuật toán Hash trong việc xử lý, lập chỉ mục và truy vấn dữ liệu nhanh chóng sẽ càng trở nên quan trọng hơn bao giờ hết.

Nội dung chính

Tổng quan về giáo trình

Tài liệu học tập "Chapter 9: Hash" (Bảng băm) là bài giảng chuyên đề thuộc học phần Cấu trúc dữ liệu và Giải thuật (Data Structures and Algorithms), được biên soạn bởi hai giảng viên Lương Thế Nhân và Trần Giang Sơn thuộc Khoa Khoa học và Kỹ thuật Máy tính, Trường Đại học Bách Khoa – Đại học Quốc gia TP.HCM (Faculty of Computer Science and Engineering, University of Technology, VNU-HCM). Trong chương trình đào tạo kỹ sư và cử nhân ngành Công nghệ Thông tin và Khoa học Máy tính, học phần Cấu trúc dữ liệu và Giải thuật giữ vai trò kiến thức cơ sở ngành bắt buộc, làm nền tảng cho việc thiết kế giải thuật và tối ưu hóa hệ thống phần mềm.

Mục tiêu học tập của chương học được xác định cụ thể thông qua hệ thống chuẩn đầu ra (Learning Outcomes):

• L.1: Trình bày và mô tả các khái niệm cơ bản gồm bảng băm (hashing table), khóa (key), xung đột (collision) và các phương pháp giải quyết xung đột (collision resolution).
• L.2: Phân tích giải thuật và sử dụng ký pháp Big-O để đặc trưng hóa độ phức tạp tính toán của các giải thuật được xây dựng từ các cấu trúc điều khiển: tuần tự (sequence), rẽ nhánh (branching) và lặp (iteration - không xét đệ quy).
• L.3: Mô tả các hàm băm và các phương pháp xử lý xung đột bằng mã giả (pseudocode), đồng thời cung cấp ví dụ minh họa từng bước thực thi thuật toán.
• L.4: Cài đặt cấu trúc dữ liệu bảng băm hoàn chỉnh bằng ngôn ngữ lập trình C/C++.
• L.5: Phân tích độ phức tạp và xây dựng chương trình thực nghiệm (experiment program) để đánh giá hiệu năng của các phương pháp bảng băm.

Nội dung bài giảng được cấu trúc theo phương pháp sư phạm tiếp cận từ bài toán thực tế: phân tích giới hạn của các cấu trúc tìm kiếm tuyến tính và nhị phân, thiết lập nhu cầu về cấu trúc dữ liệu đạt thời gian truy xuất $O(1)$, từ đó đi sâu vào cơ chế toán học của các hàm băm và kỹ thuật giải quyết xung đột bộ nhớ.

---

Nội dung kiến thức cốt lõi

Các chương/chủ đề chính

Nội dung bài giảng Chương 9 được chia thành 3 phần chính với tính logic kế thừa chặt chẽ:

1. Khái niệm cơ bản (Basic Concepts):

   • Đặt vấn đề thông qua phân tích độ phức tạp thời gian: Tìm kiếm tuần tự (Sequential search) có chi phí trung bình và xấu nhất lần lượt là $O(n/2)$ và $O(n)$; Tìm kiếm nhị phân (Binary search) đạt $O(\log n)$. Cả hai phương pháp đều đòi hỏi nhiều phép so sánh khóa trước khi định vị được dữ liệu.
   • Bảng so sánh số phép so sánh tìm kiếm theo kích thước dữ liệu ($N$):
     • $N = 16$: Nhị phân = 4, Tuần tự (TB) = 8, Tuần tự (Xấu nhất) = 16.
     • $N = 256$: Nhị phân = 8, Tuần tự (TB) = 128, Tuần tự (Xấu nhất) = 256.
     • $N = 10,000$: Nhị phân = 14, Tuần tự (TB) = 5,000, Tuần tự (Xấu nhất) = 10,000.
     • $N = 1,000,000$: Nhị phân = 20, Tuần tự (TB) = 500,000, Tuần tự (Xấu nhất) = 1,000,000.
   • Định nghĩa mô hình bảng băm đạt độ phức tạp tìm kiếm lý tưởng $O(1)$ thông qua cơ chế ánh xạ địa chỉ trực tiếp từ khóa.
   • Các thuật ngữ nền tảng:
     • Home address: Địa chỉ được sinh ra bởi hàm băm.
     • Prime area: Vùng nhớ chứa tất cả các địa chỉ gốc.
     • Synonyms: Tập hợp các khóa khác nhau nhưng được băm ra cùng một địa chỉ.
     • Collision: Hiện tượng vị trí lưu trữ dữ liệu cần chèn đã bị chiếm giữ bởi một phần tử đồng nghĩa (synonym).
     • Ideal hashing: Trạng thái băm lý tưởng không xảy ra xung đột vị trí và không gian địa chỉ được tối ưu thu gọn (compact address space).

2. Các phương pháp xây dựng hàm băm (Hash Functions): Bài giảng phân loại và cung cấp giải thuật chi tiết cho 7 phương pháp băm:

   • Direct Hashing: Địa chỉ chính là giá trị của khóa, $hash(Key) = Key$. Phương pháp này không xảy ra xung đột nhưng không gian địa chỉ phải lớn bằng toàn bộ không gian khóa.
   • Modulo Division: Tính địa chỉ theo công thức $Address = Key \pmod{listSize}$. Xung đột giảm thiểu khi $listSize$ là một số nguyên tố (prime number). Ví dụ: Quản lý 1.000.000 nhân viên trong không gian lưu trữ 300 phần tử, chọn kích thước nguyên tố $listSize = 307$, khóa $121267 \to 121267 \pmod{307} = 2$.
   • Digit Extraction: Trích xuất các chữ số ở vị trí xác định trong khóa. Ví dụ: Khóa 6 chữ số trích vị trí 1, 3, 4: $379452 \to 394$, $121267 \to 112$, $045128 \to 051$.
   • Mid-square: Bình phương khóa rồi lấy các chữ số ở giữa, $Address = \text{middle digits of } Key^2$. Ví dụ: $9452^2 = 89340304 \to 3403$. Biến thể thu gọn khóa khi $Key^2$ quá lớn: $379^2 = 143641 \to 364$, $121^2 = 014641 \to 464$, $045^2 = 002025 \to 202$.
   • Folding: Chia khóa thành các phần bằng kích thước địa chỉ:
     • Fold shift: $Key = 123|456|789 \to 123 + 456 + 789 = 1368 \to 368$.
     • Fold boundary: Đảo ngược các phần ở biên: $321 + 456 + 987 = 1764 \to 764$.
   • Rotation: Xoay vòng ký tự áp dụng cho tập khóa chỉ khác nhau ký tự cuối nhằm phân tán đều dữ liệu, thường kết hợp với Fold shift (ví dụ xoay $600101 \to 160010$, gấp lại thành 26 thay vì 62).
   • Pseudo-random: Sử dụng hàm giả ngẫu nhiên đồng dư tuyến tính $Address = ((a \times Key + c) \pmod{listSize})$, với $a$ và $c$ là các số nguyên tố. Ví dụ: $Key = 121267, a = 17, c = 7, listSize = 307 \to ((17 \times 121267 + 7) \pmod{307}) = 2061546 \pmod{307} = 41$.

3. Phương pháp xử lý xung đột (Collision Resolution):

   • Nguyên tắc hệ số tải (Load Factor): $\alpha = (k / n) \times 100$, trong đó $n$ là kích thước danh sách, $k$ là số phần tử đã lưu. Quy tắc thực nghiệm khuyến nghị: Bảng băm không nên để đầy quá 75% ($\alpha \le 75%$).
   • Hiện tượng gom cụm (Clustering):
     • Primary clustering: Dữ liệu bị dồn cục xung quanh địa chỉ gốc (home address).
     • Secondary clustering: Dữ liệu bị gom nhóm dọc theo đường dẫn thăm dò xung đột (collision path).
   • Các nhóm kỹ thuật xử lý xung đột:
     • Địa chỉ mở (Open Addressing): Định vị ô nhớ trống tiếp theo thông qua hàm thăm dò $h_p: U \times {0, 1, \dots, m-1} \to {0, 1, \dots, m-1}$.
       • Linear Probing: Thăm dò tuyến tính $h_p(k, i) = (h(k) + i) \pmod m$. Ưu điểm: Đơn giản, dữ liệu nằm gần địa chỉ gốc (tối ưu khi lưu trữ trên đĩa). Nhược điểm: Tạo ra hiện tượng gom cụm sơ cấp (primary clustering).
       • Quadratic Probing: Thăm dò bậc hai $h_p(k, i) = (h(k) + i^2) \pmod m$. Ưu điểm: Khắc phục gom cụm sơ cấp tốt hơn tuyến tính. Nhược điểm: Tốn chi phí tính toán bình phương và gây ra gom cụm thứ cấp (secondary clustering) do các khóa trùng $h(k)$ sẽ có cùng chuỗi thăm dò.
       • Double Hashing và Key Offset.
     • Giải quyết bằng danh sách liên kết (Linked List Resolution / Chaining).
     • Băm theo thùng chứa (Bucket Hashing).

Kiến thức nền tảng được xây dựng

Tài liệu xây dựng hệ thống lý thuyết chuẩn tắc:

• Nguyên lý ánh xạ toán học: Phân biệt ánh xạ một-một ($1-1$ mapping trong Direct Hashing) và ánh xạ nhiều-một (many-to-one mapping trong Modulo Division và các hàm băm khác), từ đó thiết lập tính tất yếu của các cơ chế giải quyết xung đột.
• Lý thuyết số trong phân bố khóa: Ứng dụng số nguyên tố (prime numbers) trong việc chọn kích thước bảng băm $listSize$ và các hằng số nhân $a, c$ để cực đại hóa chu kỳ phân tán, giảm thiểu chu kỳ lặp dư số.
• Mô hình giải thuật chuẩn tắc:
  • Mã giả thao tác chèn (hashInsert): Sử dụng vòng lặp kiểm tra $T[j] = \text{nil}$ với $j = h_p(k, i)$, trả về địa chỉ chèn hoặc báo lỗi tràn bảng khi $i \ge m$.
  • Mã giả thao tác tìm kiếm (hashSearch): Duyệt qua hàm thăm dò $h_p(k, i)$, dừng khi tìm thấy $T[j] = k$ hoặc gặp ô trống $\text{nil}$.

Kỹ năng phát triển

• Kỹ năng kỹ thuật: Lập trình cài đặt bảng băm, các hàm băm và giải thuật giải quyết xung đột bằng ngôn ngữ C/C++; kiểm soát bộ nhớ động và con trỏ.
• Kỹ năng phân tích: Phân tích độ phức tạp thời gian của giải thuật sử dụng ký pháp Big-O; tính toán hệ số tải $\alpha$; xác định các dạng gom cụm dữ liệu trong bộ nhớ.
• Năng lực thực nghiệm: Thiết kế và triển khai chương trình đo đạc thực nghiệm trên máy tính để so sánh số bước thăm dò thực tế giữa các giải thuật băm và thăm dò khác nhau.

---

Phương pháp giảng dạy và học tập

Phương pháp tiếp cận sư phạm

Giáo trình sử dụng phương pháp đối chiếu định lượng để tạo động lực nhận thức:

1. Đặt sinh viên vào bài toán tìm kiếm trên tập dữ liệu kích thước lớn ($N = 10^6$), so sánh trực quan $20$ phép toán của tìm kiếm nhị phân với hàng trăm nghìn phép so sánh của tìm kiếm tuyến tính.
2. Đặt câu hỏi mở: "Is there a search algorithm whose complexity is O(1)?" để dẫn dắt tự nhiên vào bản chất của giải thuật băm.
3. Chuyển đổi từ mô hình toán học giải tích sang mã giả (pseudocode), sau đó tiến tới hiện thực hóa trên ngôn ngữ lập trình cụ thể (C/C++).

Bài tập và bài toán tình huống

Tài liệu cung cấp các bài toán tính toán cụ thể:

• Bài toán Modulo: Xử lý hệ thống định danh 1.000.000 nhân viên trong mảng 307 phần tử với khóa $121267$.
• Bài toán Mid-square: Thao tác tính toán trên số nguyên 4 chữ số $9452 \to 9452^2 = 89340304$, lấy 4 chữ số giữa để xác định địa chỉ 3403.
• Bài toán Folding: So sánh sự khác biệt giữa phép gấp trượt (fold shift) và phép gấp biên (fold boundary) trên cùng một chuỗi khóa $123|456|789$.
• Bài toán Pseudo-random: Thực hiện chuỗi tính toán $((17 \times 121267 + 7) \pmod{307})$.

Phương pháp đánh giá

• Đánh giá lý thuyết: Khả năng giải thích bản chất toán học của các hàm băm, phân biệt xung đột sơ cấp và thứ cấp.
• Đánh giá giải thuật: Viết mã giả và tính toán chỉ số Big-O cho các hàm thao tác bảng băm.
• Đánh giá thực hành: Đánh giá mã nguồn chương trình C/C++, kiểm thử tính đúng đắn của bảng băm khi hệ số tải vượt ngưỡng khuyến nghị $75%$.

---

Điểm nổi bật và tính cập nhật

• Tính hệ thống và bao quát: Bài giảng tổng hợp đầy đủ 7 phương pháp băm dữ liệu kinh điển cùng 3 nhóm giải pháp xử lý xung đột chính của cấu trúc dữ liệu.
• Phân tích nhược điểm kỹ thuật rõ ràng: Không chỉ nêu khái niệm, tài liệu chỉ rõ hạn chế cơ chế của từng giải thuật:
  • Direct Hashing: Lãng phí không gian bộ nhớ bằng kích thước không gian khóa.
  • Mid-square: Tràn số khi $Key^2$ vượt giới hạn biểu diễn của kiểu dữ liệu nguyên (được khắc phục bằng cách lấy một phần khóa).
  • Linear Probing: Hiện tượng Primary clustering làm suy giảm hiệu năng tìm kiếm cục bộ.
  • Quadratic Probing: Chi phí tính lũy thừa bậc hai và hiện tượng Secondary clustering.
• Gắn liền ứng dụng hệ thống: Tài liệu nhấn mạnh đặc thù kỹ thuật của Linear Probing khi áp dụng cho địa chỉ đĩa từ (disk addresses), nơi việc các phần tử nằm liền kề nhau giúp giảm độ trễ cơ học khi đọc/ghi dữ liệu.

---

Đối tượng sử dụng giáo trình

• Sinh viên đại học: Sinh viên năm thứ 2 hoặc năm thứ 3 chuyên ngành Khoa học Máy tính, Kỹ thuật Máy tính, Công nghệ Thông tin, Hệ thống Thông tin.
• Điều kiện tiên quyết (Prerequisites):
  • Nắm vững kiến thức lập trình cơ bản và nâng cao với C/C++ (đặc biệt là con trỏ, cấp phát bộ nhớ động, mảng và cấu trúc dữ liệu struct).
  • Hiểu biết về toán rời rạc cơ bản: Số học đồng dư (modular arithmetic), số nguyên tố.
  • Đã học các kỹ thuật phân tích độ phức tạp thời gian giải thuật bằng ký pháp Big-O ($O(1), O(\log n), O(n)$).
• Giảng viên: Sử dụng làm đề cương slide bài giảng chuẩn, khung tài liệu hướng dẫn bài tập lớn và bài thực hành phòng lab.

---

Câu hỏi thường gặp

1. Giáo trình này phù hợp với ai?

Tài liệu được thiết kế trực tiếp cho sinh viên đại học khối ngành Công nghệ Thông tin - Kỹ thuật Máy tính đang theo học học phần Cấu trúc dữ liệu và Giải thuật, cũng như kỹ sư phần mềm cần củng cố kiến thức nền tảng về bảng băm và tối ưu hóa thời gian truy xuất dữ liệu.

2. Cần kiến thức nền nào trước khi tiếp cận chương học này?

Người học cần có nền tảng về ngôn ngữ lập trình C hoặc C++, hiểu nguyên lý hoạt động của mảng và danh sách liên kết, có kiến thức về phép toán chia lấy dư (modulo) và phương pháp đánh giá độ phức tạp tính toán bằng ký pháp Big-O.

3. Điểm khác biệt giữa Linear Probing và Quadratic Probing là gì?

Theo tài liệu, Linear Probing tăng bước thăm dò tuyến tính $h_p(k, i) = (h(k) + i) \pmod m$, dễ cài đặt nhưng sinh ra hiện tượng gom cụm sơ cấp (primary clustering). Quadratic Probing tăng bước thăm dò theo bình phương số lần thử $h_p(k, i) = (h(k) + i^2) \pmod m$, giúp phân tán dữ liệu tốt hơn nhưng tốn chi phí tính toán bình phương và sinh ra gom cụm thứ cấp (secondary clustering).

4. Tại sao kích thước bảng băm nên là một số nguyên tố?

Trong phương pháp băm Modulo Division ($Address = Key \pmod{listSize}$), việc chọn $listSize$ là số nguyên tố giúp giảm thiểu hiện tượng trùng lặp số dư đối với các khóa có tính tuần hoàn hoặc chia sẻ ước số chung, qua đó giảm tỷ lệ xảy ra xung đột (fewer collisions).

5. Giới hạn hệ số tải an toàn cho bảng băm là bao nhiêu?

Theo nguyên tắc kinh nghiệm được nêu trong tài liệu (slide 9.30), hệ số tải của bảng băm $\alpha = (k / n) \times 100$ không nên vượt quá $75%$ dung lượng bảng để hạn chế việc gom cụm và tăng số bước thăm dò.

---

Kết luận

Bài giảng "Chapter 9: Hash" của tác giả Lương Thế Nhân và Trần Giang Sơn cung cấp khung kiến thức chuẩn mực và toàn diện về bảng băm trong cấu trúc dữ liệu và giải thuật. Nội dung kết hợp giữa phân tích độ phức tạp toán học, đặc tả giải thuật bằng mã giả và hướng dẫn cài đặt thực nghiệm trên C/C++. Lộ trình học tập khuyến nghị cho người học là: nắm vững định nghĩa về địa chỉ gốc và xung đột $\to$ thực hành tính toán thủ công các hàm băm trên số liệu mẫu $\to$ viết mã giả thao tác chèn/tìm kiếm $\to$ cài đặt mã nguồn C/C++ và chạy chương trình đo lường thực nghiệm số phép thăm dò theo các mức hệ số tải khác nhau.

Trích đoạn nội dung tài liệu

Hash Luong The Nhan, Tran Giang Son Chapter 9 Hash Basic concepts Hash functions Direct Hashing Data Structures and Algorithms Modulo division Digit extraction Mid-square Mid-square Folding Rotation Luong The Nhan, Tran Giang Son Pseudo-random Collision resolution Faculty of Computer Science and Engineering Open addressing University of Technology, VNU-HCM Linked list resolution Bucket hashing 9.1 Hash Outcomes Luong The Nhan, Tran Giang Son • L.1 - Depict the following concepts: hashing table, key, collision, and collision resolution.2 - Describe hashing functions using pseudocode and give examples to show their algorithms.3 - Describe collision resolution methods using Hash functions pseudocode and give examples to show their algorithms. Direct Hashing Modulo division • L.4 - Implement hashing tables using C/C++. Digit extraction Mid-square • L.5 - Analyze the complexity and develop Mid-square Folding experiment (program) to evaluate methods supplied for Rotation Pseudo-random hashing tables. Collision resolution Open addressing • L.2 - Analyze algorithms and use Big-O notation to Linked list resolution characterize the computational complexity of algorithms Bucket hashing composed by using the following control structures: sequence, branching, and iteration (not recursion).2 Hash Contents Luong The Nhan, Tran Giang Son 1 Basic concepts 2 Hash functions Direct Hashing Modulo division Basic concepts Digit extraction Hash functions Mid-square Direct Hashing Modulo division Mid-square Digit extraction Folding Mid-square Mid-square Rotation Folding Rotation Pseudo-random Pseudo-random Collision resolution Open addressing 3 Collision resolution Linked list resolution Open addressing Bucket hashing Linked list resolution Bucket hashing 9.3 Hash Luong The Nhan, Tran Giang Son Basic concepts Basic concepts Hash functions Direct Hashing Modulo division Digit extraction Mid-square Mid-square Folding Rotation Pseudo-random Collision resolution Open addressing Linked list resolution Bucket hashing 9.4 Hash Basic concepts Luong The Nhan, Tran Giang Son • Sequential search: O(n) • Binary search: O(log n) Basic concepts 2 Hash functions Direct Hashing Modulo division Digit extraction Mid-square Mid-square → Requiring several key Folding Rotation Pseudo-random comparisons before the Collision resolution Open addressing Linked list resolution Bucket hashing target is found.5 Hash Basic concepts Luong The Nhan, Tran Giang Son Search complexity: Size Binary Sequential Sequential (Average) (Worst Case) Basic concepts 16 4 8 16 Hash functions Direct Hashing 50 6 25 50 Modulo division Digit extraction 256 8 128 256 Mid-square Mid-square Folding 1,000 10 500 1,000 Rotation Pseudo-random 10,000 14 5,000 10,000 Collision resolution Open addressing 100,000 17 50,000 100,000 Linked list resolution Bucket hashing 1,000,000 20 500,000 1,000,000 9.6 Hash Basic concepts Luong The Nhan, Tran Giang Son Is there a search algorithm Basic concepts Hash functions Direct Hashing whose complexity is O(1)? Modulo division Digit extraction Mid-square Mid-square Folding Rotation Pseudo-random Collision resolution Open addressing Linked list resolution Bucket hashing 9.7 Hash Basic concepts Luong The Nhan, Tran Giang Son Is there a search algorithm Basic concepts Hash functions Direct Hashing whose complexity is O(1)? Modulo division Digit extraction Mid-square Mid-square YES Folding Rotation Pseudo-random Collision resolution Open addressing Linked list resolution Bucket hashing 9.7 Hash Basic concepts Luong The Nhan, Tran Giang Son Basic concepts Hash functions Direct Hashing Modulo division Digit extraction Mid-square Mid-square Folding Rotation Pseudo-random Collision resolution Open addressing Linked list resolution Bucket hashing Hình: Each key has only one address 9.8 Hash Basic concepts Luong The Nhan, Tran Giang Son Basic concepts Hash functions Direct Hashing Modulo division Digit extraction Mid-square Mid-square Folding Rotation Pseudo-random Collision resolution Open addressing Linked list resolution Bucket hashing 9.9 Hash Basic concepts Luong The Nhan, Tran Giang Son • Home address: address produced by a hash function.

• Prime area: memory that contains all the home addresses. Basic concepts Hash functions Direct Hashing Modulo division Digit extraction Mid-square Mid-square Folding Rotation Pseudo-random Collision resolution Open addressing Linked list resolution Bucket hashing 9.10 Hash Basic concepts Luong The Nhan, Tran Giang Son • Home address: address produced by a hash function. • Prime area: memory that contains all the home addresses. Basic concepts Hash functions • Synonyms: a set of keys that hash to the Direct Hashing Modulo division same location.

Digit extraction Mid-square Mid-square • Collision: the location of the data to be Folding Rotation inserted is already occupied by the synonym Pseudo-random Collision resolution data. Open addressing Linked list resolution Bucket hashing 9.10 Hash Basic concepts Luong The Nhan, Tran Giang Son • Home address: address produced by a hash function. • Prime area: memory that contains all the home addresses. Basic concepts Hash functions • Synonyms: a set of keys that hash to the Direct Hashing Modulo division same location.

Digit extraction Mid-square Mid-square • Collision: the location of the data to be Folding Rotation inserted is already occupied by the synonym Pseudo-random Collision resolution data. Open addressing Linked list resolution • Ideal hashing: Bucket hashing • No location collision • Compact address space 9.10 Hash Basic concepts Luong The Nhan, Tran Giang Son Basic concepts Hash functions Direct Hashing Modulo division Digit extraction Mid-square Mid-square Folding Rotation Pseudo-random Collision resolution Open addressing Linked list resolution Bucket hashing 9.11 Hash Basic concepts Luong The Nhan, Tran Giang Son Basic concepts Hash functions Direct Hashing Modulo division Digit extraction Mid-square Mid-square Folding Rotation Pseudo-random Collision resolution Open addressing Linked list resolution Bucket hashing 9.12 Hash Basic concepts Luong The Nhan, Tran Giang Son Basic concepts Hash functions Direct Hashing Modulo division Digit extraction Mid-square Mid-square Folding Rotation Pseudo-random Collision resolution Open addressing Linked list resolution Bucket hashing 9.13 Hash Basic concepts Luong The Nhan, Tran Giang Son Basic concepts Hash functions Direct Hashing Modulo division Digit extraction Mid-square Mid-square Folding Rotation Pseudo-random Collision resolution Open addressing Linked list resolution Bucket hashing 9.14 Hash Luong The Nhan, Tran Giang Son Basic concepts Hash functions Hash functions Direct Hashing Modulo division Digit extraction Mid-square Mid-square Folding Rotation Pseudo-random Collision resolution Open addressing Linked list resolution Bucket hashing 9.15 Hash Hash functions Luong The Nhan, Tran Giang Son • Direct hashing • Modulo division Basic concepts Hash functions • Digit extraction Direct Hashing Modulo division • Mid-square Digit extraction Mid-square Mid-square • Folding Folding Rotation Pseudo-random • Rotation Collision resolution Open addressing • Pseudo-random Linked list resolution Bucket hashing 9.16 Hash Direct Hashing Luong The Nhan, Tran Giang Son Basic concepts The address is the key itself: Hash functions Direct Hashing Modulo division hash(Key) = Key Digit extraction Mid-square Mid-square Folding Rotation Pseudo-random Collision resolution Open addressing Linked list resolution Bucket hashing 9.17 Hash Direct Hashing Luong The Nhan, Tran Giang Son Basic concepts • Advantage: there is no collision. Hash functions Direct Hashing • Disadvantage: the address space (storage Modulo division Digit extraction size) is as large as the key space. Mid-square Mid-square Folding Rotation Pseudo-random Collision resolution Open addressing Linked list resolution Bucket hashing 9.18 Hash Modulo division Luong The Nhan, Tran Giang Son Address = Key mod listSize Basic concepts • Fewer collisions if listSize is a prime Hash functions Direct Hashing number.

Modulo division Digit extraction Mid-square • Example: Mid-square Folding Numbering system to handle 1,000,000 Rotation Pseudo-random employees Collision resolution Open addressing Data space to store up to 300 employees Linked list resolution Bucket hashing hash(121267) = 121267 mod 307 = 2 9.19 Hash Digit extraction Luong The Nhan, Tran Giang Son Address = selected digits f rom Key Basic concepts Hash functions Example: Direct Hashing Modulo division 379452→394 Digit extraction Mid-square 121267→112 Mid-square Folding Rotation 378845→388 Pseudo-random Collision resolution 160252→102 Open addressing Linked list resolution 045128→051 Bucket hashing 9.20 Hash Mid-square Luong The Nhan, Tran Giang Son Basic concepts Hash functions Address = middle digits of Key 2 Direct Hashing Modulo division Digit extraction Example: Mid-square Mid-square Folding 9452 * 9452 = 89340304→3403 Rotation Pseudo-random Collision resolution Open addressing Linked list resolution Bucket hashing 9.21 Hash Mid-square Luong The Nhan, Tran Giang Son • Disadvantage: the size of the Key 2 is too large. Basic concepts Hash functions • Variations: use only a portion of the key. Direct Hashing Modulo division Example: Digit extraction Mid-square Mid-square 379452: 379 * 379 = 143641→364 Folding Rotation 121267: 121 * 121 = 014641→464 Pseudo-random Collision resolution 045128: 045 * 045 = 002025→202 Open addressing Linked list resolution Bucket hashing 9.22 Hash Folding Luong The Nhan, Tran Giang Son The key is divided into parts whose size matches the address size. Example: Basic concepts Key = 123|456|789 Hash functions Direct Hashing Modulo division fold shift Digit extraction Mid-square 123 + 456 + 789 = 1368 Mid-square Folding → 368 Rotation Pseudo-random Collision resolution Open addressing Linked list resolution Bucket hashing 9.23 Hash Folding Luong The Nhan, Tran Giang Son The key is divided into parts whose size matches the address size.

Example: Basic concepts Key = 123|456|789 Hash functions Direct Hashing Modulo division fold shift Digit extraction Mid-square 123 + 456 + 789 = 1368 Mid-square Folding → 368 Rotation Pseudo-random Collision resolution Open addressing fold boundary Linked list resolution Bucket hashing 321 + 456 + 987 = 1764 → 764 9.23 Hash Rotation Luong The Nhan, Tran Giang Son • Hashing keys that are identical except for the last character may create synonyms. • The key is rotated before hashing. Basic concepts Hash functions Direct Hashing original key rotated key Modulo division Digit extraction 600101 160010 Mid-square Mid-square 600102 260010 Folding Rotation Pseudo-random 600103 360010 Collision resolution Open addressing 600104 460010 Linked list resolution Bucket hashing 600105 560010 9.24 Hash Rotation Luong The Nhan, Tran Giang Son • Used in combination with fold shift. original key rotated key 600101 → 62 160010 → 26 Basic concepts Hash functions 600102 → 63 260010 → 36 Direct Hashing Modulo division 600103 → 64 360010 → 46 Digit extraction Mid-square 600104 → 65 460010 → 56 Mid-square Folding Rotation 600105 → 66 560010 → 66 Pseudo-random Collision resolution Open addressing Spreading the data more evenly across the Linked list resolution Bucket hashing address space.25 Hash Pseudo-random Luong The Nhan, Tran Giang Son Basic concepts Hash functions Direct Hashing Modulo division Digit extraction Mid-square Mid-square Folding Rotation Pseudo-random For maximum efficiency, a and c should be Collision resolution Open addressing prime numbers.

Linked list resolution Bucket hashing 9.26 Hash Pseudo-random Luong The Nhan, Tran Giang Son Example: Key = 121267 a = 17 Basic concepts Hash functions c=7 Direct Hashing Modulo division listSize = 307 Digit extraction Mid-square Mid-square Address = ((17*121267 + 7) mod 307 Folding Rotation = (2061539 + 7) mod 307 Pseudo-random Collision resolution = 2061546 mod 307 Open addressing Linked list resolution = 41 Bucket hashing 9.27 Hash Luong The Nhan, Tran Giang Son Basic concepts Collision resolution Hash functions Direct Hashing Modulo division Digit extraction Mid-square Mid-square Folding Rotation Pseudo-random Collision resolution Open addressing Linked list resolution Bucket hashing 9.28 Hash Collision resolution Luong The Nhan, Tran Giang Son • Except for the direct hashing, none of the Basic concepts others are one-to-one mapping Hash functions → Requiring collision resolution methods Direct Hashing Modulo division Digit extraction Mid-square Mid-square • Each collision resolution method can be Folding Rotation used independently with each hash function Pseudo-random Collision resolution Open addressing Linked list resolution Bucket hashing 9.29 Hash Collision resolution Luong The Nhan, Tran Giang Son • A rule of thumb: a hashed list should not be allowed to become more than 75% full. Basic concepts Hash functions Direct Hashing Modulo division Load factor: Digit extraction Mid-square Mid-square α = (k/n) × 100 Folding Rotation n = list size Pseudo-random Collision resolution k = number of filled elements Open addressing Linked list resolution Bucket hashing 9.30 Hash Collision resolution Luong The Nhan, Tran Giang Son • As data are added and collisions are resolved, hashing tends to cause data to group within the list. Basic concepts Hash functions → Clustering: data are unevenly distributed Direct Hashing Modulo division across the list. Digit extraction Mid-square Mid-square Folding Rotation • High degree of clustering increases the Pseudo-random Collision resolution number of probes to locate an element.

Open addressing Linked list resolution → Minimize clustering.31 Hash Collision resolution Luong The Nhan, Tran Giang Son • Primary clustering: data become clustered around a home address.