Chương 9: Bảng băm (Hash) - Cấu trúc dữ liệu & Thuật toán [CO2003 - ĐHBK]

Tài liệu nghiên cứu Data structure and algorithms cấu trúc dữ liệu và thuật toán ch09 hash, tổng hợp lý thuyết và thực hành, cung cấp kiến thức chuyên sâu về toán học.

• Trường học: Trường Đại Học Công Nghệ Thông Tin
• Chuyên ngành: Cấu Trúc Dữ Liệu Và Thuật Toán
• Đề tài: Hash
• Loại tài liệu: Bài Giảng
• Năm xuất bản: 2023
• Địa điểm: Thành Phố Hồ Chí Minh

Mục lục chi tiết

• CHUẨN ĐẦU RA
• 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 lấy dư
• 9.2.3. Trích xuất 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. Phương pháp giả ngẫu nhiên
• 9.3. Giải quyết đụng độ
• 9.3.1. Địa chỉ mở
• 9.3.1.1. Thăm dò tuyến tính
• 9.3.1.2. Thăm dò bậc hai
• 9.3.1.3. Băm kép
• 9.3.1.4. Khoảng bù khóa
• 9.3.2. Giải quyết bằng danh sách liên kết
• 9.3.3. Băm theo ngăn (Bucket hashing)

Tóm tắt

I. Khám phá cấu trúc dữ liệu Hash Giải pháp tìm kiếm O 1

Trong lĩnh vực khoa học máy tính, hiệu quả truy xuất dữ liệu là yếu tố then chốt. Các phương pháp truyền thống như tìm kiếm tuần tự (Sequential search) có độ phức tạp O(n), trong khi tìm kiếm nhị phân (Binary search) tối ưu hơn với O(log n), nhưng vẫn yêu cầu nhiều phép so sánh. Câu hỏi đặt ra là liệu có tồn tại một thuật toán tìm kiếm với độ phức tạp O(1) không? Câu trả lời là có, và đó chính là sức mạnh của cấu trúc dữ liệu và thuật toán hash. Kỹ thuật hashing, hay băm, là một phương pháp mang tính cách mạng, cho phép ánh xạ trực tiếp một khóa (key) vào một địa chỉ cụ thể trong một mảng, được gọi là bảng băm (hash table). Thay vì duyệt qua các phần tử, hashing tính toán vị trí của dữ liệu dựa trên chính khóa của nó. Điều này giúp giảm đáng kể thời gian tìm kiếm, chèn và xóa, đưa chúng về thời gian gần như không đổi trong trường hợp lý tưởng. Về cơ bản, một hàm băm (hash function) sẽ nhận một khóa đầu vào và tạo ra một chỉ số (index) trong bảng băm. Vị trí này được gọi là địa chỉ nhà (home address), là nơi dữ liệu sẽ được lưu trữ. Mục tiêu của một hàm băm lý tưởng là phân phối các khóa một cách đồng đều trên khắp bảng băm, giảm thiểu khả năng nhiều khóa cùng trỏ về một địa chỉ.

1.1. So sánh hiệu năng Tìm kiếm tuần tự nhị phân và hash

Hiệu năng của một thuật toán tìm kiếm được đo bằng độ phức tạp tính toán (computational complexity). Với tìm kiếm tuần tự, trong trường hợp xấu nhất, thuật toán phải duyệt qua toàn bộ n phần tử của danh sách, dẫn đến độ phức tạp là O(n). Tìm kiếm nhị phân cải thiện đáng kể bằng cách liên tục chia đôi không gian tìm kiếm trên một danh sách đã được sắp xếp, đạt độ phức tạp O(log₂ n). Tuy nhiên, cả hai phương pháp này đều phụ thuộc vào số lượng phần tử. Ngược lại, hashing hướng tới mục tiêu tham vọng hơn: độ phức tạp O(1). Trong một kịch bản lý tưởng, hàm băm sẽ tạo ra một địa chỉ duy nhất cho mỗi khóa. Khi cần tìm kiếm, chèn, hoặc xóa một phần tử, hệ thống chỉ cần áp dụng hàm băm lên khóa để tính toán trực tiếp địa chỉ của nó và thực hiện thao tác ngay lập tức. Theo tài liệu của Dr. Duc Dung Nguyen, sự khác biệt này trở nên cực kỳ rõ rệt khi kích thước dữ liệu lớn. Ví dụ, với 1,000,000 bản ghi, tìm kiếm nhị phân cần khoảng 20 phép so sánh, trong khi tìm kiếm tuần tự có thể cần đến 500,000 phép so sánh trung bình. Hashing, về lý thuyết, chỉ cần một phép tính duy nhất.

1.2. Các khái niệm cơ bản Bảng băm khóa và địa chỉ nhà

Để hiểu rõ về cấu trúc dữ liệu và thuật toán hash, cần nắm vững các thuật ngữ cốt lõi. Bảng băm (hash table) là một cấu trúc dữ liệu dạng mảng, nơi mỗi phần tử được truy cập thông qua một chỉ số. Khóa (key) là một giá trị duy nhất (hoặc gần như duy nhất) được liên kết với một bản ghi dữ liệu, dùng để xác định và truy xuất bản ghi đó. Hàm băm (hash function) là một thuật toán toán học nhận đầu vào là một khóa và trả về một số nguyên, chính là chỉ số trong bảng băm. Địa chỉ được tạo ra bởi hàm băm được gọi là địa chỉ nhà (home address). Toàn bộ vùng nhớ chứa các địa chỉ nhà này được gọi là prime area. Mục tiêu của một hệ thống hashing lý tưởng là đạt được hai điều: không có xung đột (collision) và không gian địa chỉ phải nhỏ gọn. Tuy nhiên, trong thực tế, việc tạo ra một hàm băm hoàn hảo là bất khả thi, dẫn đến một thách thức lớn nhất của hashing: giải quyết xung đột.

II. Thách thức lớn nhất của hashing Vấn đề xung đột collision

Mặc dù hashing mang lại hiệu suất vượt trội, nó không tránh khỏi một vấn đề cố hữu: xung đột (collision). Xung đột xảy ra khi hàm băm tạo ra cùng một địa chỉ nhà (home address) cho hai hoặc nhiều khóa khác nhau. Theo tài liệu gốc, 'Collision: the location of the data to be inserted is already occupied by the synonym data'. Khi một vị trí trong bảng băm đã bị chiếm dụng, phần tử mới không thể được chèn vào đó một cách trực tiếp, đòi hỏi phải có một cơ chế xử lý. Tập hợp các khóa được băm vào cùng một địa chỉ được gọi là từ đồng nghĩa (synonyms). 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 (load factor) của bảng băm – tỷ lệ giữa số lượng phần tử được lưu trữ và kích thước 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 trên toàn bộ không gian địa chỉ, làm giảm xác suất xảy ra xung đột. Tuy nhiên, ngay cả với hàm băm tốt nhất, xung đột vẫn là điều khó tránh khỏi khi số lượng khóa tăng lên. Do đó, việc thiết kế một chiến lược giải quyết xung đột (collision resolution) hiệu quả là một phần không thể thiếu và mang tính quyết định đến hiệu năng thực tế của cấu trúc dữ liệu và thuật toán hash.

2.1. Định nghĩa xung đột và từ đồng nghĩa synonyms là gì

Trong ngữ cảnh của bảng băm, xung đột là hiện tượng khi một hàm băm h(k) ánh xạ hai khóa khác nhau k1 và k2 (với k1 ≠ k2) vào cùng một chỉ số trong bảng, tức là h(k1) = h(k2). Vị trí này đã bị chiếm bởi một phần tử khác, khiến cho việc chèn phần tử mới trở nên phức tạp. Tài liệu gốc định nghĩa từ đồng nghĩa (synonyms) là 'một tập hợp các khóa được băm vào cùng một vị trí'. Ví dụ, nếu hàm băm là h(k) = k mod 10, cả hai khóa 27 và 37 đều sẽ được ánh xạ vào địa chỉ 7. Do đó, 27 và 37 là các từ đồng nghĩa. Khi chèn 27 vào vị trí 7, nếu sau đó cần chèn 37, một xung đột sẽ xảy ra. Hiện tượng này làm giảm hiệu quả của bảng băm, vì nó phá vỡ giả định truy cập O(1). Thay vì truy cập trực tiếp, 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 xử lý danh sách các phần tử tại vị trí đó. Tóm lại, quản lý xung đột và từ đồng nghĩa là nhiệm vụ trung tâm để duy trì hiệu suất cao của cấu trúc dữ liệu hash.

2.2. Tại sao việc lựa chọn hàm băm ảnh hưởng đến xung đột

Chất lượng của hàm băm là yếu tố quyết định trực tiếp đến tần suất xảy ra xung đột. Một hàm băm lý tưởng phải có khả năng phân tán các khóa một cách ngẫu nhiên và đồng đều trên toàn bộ dải địa chỉ của bảng băm. Nếu hàm băm tạo ra các mẫu có thể dự đoán được hoặc có xu hướng tập trung các khóa vào một vài khu vực nhất định, nó sẽ gây ra hiện tượng phân cụm (clustering) và làm tăng đột biến số lần xung đột. Ví dụ, một hàm băm chỉ dựa vào các chữ số đầu của một mã số nhân viên có thể gây ra xung đột nghiêm trọng nếu các mã số này thường bắt đầu bằng cùng một chuỗi số. Ngược lại, một hàm băm tốt như phép chia lấy dư (Modulo division) với một số nguyên tố làm kích thước bảng (listSize) sẽ giúp phân tán các khóa tốt hơn, vì các số nguyên tố có đặc tính chia ít hơn. Việc lựa chọn sai hàm băm có thể làm cho hiệu suất của bảng băm suy giảm nghiêm trọng, thậm chí tiệm cận với hiệu suất của một danh sách liên kết, tức là O(n) trong trường hợp xấu nhất.

III. Các hàm băm phổ biến trong cấu trúc dữ liệu và thuật toán

Để ánh xạ hiệu quả từ không gian khóa sang không gian địa chỉ, nhiều hàm băm (hash function) đã được phát triển, mỗi loại có ưu và nhược điểm riêng. Việc lựa chọn hàm băm phù hợp phụ thuộc vào đặc điểm của dữ liệu đầu vào và yêu cầu về hiệu suất. Một trong những phương pháp đơn giản nhất là băm trực tiếp (Direct Hashing), nơi địa chỉ chính là khóa: hash(Key) = Key. Phương pháp này không gây ra xung đột nhưng lại đòi hỏi không gian lưu trữ khổng lồ, bằng với không gian của khóa. Phổ biến hơn là phép chia lấy dư (Modulo Division), Address = Key mod listSize, đặc biệt hiệu quả khi listSize là một số nguyên tố. Các kỹ thuật khác tập trung vào việc xử lý khóa để tạo ra địa chỉ. Trích xuất số (Digit Extraction) chọn một vài chữ số từ khóa để tạo thành địa chỉ. Bình phương giữa (Mid-square) lấy bình phương của khóa và sử dụng các chữ số ở giữa kết quả. Phương pháp gấp (Folding) chia khóa thành nhiều phần, sau đó cộng chúng lại với nhau. Mỗi phương pháp này đều nhằm mục đích tạo ra một sự phân bố ngẫu nhiên và đồng đều hơn, giảm thiểu khả năng các khóa tương tự nhau tạo ra cùng một địa chỉ.

3.1. Phân tích phương pháp băm trực tiếp và phép chia lấy dư

Băm trực tiếp (Direct Hashing) là phương pháp lý tưởng nhất về mặt tốc độ và không xung đột. Tuy nhiên, nó chỉ thực tế khi không gian khóa nhỏ và dày đặc. Ví dụ, nếu quản lý 1000 sinh viên với mã số từ 1 đến 1000, có thể dùng một mảng 1001 phần tử và sử dụng mã số làm chỉ số. Nhược điểm chí mạng của nó là lãng phí bộ nhớ khi không gian khóa lớn và thưa thớt. Ngược lại, phép chia lấy dư (Modulo Division) là một trong những hàm băm được sử dụng rộng rãi nhất do tính đơn giản và hiệu quả. Công thức Address = Key mod listSize đảm bảo địa chỉ tạo ra luôn nằm trong phạm vi của bảng băm (từ 0 đến listSize - 1). Hiệu quả của phương pháp này phụ thuộc rất nhiều vào việc chọn listSize. Theo kinh nghiệm thực tiễn và khuyến nghị trong tài liệu, chọn listSize là một số nguyên tố sẽ giúp giảm thiểu xung đột vì nó giúp phân tán các khóa có quy luật (ví dụ, các khóa đều là số chẵn) một cách tốt hơn.

3.2. Kỹ thuật trích xuất số bình phương và phương pháp gấp

Các kỹ thuật này thường được áp dụng khi khóa không phải là số nguyên hoặc có các phần không mang nhiều thông tin. Trích xuất số (Digit Extraction) hữu ích khi một số phần của khóa có tính ngẫu nhiên hơn các phần khác. Ví dụ, trong một mã sản phẩm dài, các chữ số ở giữa có thể thay đổi nhiều hơn các chữ số đầu (chỉ loại sản phẩm). Bình phương giữa (Mid-square) hoạt động bằng cách bình phương khóa, sau đó lấy các chữ số ở giữa của kết quả. Ý tưởng là hầu hết các chữ số của khóa đều góp phần tạo ra các chữ số ở giữa, giúp tăng tính ngẫu nhiên. Tuy nhiên, phương pháp này có thể tạo ra kết quả lớn, cần xử lý cẩn thận. Phương pháp gấp (Folding) đặc biệt hiệu quả với các khóa dài. Khóa được chia thành nhiều đoạn có độ dài bằng với độ dài địa chỉ, sau đó các đoạn này được cộng lại với nhau (có thể đảo ngược một số đoạn – 'fold boundary') để tạo ra địa chỉ cuối cùng. Kỹ thuật này đảm bảo mọi phần của khóa đều ảnh hưởng đến kết quả băm.

3.3. Tối ưu hóa phân tán với phương pháp xoay và giả ngẫu nhiên

Để giải quyết vấn đề các khóa tương tự nhau (ví dụ: 600101, 600102) tạo ra các từ đồng nghĩa (synonyms), phương pháp xoay (Rotation) được sử dụng. Trước khi băm, khóa được xoay vòng. Ví dụ, 600101 có thể trở thành 160010. Thao tác này thay đổi đáng kể giá trị của khóa và khi kết hợp với các hàm băm khác như phương pháp gấp, nó giúp phân tán các khóa tương tự ra xa nhau trong bảng băm. 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 số có vẻ ngẫu nhiên từ khóa. Một công thức phổ biến là Address = (a * Key + c) mod listSize. Để đạt hiệu quả tối đa, các hằng số a và c nên là các số nguyên tố. Phương pháp này thường cho kết quả phân tán rất tốt và là một lựa chọn mạnh mẽ khi các phương pháp khác không mang lại hiệu quả như mong đợi, giúp giảm thiểu đáng kể tỷ lệ xung đột.

IV. Hướng dẫn các phương pháp giải quyết xung đột trong bảng băm

Khi một xung đột xảy ra, một chiến lược giải quyết xung đột (collision resolution) phải được áp dụng để tìm một vị trí mới cho phần tử cần chèn. Ngoại trừ băm trực tiếp, tất cả các hàm băm khác đều cần đến cơ chế này. Tài liệu gốc giới thiệu ba nhóm phương pháp chính: địa chỉ mở (Open addressing), giải quyết bằng danh sách liên kết (Linked list resolution), và băm theo khối (Bucket hashing). Địa chỉ mở là kỹ thuật phổ biến nhất, hoạt động dựa trên nguyên tắc khi địa chỉ nhà đã bị chiếm, thuật toán sẽ 'dò' (probe) các vị trí khác trong chính bảng băm theo một quy tắc nhất định cho đến khi tìm thấy một ô trống. Các biến thể của địa chỉ mở bao gồm dò tuyến tính (Linear Probing), dò bậc hai (Quadratic Probing) và băm kép (Double Hashing). Mỗi phương pháp có cách tiếp cận khác nhau để xác định chuỗi dò, nhằm mục đích tránh phân cụm và đảm bảo tất cả các ô trong bảng đều có thể được truy cập. Việc lựa chọn phương pháp giải quyết xung đột ảnh hưởng trực tiếp đến hiệu suất tìm kiếm và chèn khi bảng bắt đầu đầy.

4.1. Địa chỉ mở Dò tuyến tính và dò bậc hai hiệu quả ra sao

Dò tuyến tính (Linear Probing) là phương pháp đơn giản nhất trong địa chỉ mở. Khi xung đột tại địa chỉ h(k), nó sẽ kiểm tra tuần tự các vị trí tiếp theo: (h(k) + 1) mod m, (h(k) + 2) mod m,... cho đến khi tìm thấy ô trống. Ưu điểm của nó là dễ cài đặt và có xu hướng giữ dữ liệu gần địa chỉ nhà, tốt cho bộ nhớ cache. Tuy nhiên, nhược điểm lớn của nó là gây ra phân cụm sơ cấp (primary clustering), nơi các khối ô bị chiếm dụng liên tiếp có xu hướng hợp nhất lại thành các cụm lớn hơn, làm tăng đáng kể thời gian tìm kiếm. Dò bậc hai (Quadratic Probing) cải thiện vấn đề này bằng cách dò theo một bước nhảy bậc hai: (h(k) + i²) mod m. Điều này giúp các phần tử 'nhảy' qua các cụm đã hình thành, phân tán dữ liệu tốt hơn và giảm thiểu 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ỉ nhà sẽ đi theo cùng một chuỗi dò.

4.2. Kỹ thuật băm kép Double Hashing để giảm thiểu phân cụm

Băm kép (Double Hashing) được xem là một trong những phương pháp địa chỉ mở hiệu quả nhất để giảm thiểu hiện tượng phân cụm. Kỹ thuật này sử dụng hai hàm băm khác nhau: h1(k) để xác định địa chỉ nhà ban đầu, và h2(k) để xác định khoảng cách bước nhảy cho chuỗi dò. Công thức dò là hp(k, i) = (h1(k) + i * h2(k)) mod m. Vì bước nhảy phụ thuộc vào chính khóa k (thông qua h2(k)), các khóa khác nhau dù có cùng địa chỉ nhà (h1(k1) = h1(k2)) rất có thể sẽ có chuỗi dò khác nhau. Điều này giúp phân tán các từ đồng nghĩa một cách hiệu quả trên toàn bảng băm, gần như loại bỏ cả phân cụm sơ cấp và thứ cấp. Kết quả là một hệ thống hashing có hiệu suất ổn định và gần với lý thuyết hơn, ngay cả khi bảng đầy lên đáng kể. Nhược điểm của nó là chi phí tính toán cao hơn một chút do phải thực hiện hai phép băm.

4.3. So sánh ưu và nhược điểm của từng kỹ thuật địa chỉ mở

Việc lựa chọn kỹ thuật địa chỉ mở phụ thuộc vào sự cân bằng giữa tính đơn giản, hiệu suất và yêu cầu bộ nhớ. Dò tuyến tính đơn giản nhất để triển khai nhưng lại dễ bị phân cụm sơ cấp, làm giảm hiệu suất khi hệ số tải tăng. Dò bậc hai là một sự cải tiến tốt, loại bỏ phân cụm sơ cấp nhưng lại tạo ra phân cụm thứ cấp và có thể không duyệt qua tất cả các ô trong bảng nếu kích thước bảng không được chọn cẩn thận. Băm kép cung cấp hiệu suất tốt nhất bằng cách giảm thiểu cả hai loại phân cụm, tạo ra sự phân bố gần với ngẫu nhiên nhất. Tuy nhiên, nó phức tạp hơn và đòi hỏi chi phí tính toán cho hàm băm thứ hai. Một phương pháp khác là Key Offset, sử dụng chính giá trị của khóa để tính toán bước nhảy, ví dụ offset = [key/listSize]. Tóm lại, không có phương pháp nào là tốt nhất trong mọi trường hợp; sự lựa chọn tối ưu phụ thuộc vào đặc điểm cụ thể của ứng dụng và dữ liệu.

V. Bí quyết đánh giá hiệu quả thuật toán hashing và độ phức tạp

Đánh giá hiệu quả của một cấu trúc dữ liệu và thuật toán hash không chỉ dừng lại ở độ phức tạp Big-O lý thuyết. Trong thực tế, hiệu suất của bảng băm bị ảnh hưởng sâu sắc bởi các yếu tố như chất lượng hàm băm, chiến lược giải quyết xung đột, và hệ số tải của bảng. Mục tiêu phân tích là xác định số lần so sánh trung bình cần thiết cho một thao tác (tìm kiếm, chèn, xóa). Trong kịch bản lý tưởng không có xung đột, độ phức tạp là O(1). Tuy nhiên, khi xung đột xảy ra, chi phí sẽ tăng lên. Ví dụ, với dò tuyến tính, khi phân cụm sơ cấp xuất hiện, số lần dò có thể tăng lên đáng kể. Việc phân tích này giúp các lập trình viên lựa chọn sự kết hợp tối ưu giữa hàm băm và phương pháp giải quyết xung đột cho một bài toán cụ thể. Thực hiện các thử nghiệm thực tế (experiment program) để đánh giá các phương pháp trên các bộ dữ liệu khác nhau cũng là một bước quan trọng để xác thực các phân tích lý thuyết. Một hệ thống hashing tốt phải duy trì được hiệu suất gần O(1) ngay cả khi hệ số tải cao.

5.1. Phân tích độ phức tạp Big O cho các hoạt động trên bảng băm

Về mặt lý thuyết, các hoạt động chính trên bảng băm – chèn, xóa và tìm kiếm – đều có độ phức tạp trung bình là O(1). Điều này dựa trên giả định rằng hàm băm phân tán các khóa một cách đồng đều và hệ số tải (α = n/m, với n là số phần tử và m là kích thước bảng) thấp. Tuy nhiên, trong trường hợp xấu nhất, hiệu suất có thể suy giảm nghiêm trọng. Nếu tất cả các khóa đều băm vào cùng một địa chỉ, bảng băm sẽ hoạt động không khác gì một danh sách liên kết, và độ phức tạp cho các thao tác sẽ trở thành O(n). Phân tích hiệu suất thực tế thường dựa trên hệ số tải α. Ví dụ, đối với địa chỉ mở, số lần dò trung bình cho một tìm kiếm không thành công là khoảng 1/(1-α). Khi α tiến gần đến 1 (bảng gần đầy), số lần dò tăng vọt. Do đó, để duy trì hiệu suất O(1), việc giữ hệ số tải ở mức thấp (ví dụ, dưới 0.7) và chọn một cơ chế giải quyết xung đột tốt là cực kỳ quan trọng.

5.2. Hiện tượng phân cụm sơ cấp và thứ cấp clustering

Phân cụm (Clustering) là hiện tượng các phần tử bị chiếm dụng trong bảng băm có xu hướng tập hợp lại thành các khối. Đây là kẻ thù chính của hiệu suất hashing khi sử dụng địa chỉ mở. Phân cụm sơ cấp (Primary clustering), đặc trưng của dò tuyến tính, xảy ra khi các khóa có địa chỉ nhà khác nhau nhưng lại rơi vào cùng một chuỗi dò, tạo ra các cụm ngày càng lớn. Một khi một cụm hình thành, xác suất một phần tử mới rơi vào cụm đó sẽ tăng lên, làm chuỗi dò dài ra và hiệu suất giảm sút. Phân cụm thứ cấp (Secondary clustering) là một vấn đề tinh vi hơn, xảy ra trong dò bậc hai. Các khóa có cùng địa chỉ nhà sẽ luôn đi theo cùng một chuỗi dò, mặc dù chuỗi này không phải là tuần tự. Điều này vẫn có thể làm tăng nhẹ thời gian tìm kiếm. Các phương pháp như băm kép được thiết kế đặc biệt để phá vỡ các mẫu này, đảm bảo rằng chuỗi dò phụ thuộc vào toàn bộ khóa chứ không chỉ địa chỉ nhà của nó, qua đó giảm thiểu cả hai loại phân cụm và duy trì hiệu suất cao.

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

Data Structure and Algorithms [CO2003] Chapter 9 - Hash Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Faculty of Computer Science and Engineering Hochiminh city University of Technology Contents 1. Collision resolution Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 1 / 44 Outcomes • 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 pseudocode and give examples to show their algorithms.4 - Implement hashing tables using C/C++.5 - Analyze the complexity and develop experiment (program) to evaluate methods supplied for hashing tables.2 - Analyze algorithms and use Big-O notation to characterize the computational complexity of algorithms composed by using the following control structures: sequence, branching, and iteration (not recursion).

Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 2 / 44 Basic concepts Basic concepts • Sequential search: O(n) • Binary search: O(log2 n) → Requiring several key comparisons before the target is found. Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 3 / 44 Basic concepts Search complexity: Size Binary Sequential (Av- Sequential (Worst erage) Case) 16 4 8 16 50 6 25 50 256 8 128 256 1,000 10 500 1,000 10,000 14 5,000 10,000 100,000 17 50,000 100,000 1,000,000 20 500,000 1,000,000 Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 4 / 44 Basic concepts Is there a search algorithm whose complexity is O(1)? Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 5 / 44 Basic concepts Is there a search algorithm whose complexity is O(1)? YES Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 5 / 44 Basic concepts Figure 1: Each key has only one address Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 6 / 44 Basic concepts Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 7 / 44 Basic concepts • Home address: address produced by a hash function. • Prime area: memory that contains all the home addresses. Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 8 / 44 Basic concepts • Home address: address produced by a hash function.

• Prime area: memory that contains all the home addresses. • Synonyms: a set of keys that hash to the same location. • Collision: the location of the data to be inserted is already occupied by the synonym data. Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 8 / 44 Basic concepts • Home address: address produced by a hash function. • Prime area: memory that contains all the home addresses. • Synonyms: a set of keys that hash to the same location. • Collision: the location of the data to be inserted is already occupied by the synonym data.

• Ideal hashing: • No location collision • Compact address space Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 8 / 44 Basic concepts Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 9 / 44 Basic concepts Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 10 / 44 Basic concepts Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 11 / 44 Basic concepts Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 12 / 44 Hash functions Hash functions • Direct hashing • Modulo division • Digit extraction • Mid-square • Folding • Rotation • Pseudo-random Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 13 / 44 Direct Hashing The address is the key itself: hash(Key) = Key Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 14 / 44 Direct Hashing • Advantage: there is no collision.

• Disadvantage: the address space (storage size) is as large as the key space. Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 15 / 44 Modulo division Address = Key mod listSize • Fewer collisions if listSize is a prime number. • Example: Numbering system to handle 1,000,000 employees Data space to store up to 300 employees hash(121267) = 121267 mod 307 = 2 Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 16 / 44 Digit extraction Address = selected digits f rom Key Example: 379452→394 121267→112 378845→388 160252→102 045128→051 Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 17 / 44 Mid-square Address = middle digits of Key 2 Example: 9452 * 9452 = 89340304→3403 Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 18 / 44 Mid-square • Disadvantage: the size of the Key 2 is too large. • Variations: use only a portion of the key.

Example: 379452: 379 * 379 = 143641→364 121267: 121 * 121 = 014641→464 045128: 045 * 045 = 002025→202 Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 19 / 44 Folding The key is divided into parts whose size matches the address size. Example: Key = 123|456|789 fold shift 123 + 456 + 789 = 1368 → 368 Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 20 / 44 Folding The key is divided into parts whose size matches the address size.

Example: Key = 123|456|789 fold shift 123 + 456 + 789 = 1368 → 368 fold boundary 321 + 456 + 987 = 1764 → 764 Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 20 / 44 Rotation • Hashing keys that are identical except for the last character may create synonyms. • The key is rotated before hashing. original key rotated key 600101 160010 600102 260010 600103 360010 600104 460010 600105 560010 Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 21 / 44 Rotation • Used in combination with fold shift. original key rotated key 600101 → 62 160010 → 26 600102 → 63 260010 → 36 600103 → 64 360010 → 46 600104 → 65 460010 → 56 600105 → 66 560010 → 66 Spreading the data more evenly across the address space. Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 22 / 44 Pseudo-random For maximum efficiency, a and c should be prime numbers.

Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 23 / 44 Pseudo-random Example: Key = 121267 a = 17 c=7 listSize = 307 Address = ((17*121267 + 7) mod 307 = (2061539 + 7) mod 307 = 2061546 mod 307 = 41 Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 24 / 44 Collision resolution Collision resolution • Except for the direct hashing, none of the others are one-to-one mapping → Requiring collision resolution methods • Each collision resolution method can be used independently with each hash function Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 25 / 44 Collision resolution • Open addressing • Linked list resolution • Bucket hashing Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 26 / 44 Open addressing When a collision occurs, an unoccupied element is searched for placing the new element in. Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 27 / 44 Open addressing Hash function: h : U → {0, 1, 2, ., m − 1} set of keys addresses Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 28 / 44 Open addressing Hash and probe function: hp : U × {0, 1, 2, ., m − 1} set of keys probe numbers addresses Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 29 / 44 Open Addressing Algorithm hashInsert(ref T <array>, val k <key>) Inserts key k into table T. i=0 while i < m do j = hp(k, i) if T[j] = nil then T[j] = k return j else i=i+1 end end return error: “hash table overflow” End hashInsert Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 30 / 44 Open Addressing Algorithm hashSearch(val T <array>, val k <key>) Searches for key k in table T. i=0 while i < m do j = hp(k, i) if T[j] = k then return j else if T[j] = nil then return nil else i=i+1 end end return nil End hashSearch Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 31 / 44 Open Addressing There are different methods: • Linear probing • Quadratic probing • Double hashing • Key offset Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 32 / 44 Linear Probing • When a home address is occupied, go to the next address (the current address + 1): hp(k, i) = (h(k) + i) mod m Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 33 / 44 Linear Probing • When a home address is occupied, go to the next address (the current address + 1): hp(k, i) = (h(k) + i) mod m Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 33 / 44 Linear Probing Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 34 / 44 Linear Probing • Advantages: • quite simple to implement • data tend to remain near their home address (significant for disk addresses) • Disadvantages: • produces primary clustering Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 35 / 44 Quadratic Probing • The address increment is the collision probe number squared: hp(k, i) = (h(k) + i2 ) mod m Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 36 / 44 Quadratic Probing • Advantages: • works much better than linear probing • Disadvantages: • time required to square numbers • produces secondary clustering h(k1 ) = h(k2 ) → hp(k1 , i) = hp(k2 , i) Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 37 / 44 Double Hashing • Using two hash functions: hp(k, i) = (h1 (k) + ih2 (k)) mod m Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 38 / 44 Key Offset • The new address is a function of the collision address and the key. of f set = [key/listSize] newAddress = (collisionAddress + of f set) mod listSize Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 39 / 44 Key Offset • The new address is a function of the collision address and the key. of f set = [key/listSize] newAddress = (collisionAddress + of f set) mod listSize hp(k, i) = (hp(k, i − 1) + [k/m]) mod m Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 39 / 44 Open addressing Hash and probe function: hp : U × {0, 1, 2, ., m − 1} set of keys probe numbers addresses {hp(k, 0), hp(k, 1),. , hp(k, m − 1)} is a permutation of {0, 1,. , m − 1} Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 40 / 44