BẢNG BĂM TRONG CẤU TRÚC DỮ LIỆU

     
Mở đầu Mở đầu Hàng đợi ưu tiên Hàng đợi ưu tiên Heap ra mắt về Heap, max heap Min Heap bố trí heap sort Bảng băm - Hash table Bảng băm - Hash table giải quyết và xử lý xung bỗng - Separate chaining

Giới thiệu về hashing

Hashing là một kỹ thuật dùng để làm xác định độc nhất vô nhị một đối tượng rõ ràng từ một đội các đối tượng người sử dụng tương từ nó. Một vài lấy ví dụ như về hashing trong cuộc sống đời thường thực tế:

Mỗi cuốn sách trong thư viện cũng rất được gán cho 1 ID duy nhất, từ bỏ ID này ta hoàn toàn có thể biết được vị trí đúng chuẩn của nó trong tủ sách hoặc các người tiêu dùng đã mượn nó.

Bạn đang xem: Bảng băm trong cấu trúc dữ liệu

Trong những ví dụ trên, sách và sinh viên đã có được mã hóa với cùng 1 ID duy nhất, chuyên môn đó gọi là hashing.

Như vậy ta cũng hoàn toàn có thể định nghĩa hashing là kỹ thuật chuyển đổi một khóa (key) trở thành một trong những nguyên bằng phương pháp dùng những công thức toán học. Công thức toán học này được tiến hành trong một hàm gọi là hash function (hàm băm). Một key lúc qua xử lý của hàm băm sẽ sinh ra một trong những nguyên duy nhất được hotline là mã băm (hash code).

Giả sử rằng các bạn có một đối tượng, và chúng ta một gán mang đến nó một ID để dễ dàng quản lý. Lúc gán cho đối tượng người dùng một ID thì một cặp key/value được hình thành, cùng với key là ID mà bạn gán với value đó là đối tượng được gán đến ID đó.

Để tiến hành việc trên, đơn giản dễ dàng là chúng ta cũng có thể dùng mảng, trong lúc này key chính là chỉ số của mảng, khu vực lưu trữ đối tượng người tiêu dùng (value). Tuy nhiên, trong trường vừa lòng khi key quá lớn thì bài toán dùng key trực tiếp làm cho chỉ số của mảng không còn hiệu quả nữa, và bạn nên dùng hashing.

Sau lúc hashing, cặp key/value (key vẫn dược đưa đổi) được chứa trong một cấu trúc dữ liệu là bảng băm (hash table). Bằng phương pháp sử dụng key trong bảng băm, bạn có thể truy cập các thành phần trong bảng này trong thời hạn O(1).

Hashing rất có thể được tiến hành trong nhị bước:

Chuyển đổi khóa (key) thành số nguyên (khóa nhỏ hơn) sử dụng hàm băm. Khóa sau khi đổi khác có thể được dùng như chỉ số để đựng phần tử thuở đầu nằm vào bảng băm.

Phần tử được đựng trong bảng băm có thể được truy cập nhanh chóng qua khóa đang được đưa đổi.

hash_code = hash_function(key)

index = hash % array_size

Với bí quyết chuyển đồi này, hash_code là chủ quyền với form size của mảng, kế tiếp giá trị của nó được thay đổi về index (index có giá trị trường đoản cú 0 tới array_size - 1).

Hàm băm (hash function)

Hàm băm là một hàm ngẫu nhiên có thể được áp dụng để ánh xạ một bộ dữ liệu có kích cỡ tùy ý cho tới một bộ tài liệu có kích thước cố định và thắt chặt nằm vào bảng băm. Quý giá trả về vày hàm băm được điện thoại tư vấn là mã băm (hash code hoặc hash value).

Để giành được một cơ chế hashing tốt, ta rất cần được có một hàm băm tốt với những đk cơ bản như sau:

Dễ tính toán.

Phân phối đồng nhất: Mỗi địa chỉ trong bảng được cung cấp đếu cho từng key (khóa băm).

Ít xung đột: Sự xung bất chợt (collision) xẩy ra khi cơ mà có những cặp phần tử khác nhau được ánh xạ tới chung một mã băm.

Sự xung thốt nhiên trong bảng băm gây tác động lớn tới hiệu năng của loại kết cấu dữ liệu này, cho nên vì vậy với bảng băm, việc sử dụng các kỹ thuật để sút xung tự dưng trong bảng là khôn xiết quan trọng.

Cùng xem ví dụ sau để xem tại sao chúng ta cần một hàm băm tốt

Giả sử bọn họ phải chứa những chuỗi sau trong một bảng băm, sử dụng kỹ thuật hashing: "abcdef", "bcdefa", "cdefab" , "defabc".

Để giám sát các chỉ số cho câu hỏi lưu trữ những chuỗi, ta thực hiện hàm băm với những cách tiến hành như sau.

Xem thêm: Mẫu Lịch Làm Việc Trong Tháng, Mẫu Lịch Tuần Miễn Phí Trên Office

Cách thực hiện thứ nhất:

Chỉ số cho mỗi chuỗi bằng tổng mức mã ASCII của mỗi phần ký kết tự trong chuỗi.

Gọi cực hiếm mã ASCII của một cam kết tự x là aval(x), istr(s) là tổng mức vốn mã ASCII của chuỗi s, ta có:

istr(abcdef) = aval(a) + aval(b) + aval(c) + aval(d) + aval(e) + aval(f) = 599

istr(bcdefa) = aval(b) + aval(c) + aval(d) + aval(e) + aval(f) + aval(a) = 599

istr(cdefab) = aval(c) + aval(d) + aval(e) + aval(f) + aval(a) + aval(b) = 599

istr(defabc) = aval(d) + aval(e) + aval(f) + aval(a) + aval(b) + aval(c) = 599

Với aval(a) = 97, aval(b) = 98, aval(c) = 99, aval(d) = 100, aval(e) = 101, aval(f) = 102

Và chỉ số được tính oán thù bằng cách chia đem phần dư istr(s) đến số ký kết tự tất cả trong chuỗi s.

Gọi chỉ số của chuỗi s là idx(s) ta có:

idx(abcdef) = idx(bcdefa) = idx(cdefab) = idx(defabc) = 599 % 6 = 5

Như vậy 4 chuỗi làm việc trên sẽ được ánh xạ vào phổ biến một chỉ số trong bảng băm.

Bởi bởi chỉ số của toàn bộ các chuỗi là giống nhau, nên bạn có thể tạo một danh sách link với chỉ số đó để chèn những chuỗi vào.

*

Hình 1: Bảng băm không tối ưu

Với bảng băm ngơi nghỉ trên, ta hoàn toàn có thể nhận thấy rằng để truy vấn vào một chuỗi trong bảng thì trong trường phù hợp xấu độc nhất vô nhị ta đang mất thời gian là O(N). Do vậy với giải pháp thực hiện đầu tiên ta bao gồm một hàm băm không về tối ưu.

Cách thực hiện thứ 2:

Ta vẫn dùng cách khác để tính toán chỉ số cho những chuỗi, với phương pháp này, chỉ số của một chuỗi sẽ bằng tổng mã ASCII của từng cam kết tự nhân với thứ tự thu xếp của cam kết tự đó trong chuỗi. Rồi lấy tổng đó chia cho số nguyên tố bất kỳ. Trong bài này số được chọn là 2069 (số nguyên tố lớn nhất của tổng bé nhất).

Chuỗi

Tính toán vào hàm băm

Chỉ số

abcdef

(97*1 + 98*2 + 99*3 + 100*4 + 101*5 + 102*6) % 2069

38

bcdefa

(98*1 + 99*2 + 100*3 + 101*4 + 102*5 + 97*6) % 2069

23

cdefab

(99*1 + 100*2 + 101*3 + 102*4 + 97*5 + 98*6) % 2069

14

defabc

(100*1 + 101*2 + 102*3 + 97*4 + 98*5 + 99*6) % 2069

11

*

Hình 2: Bảng băm tối ưu hơn

Bảng băm - Hash table

Bảng băm là một loại cấu trúc dữ liệu được dùng để chứa cặp key/value. Nó sử dụng hàm băm để tính toán chỉ số, chỉ số này được dùng mang đến việc chèn hoặc tìm kiếm dữ liệu được dễ dàng hơn. Với một bảng băm có một hàm băm được thực hiện tốt thì vào trường hợp lý tưởng, việc tìm kiếm các phần tử trong bảng có thời gian là O(1).

Ta hãy cùng coi xét ví dụ sau:

Yêu cầu: Đếm số lần xuất hiện của các ký tự trong chuỗi sau: “ababcd”.

Cách tiếp cận đơn giản

Ta sẽ duyệt qua tất cả các phần tử của chuỗi và đếm số lần xuất hiện của từng ký tự. Độ phức tạp về thời gian của cách tiếp cận này là O(26*N) với N là độ dài của chuỗi và 26 là số ký tự có thể có trong chuỗi (số lượng ký tự trong bảng chữ cái tiếng anh).

string S = "ababcd"void countChar(string S){ for(char c = "a"; c Kết quả sau khoản thời gian chạy kiểm tra tại https://www.onlinegdb.com/online_c++_compiler .

*

Mã nguồn hoàn chỉnh để chạy chương trình ở bên trên có thể tìm thấy tại đây.

Cách tiếp cận tối ưu hơn

Sử dụng kỹ thuật hashing cho bài toán này. Ta dùng một mảng có kích thước là 26 để chứa giá trị là số lần xuất hiện của một ký tự trong chuỗi.

Dùng hàm băm để tính toán ra chỉ số của ký tự vào chuỗi.

Duyệt qua toàn bộ chuỗi, và tăng giá trị của phần tử mảng có chỉ số tương ứng bằng với chỉ số của ký tự vừa được tính ở bước trên.

#include using namespace std;int C<26>;/* Hàm băm tính toán chỉ số của ký tự trong chuỗi */int hash_function(char c) return (c - "a");/* Hàm đếm số lần xuất hiện của một ký tự trong chuỗi */void count_char(string S) { for (int i = 0; i

Kết quả sau khoản thời gian chạy chương trình trên.

*

Kết luận

Bởi vày hàm băm trả về một khóa có giá trị bé dại hơn khóa cội (là một vài nguyên phệ hoặc một chuỗi dài), điều này dẫn đến việc hai khóa hoàn toàn có thể có tầm thường một giá bán trị.

Xem thêm: Câu Chuyện Tào Tháo Với Rừng Mơ ? Câu Chuyện Tào Tháo Với Rừng Mơ

Tình huống khi một phần tử new được chèn vào bảng băm có khóa ánh xạ cho tới một vị trí sẽ có tài liệu (ánh xạ tới bình thường một giá trị với một khóa khác) được gọi là sự việc xung đột. Và họ phải xử lý vấn đề này bằng các kỹ thuật xử lý xung đột.