ĐỀ TÀI BẢNG BĂM VÀ CÁC KỸ THUẬT XỬ LÝ VA CHẠM

TỔNG QUAN VỀ BẢNG BĂM

Các thuộc tính của một hàm băm

Một hàm băm chất lượng cần đáp ứng các tiêu chí cơ bản, bao gồm khả năng tính toán dễ dàng và không phải là một thuật toán phức tạp.

+ Phân bố đồng đều: Nó cần phải phân phối đồng đều trên bảng băm, không xảy ra việc tập trung thành các cụm

+ Ít va chạm: Va chạm xảy ra khi các cặp phần tử được ánh xạ tới cùng một giá trị băm

Va chạm băm là một vấn đề không thể tránh khỏi khi xử lý một tập hợp ngẫu nhiên lớn các khóa Chẳng hạn, khi băm 2500 khóa vào một triệu ô nhớ, có đến 95% khả năng ít nhất hai khóa sẽ trùng nhau trong một ô nhớ, ngay cả khi phân bố hoàn toàn ngẫu nhiên Do đó, cần thiết phải áp dụng các kỹ thuật để xử lý các tình huống va chạm băm này.

CÁC KỸ THUẬT XỬ LÝ VA CHẠM

Separate chaining (open hashing)

Kỹ thuật separate chaining là phương pháp phổ biến nhất để xử lý va chạm trong bảng băm, thường được triển khai thông qua danh sách liên kết Khi một phần tử được thêm vào bảng băm, nó sẽ được lưu giữ trong danh sách liên kết tương ứng với chỉ mục của nó Nếu xảy ra va chạm, các phần tử sẽ được lưu trữ chung trong cùng một danh sách liên kết.

Hình 2.1: Separate chaining khi xảy ra va chạm Để xử lý vụ va chạm,

- Kỹ thuật này tạo ra một danh sách liên kết đến vị trí mà xung đột xảy ra.

- Sau đó, khóa mới sẽ được chèn vào danh sách liên kết.

- Những danh sách được liên kết với các vị trí xuất hiện giống như chuỗi.

- Đó là lý do tại sao, kỹ thuật này được gọi là chuỗi riêng biệt (Separate chaining.)

2.1.1, Độ phức tạp về thời gian Để tìm kiếm

Tiểu luận Chương II: Các kỹ thuật xử lý va chạm

- Trong trường hợp xấu nhất, tất cả các khóa có thể ánh xạ đến cùng một nhóm của bảng băm.

- Trong trường hợp như vậy, tất cả các khóa sẽ có trong một danh sách được liên kết duy nhất.

- Tìm kiếm tuần tự sẽ phải được thực hiện trên danh sách liên kết để thực hiện tìm kiếm.

- Vì vậy, thời gian cần thiết để tìm kiếm trong trường hợp xấu nhất là O (n). Để xóa

- Trong trường hợp xấu nhất, khóa có thể phải được tìm kiếm trước rồi mới xóa.

- Trong trường hợp xấu nhất, thời gian tìm kiếm là O (n).

- Vì vậy, thời gian cần thiết để xóa trong trường hợp xấu nhất là O (n).

Hệ số tải (α) được định nghĩa là: hệ số t i ả (α )= số ph n ầ tử có trong b ng ả băm t ng ổ kíchth c ướ c a ủ b ng ả băm

Nếu Hệ số tải (α) = không đổi, thì độ phức tạp thời gian của Chèn, Tìm kiếm, Xóa = Θ (1)

2.1.2 Cài đặt bảng băm sử dụng Separate chaining

Giả định: Hàm băm sẽ trả về số int trong [0, 19].

2.1.3 Bài toán thực hành dựa vào Separate Chaining

Sử dụng hàm băm 'key mod 7', chèn chuỗi phím sau vào bảng băm

Sử dụng kỹ thuật chuỗi riêng biệt để giải quyết va chạm.

Chuỗi khóa đã cho sẽ được chèn vào bảng băm như sau:

- Vẽ một bảng băm trống.

- Đối với hàm băm đã cho, phạm vi giá trị băm có thể có là [0, 6].

- Vì vậy, hãy vẽ một bảng băm trống bao gồm 7 nhóm như-

- Chèn lần lượt các khóa đã cho vào bảng băm.

- Khóa đầu tiên được chèn vào bảng băm = 50.

- Nhóm của bảng băm mà 50 bản đồ chính = 50 mod 7 = 1.

- Vì vậy, khóa 50 sẽ được chèn vào thùng-1 của bảng băm như

- Khóa tiếp theo sẽ được chèn vào bảng băm = 700.

- Nhóm của bảng băm mà khóa 700 bản đồ = 700 mod 7 = 0.

- Vì vậy, khóa 700 sẽ được chèn vào thùng-0 của bảng băm như-

- Khóa tiếp theo được chèn vào bảng băm = 76.

- Nhóm của bảng băm mà khóa 76 ánh xạ = 76 mod 7 = 6.

- Vì bucket-1 đã bị chiếm dụng nên xảy ra va chạm.

- Chuỗi riêng biệt xử lý va chạm bằng cách tạo một danh sách được liên kết tới nhóm-1.

- Vì vậy, khóa 92 sẽ được chèn vào thùng-1 của bảng băm nhưsau

- Vì vậy, khóa 73 sẽ được chèn vào thùng-3 của bảng băm như sau

- Vì xô-3 đã bị chiếm dụng nên xảy ra va chạm.

- Chuỗi riêng biệt xử lý va chạm bằng cách tạo một danh sách được liên kết với nhóm-3.

2.2, Linear probing (open addressing or closed hashing)

Một phương pháp để giải quyết va chạm trong băm bảng được gọi là giải quyết mở Thay vì tạo ra cấu trúc dữ liệu thứ cấp, phương pháp này xử lý các xung đột bằng cách tìm kiếm các vị trí khác trong bảng Cụ thể, chúng ta sử dụng một chuỗi các hàm băm h0, h1, h2, , Hm-1, sao cho với bất kỳ mục x nào, các đầu dò h0(x), h1(x), , Hm-1(x) là một hoán vị của 0, 1, 2, , m-1.

Trong khác từ, khác nhau băm chức năng trong các chuỗi luôn map x để khác nhau địa điểm trong các hash bảng.

Để tìm kiếm giá trị x, thuật toán sẽ trả về chỉ số mảng i nếu T[i] = x Nếu x không có trong bảng nhưng có một vùng trống, thuật toán sẽ thông báo 'vắng mặt' Ngược lại, nếu x không có trong bảng và không có vị trí trống nào, kết quả sẽ là 'đầy'.

Trong địa chỉ mở, tất cả các bản ghi mục nhập được lưu trữ trực tiếp trong mảng thay vì trong danh sách liên kết Khi cần chèn một mục nhập mới, chỉ số băm của giá trị sẽ được tính toán và mảng sẽ được kiểm tra bắt đầu từ chỉ số băm Nếu vị trí tại chỉ số băm đã có dữ liệu, quá trình sẽ tiếp tục tìm kiếm vị trí trống bằng cách sử dụng một trình tự thăm dò cho đến khi tìm thấy chỗ trống để chèn bản ghi.

Trình tự thăm dò là quy trình được áp dụng khi kiểm tra các mục nhập Trong các loại trình tự thăm dò khác nhau, có thể có các khoảng thời gian khác nhau giữa các vị trí đầu vào hoặc đầu dò liên tiếp.

Khi thực hiện tìm kiếm mục nhập trong bảng băm, mảng sẽ được quét theo trình tự cho đến khi tìm thấy phần tử đích hoặc một vị trí không sử dụng, cho thấy không có khóa tương ứng trong bảng Thuật ngữ "mở địa chỉ" chỉ ra rằng địa chỉ của mục không được xác định bởi giá trị băm Đầu dò tuyến tính là phương pháp trong đó khoảng cách giữa các đầu dò liên tiếp là cố định, thường là 1 Cụ thể, chỉ số được băm cho một mục sẽ được tính toán theo công thức index = index % hashTableSize, sau đó các chỉ số tiếp theo sẽ được xác định bằng cách cộng thêm 1, 2, 3, v.v vào chỉ số ban đầu.

 Trong open addressing (địa chỉ mở)

- Không giống như chuỗi riêng biệt, tất cả các khóa được lưu trữ bên trong bảng băm.

- Không có khóa nào được lưu trữ bên ngoài bảng băm.

 Các kỹ thuật được sử dụng để đánh địa chỉ mở là

2.2.2, Hoạt động trong địa chỉ mở:

Hãy để chúng tôi thảo luận về cách các hoạt động được thực hiện trong địa chỉ mở

- Hàm băm được sử dụng để tính toán giá trị băm cho một khóa được chèn vào.

- Giá trị băm sau đó được sử dụng như một chỉ mục để lưu trữ khóa trong bảng băm.

 Để chèn một khóa nếu vị trí giá trị băm được tính toán trong bảng băm là

- Lưu khóa 1 vị trí không có người sử dụng

- Địa chỉ tiếp theo được tìm ra bằng cách di chuyển từng nơi một cho đến khi tìm thấy vị trí trống và khóa chúng tôi đã lưu.

- Để tìm kiếm một khóa, vị trí giá trị băm được tính toán sẽ được so sánh

 So sánh các kết quả phù hợp để trả về trị trí

Nếu không tìm thấy khóa, quá trình so sánh địa chỉ tiếp theo sẽ diễn ra bằng cách di chuyển từng vị trí một, cho đến khi xác định được khóa hoặc gặp phải một vị trí trống.

Trong trường hợp va chạm,

- Việc dò tìm được thực hiện cho đến khi tìm thấy một thùng rỗng.

- Sau khi tìm thấy một thùng rỗng, chìa khóa sẽ được đưa vào.

- Việc thăm dò được thực hiện theo kỹ thuật được sử dụng để định địa chỉ mở.

2.2.2.2 Hoạt động tìm kiếm Để tìm kiếm bất kỳ khóa cụ thể nào,

- Giá trị băm của nó nhận được bằng cách sử dụng hàm băm được sử dụng.

- Sử dụng giá trị băm, nhóm của bảng băm đó sẽ được kiểm tra.

- Nếu khóa được yêu cầu được tìm thấy, khóa sẽ được tìm kiếm.

- Nếu không, các nhóm tiếp theo sẽ được kiểm tra cho đến khi tìm thấy khóa cần thiết hoặc một nhóm trống.

- Thùng rỗng chỉ ra rằng khóa không có trong bảng băm.

 Vì sao thăm dò tuyển tính lại khác nhau :

Trong băm chuỗi, va chạm chỉ xảy ra khi hai giá trị có chính xác cùng một mã băm.

● Trong thăm dò tuyến tính, va chạm có thể xảy ra giữa các yếu tố với các mã băm khác nhau.

● Để phân tích thăm dò tuyến tính, chúng ta cần biết nhiều hơn có bao nhiêu phần tử va chạm với nhau.

 Để tra cứu một phần tử x, tính h (x) và bắt đầu nhìn ở đó.

● Di chuyển xung quanh vòng cho đến khi hoặc phần tử được tìm thấy hoặc một điểm trống được phát hiện.

● (Chúng tôi sẽ giả định tải yếu tố cấm chúng tôi chèn rất nhiều yếu tố rằng không có miễn phí dấu cách.)

- Khóa được tìm kiếm đầu tiên và sau đó bị xóa.

- Sau khi xóa khóa, nhóm cụ thể đó được đánh dấu là "đã xóa".

- Trong khi chèn, các nhóm được đánh dấu là “đã xóa” được coi như bất kỳ nhóm trống nào khác.

- Trong quá trình tìm kiếm, tìm kiếm không bị kết thúc khi gặp phải nhóm được đánh dấu là “đã xóa”.

- Tìm kiếm chỉ kết thúc sau khi tìm thấy khóa được yêu cầu hoặc một nhóm trống.

2.2.3, Linear Probing( Đầu dò tuyến tính)

Trong thăm dò tuyến tính,

- Khi va chạm xảy ra, chúng tôi thăm dò tuyến tính cho xô tiếp theo.

- Chúng tôi tiếp tục thăm dò cho đến khi tìm thấy một thùng rỗng.

- Nó rất dễ dàng để tính toán.

Chiến lược thăm dò truy cập các mục nhập liên tiếp trong bảng băm, cụ thể là thăm dò tuyến tính, cho thấy khả năng bộ nhớ đệm tốt hơn và mang lại hiệu suất vượt trội so với các chiến lược khác.

Miễn là hệ số tải nhỏ hơn 1, chiều dài của bất kỳ trình tự thăm dò nào sẽ không thay đổi Điều này đảm bảo hiệu suất ổn định ngay cả với các hàm băm có tính độc lập hạn chế.

Khi hệ số tải của bảng băm tiến gần đến 1, số lượng đầu dò phát triển nhanh chóng do các ô bị chiếm đóng có xu hướng tụ lại Điều này mang lại lợi thế cho thăm dò tuyến tính, vì bất kỳ truy cập nào vào bảng băm sẽ tải thêm các mục nhập lân cận vào bộ nhớ cache, cải thiện hiệu suất truy xuất dữ liệu.

- Vấn đề chính của thăm dò tuyến tính là phân cụm.

- Nhiều phần tử liên tiếp tạo thành nhóm.

- Sau đó, phải mất thời gian để tìm kiếm một phần tử hoặc tìm một thùng rỗng. Độ phức tạp về thời gian

Tiểu luận Chương II: Các kỹ thuật xử lý va chạm Điều này là bởi vì:

- Ngay cả khi chỉ có một phần tử hiện diện và tất cả các phần tử khác đều bị xóa.

- Sau đó, các điểm đánh dấu “đã xóa” hiện diện trong bảng băm thực hiện tìm kiếm trên toàn bộ bảng.

2.2.4, Bài toán thực hành dựa vào địa chỉ mở (open addressing)

Sử dụng hàm băm 'key mod 7', chèn chuỗi phím sau vào bảng băm-

Sử dụng kỹ thuật thăm dò tuyến tính để giải quyết va chạm.

Chuỗi khóa đã cho sẽ được chèn vào bảng băm như sau:

- Vẽ một bảng băm trống.

- Đối với hàm băm đã cho, phạm vi giá trị băm có thể có là [0, 6].

- Vì vậy, hãy vẽ một bảng băm trống bao gồm 7 nhóm như sau

- Chèn lần lượt các khóa đã cho vào bảng băm.

- Khóa đầu tiên được chèn vào bảng băm = 50.

- Khóa tiếp theo sẽ được chèn vào bảng băm = 700.

- Nhóm của bảng băm mà khóa 700 bản đồ = 700 mod 7 = 0.

 Khóa tiếp theo được chèn vào bảng băm = 76.

 Nhóm của bảng băm mà khóa 76 ánh xạ = 76 mod 7 = 6.

 Vì vậy, khóa 76 sẽ được chèn vào thùng-6 của bảng băm như sau

- Để xử lý vụ va chạm, kỹ thuật thăm dò tuyến tính tiếp tục thăm dò tuyến tính cho đến khi tìm thấy một thùng rỗng.

- Thùng rỗng đầu tiên là thùng-2.

- Vì vậy, khóa 92 sẽ được chèn vào thùng-3 của bảng băm như sau:

2.2.5, So sánh Separate Chaining Vs Open Addressing

Chuỗi riêng biệt Mở địa chỉ

Các khóa được lưu trữ bên trong bảng băm cũng như bên ngoài bảng băm.

- Tất cả các khóa chỉ được lưu trữ bên trong bảng băm.

- Không có khóa nào hiện diện bên ngoài bảng băm.

Số lượng khóa được lưu trữ trong bảng băm thậm chí có thể vượt quá kích thước của bảng băm.

Số lượng khóa được lưu trữ trong bảng băm không bao giờ được vượt quá kích thước của bảng băm.

Xóa dễ dàng hơn Việc xóa rất khó.

Cần có thêm không gian để con trỏ lưu trữ các khóa bên ngoài bảng băm Không cần thêm không gian.

- Hiệu suất bộ nhớ cache kém. Điều này là do danh sách được liên kết lưu trữ các khóa bên ngoài bảng băm.

- Hiệu suất bộ nhớ cache tốt hơn. Điều này là do ở đây không có danh sách liên kết nào được sử dụng.

Một số thùng của bảng băm không bao giờ được sử dụng, dẫn đến lãng phí dung lượng.

Các nhóm có thể được sử dụng ngay cả khi không có bản đồ chính nào đến các nhóm cụ thể đó.

2.3, Phương pháp dò bậc hai (Quadratic Probing)

Bảng băm sử dụng phương pháp dò tuyến tính gặp khó khăn trong việc phân bố các phần tử không đều, trong khi bảng băm áp dụng phương pháp dò bậc hai cho phép rải các phần tử một cách đồng đều hơn.

Bảng băm trong bài viết này được thiết lập bằng danh sách kề với M phần tử, trong đó mỗi phần tử là một mẫu tin chứa trường key để lưu trữ khóa của các phần tử Để áp dụng phương pháp băm bậc hai, cần chọn số địa chỉ M là một số nguyên tố.

-Khi khởi động bảng băm thì tất cả trường key bị gán NULL.

-Thêm phần tử có khóa 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 M-1.

+) Nếu chưa bị xung đột thì thêm phần tử mới vào địa chỉ i này.

+) Nếu bị xung đột thì hàm băm lại lần 1 f1 sẽ xác định địa chỉ cách

1 2 , nếu lại bị xung đột thì hàm băm lại lần 2 f2 sẽ xét địa chỉ cách i 2 2 ,

…, tiếp tục quá trình như vậy cho đến khi nào tìm được trống và thêm phần tử vào địa chỉ này.

Để tìm kiếm một phần tử với khóa key trong bảng băm, ta bắt đầu bằng cách kiểm tra phần tử tại địa chỉ i = f(key) Nếu không tìm thấy, ta sẽ kiểm tra lần lượt các phần tử tại các địa chỉ i + 1, i + 2, i + 4, … cho đến khi tìm được khóa hoặc gặp một địa chỉ trống, chỉ ra rằng phần tử không tồn tại trong bảng.

Hàm băm lại trong phương pháp dò bậc hai sử dụng công thức fi(key) = (f(key) + i^2) % M, trong đó f(key) là hàm băm chính của bảng băm Phương pháp này cho phép truy xuất các địa chỉ theo cách bậc 2, giúp tối ưu hóa quá trình tìm kiếm trong bảng băm.

-Nếu đã dò đến cuối bảng thì trở về dò lại từ đầu bảng.

-Bảng băm minh họa có cấu trúc như sau:

Tập khóa K: tập số tự nhiên

Tập địa chỉ M: gồm 10 địa chỉ (M={0, 1, …, 9}

- Nên chọn số địa chỉ M là số nguyên tố Khi khởi động bảng băm thì tất cả M trường key được gán NULL, biến toàn cục N được gán 0.

-Bảng băm đầy khi N = M-1, và nên dành ít nhất một phần tử trống trên

Bảng băm này hiệu quả hơn so với bảng băm sử dụng phương pháp dò tuyến tính nhờ vào việc phân bố phần tử đều hơn Khi bảng băm chưa đầy, tốc độ truy xuất đạt mức O(1) Tuy nhiên, trong trường hợp xấu nhất khi bảng băm đầy, tốc độ truy xuất sẽ giảm do cần thực hiện nhiều lần so sánh.

Double Hashing

Băm kép (double hashing) là một kỹ thuật lập trình máy tính hiệu quả, kết hợp với địa chỉ mở (open addressing) trong bảng băm để xử lý xung đột băm Kỹ thuật này sử dụng hàm băm phụ của khóa làm điểm bù khi xảy ra xung đột, giúp cải thiện hiệu suất tìm kiếm Hàm băm kép cùng với địa chỉ mở là một cấu trúc dữ liệu cổ điển và quan trọng trong bảng T.

Kỹ thuật băm kép sử dụng một giá trị băm để chỉ mục trong bảng, sau đó lặp lại việc chuyển tiếp một khoảng cách cho đến khi tìm thấy giá trị mong muốn, một vị trí trống, hoặc khi toàn bộ bảng đã được kiểm tra Khoảng cách này được xác định bởi một hàm băm thứ hai, độc lập với hàm băm đầu tiên.

Khác với các phương pháp giải quyết va chạm thay thế như thăm dò tuyến tính và thăm dò bậc hai, phương pháp này phụ thuộc vào dữ liệu, dẫn đến việc các giá trị ánh xạ đến cùng một vị trí có trình tự nhóm khác nhau Điều này giúp giảm thiểu va chạm lặp lại và ảnh hưởng của việc phân cụm.

- Băm kép rất hữu ích nếu một ứng dụng yêu cầu một bảng băm nhỏ hơn vì nó có thể tìm thấy một vùng trống một cách hiệu quả.

Mặc dù chi phí tính toán có thể cao, băm kép lại cho phép tìm vị trí trống tiếp theo nhanh hơn so với phương pháp thăm dò tuyến tính.

Băm kép có thể được thực hiện bằng cách sử dụng công thức :

Công thức tính toán băm được biểu diễn như sau: (hash1 (key) + i * hash2 (key)) % TABLE_SIZE, trong đó hash1() và hash2() là các hàm băm, và TABLE_SIZE là kích thước của bảng băm Khi xảy ra va chạm, giá trị i sẽ được tăng lên để tìm vị trí tiếp theo trong bảng.

Hàm băm đầu tiên thường là hash1 (key) = key% TABLE_SIZE Một hàm băm thứ hai phổ biến là: hash2 (key) = PRIME - (key%

PRIME) trong đó PRIME là một số nguyên tố nhỏ hơn TABLE_SIZE.

Một chức năng Hash2 là:

 Nó không bao giờ được đánh giá bằng 0

 Phải đảm bảo rằng tất cả các ô đều có thể được thăm dò

2.4.2, Ví dụ về double hashing :

// CPP program to implement double hashing

#include using namespace std;

// Used in second hash function.

// Pointer to an array containing buckets int* hashTable; int curr_size; public:

// function to check if hash table is full bool isFull()

// if hash size reaches maximum size return (curr_size == TABLE_SIZE);

// function to calculate first hash int hash1(int key)

// function to calculate second hash int hash2(int key)

} hashTable = new int[TABLE_SIZE]; curr_size = 0; for (int i = 0; i < TABLE_SIZE; i++) hashTable[i] = -1;

// function to insert key into hash table void insertHash(int key)

// if hash table is full if (isFull()) return;

// get index from first hash int index = hash1(key);

// if collision occurs if (hashTable[index] != -1) {

// get index2 from second hash int index2 = hash2(key); int i = 1; while (1) {

// get newIndex int newIndex = (index + i * index2) % TABLE_SIZE;

// if no collision occurs, store

// the key if (hashTable[newIndex] == -1) { hashTable[newIndex] = key; break;

// if no collision occurs else hashTable[index] = key; curr_size++;

// function to search key in hash table void search(int key)

{ int index1 = hash1(key); int index2 = hash2(key); int i = 0; while (hashTable[(index1 + i * index2) % TABLE_SIZE] != key) { if (hashTable[(index1 + i * index2) % TABLE_SIZE] == -1) { cout

Tiêu đề	Bảng băm và các kỹ thuật xử lý va chạm
Tác giả	Nguyễn Lương Linh, Nguyễn Hữu Đức, Lê Đức Hiếu, Nguyễn Triệu Việt Hùng, Nguyễn Văn Nội
Người hướng dẫn	TS. Phạm Anh Thư
Trường học	Học viện công nghệ bưu chính viễn thông
Thể loại	tiểu luận
Năm xuất bản	2021
Thành phố	Hà Nội

Định dạng
Số trang	35
Dung lượng	719,78 KB