Giới thiệu về hashing
Hashing là một kỹ thuật dùng để xác định duy nhất một đối tượng cụ thể từ một nhóm các đối tượng tương tự nó. Một vài ví dụ về hashing trong cuộc sống thực tế:
Mỗi cuốn sách trong thư viện cũng được gán cho một ID duy nhất, từ ID này ta có thể biết được vị trí chính xác của nó trong thư viện hoặc các người dùng đã mượn nó.
Bạn đang xem: Hash table là gì
Trong các ví dụ trên, sách và sinh viên đã được mã hóa với một ID duy nhất, kỹ thuật đó gọi là hashing.
Như vậy ta cũng có thể định nghĩa hashing là kỹ thuật biến đổi một khóa (key) trở thành một số nguyên bằng cách dùng các công thức toán học. Công thức toán học này được thực hiện trong một hàm gọi là hash function (hàm băm). Một key khi qua xử lý của hàm băm sẽ sinh ra một số nguyên duy nhất được gọi là mã băm (hash code).
Giả sử rằng bạn có một đối tượng, và bạn một gán cho nó một ID để dễ quản lý. khi gán cho đối tượng một ID thì một cặp key/value được hình thành, với key là ID mà bạn gán và value chính là đối tượng được gán cho ID đó.
Để thực hiện việc trên, đơn giản là bạn có thể dùng mảng, khi này key chính là chỉ số của mảng, nơi lưu trữ đối tượng (value). Tuy nhiên, trong trường hợp khi key quá lớn thì việc dùng key trực tiếp làm chỉ số của mảng không còn hiệu quả nữa, và bạn nên dùng hashing.
Sau khi hashing, cặp key/value (key đã dược chuyển đổi) được chứa trong một cấu trúc dữ liệu là bảng băm (hash table). Bằng cách sử dụng key trong bảng băm, bạn có thể truy cập các phần tử trong bảng này trong thời gian O(1).
Hashing có thể được thực hiện trong hai bước:
Chuyển đổi khóa (key) thành số nguyên (khóa nhỏ hơn) dùng hàm băm. Khóa sau khi chuyển đổi có thể được dùng như chỉ số để chứa phần tử ban đầu nằm trong bảng băm.
Phần tử được chứa trong bảng băm có thể được truy cập nhanh chóng qua khóa đã được chuyển đổi.
hash_code = hash_function(key) index = hash % array_size |
Với cách chuyển đồi này, hash_code là độc lập với kích thước của mảng, sau đó giá trị của nó được chuyển đổi về index (index có giá trị từ 0 tới array_size – 1).
Hàm băm (hash function)
Hàm băm là một hàm bất kỳ có thể được sử dụng để ánh xạ một bộ dữ liệu có kích thước tùy ý tới một bộ dữ liệu có kích thước cố định nằm trong bảng băm. Giá trị trả về bởi hàm băm được gọi là mã băm (hash code hoặc hash value).
Để có được một cơ chế hashing tốt, ta cần phải có một hàm băm tốt với những điều kiện cơ bản như sau:
Dễ tính toán.
Phân phối đồng nhất: Mỗi vị trí trong bảng được phân phối đếu cho mỗi key (khóa băm).
Ít xung đột: Sự xung đột (collision) xảy ra khi mà có các cặp phần tử khác nhau được ánh xạ tới chung một mã băm.
Sự xung đột trong bảng băm gây ảnh hưởng lớn tới hiệu năng của loại cấu trúc dữ liệu này, cho nên với bảng băm, việc sử dụng các kỹ thuật để giảm xung đột trong bảng là vô cùng quan trọng.
Cùng xem ví dụ sau để thấy tại sao chúng ta cần một hàm băm tốt
Giả sử chúng ta phải chứa các chuỗi sau trong một bảng băm, sử dụng kỹ thuật hashing: {“abcdef”, “bcdefa”, “cdefab” , “defabc”}.
Để tính toán các chỉ số cho việc lưu trữ các chuỗi, ta sử dụng hàm băm với các cách thực hiện như sau.
Xem thêm: Viêm Đường Tiết Niệu Là Gì, Tất Tần Tật Về Nhiễm Trùng Đường Tiết Niệu
Cách thực hiện thứ nhất:
Chỉ số cho mỗi chuỗi bằng tổng giá trị mã ASCII của mỗi phần ký tự trong chuỗi.
Gọi giá trị mã ASCII của một ký tự x là aval(x), istr(s) là tổng giá trị 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 bằng cách chia lấy phần dư istr(s) cho số ký 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 ở trên sẽ được ánh xạ vào chung một chỉ số trong bảng băm.
Bởi vì chỉ số của tất cả các chuỗi là giống nhau, nên bạn có thể tạo một danh sách liên kết với chỉ số đó để chèn các chuỗi vào.
Hình 1: Bảng băm không tối ưu
Với bảng băm ở trên, ta có thể nhận thấy rằng để truy cập vào một chuỗi trong bảng thì trong trường hợp xấu nhất ta sẽ mất thời gian là O(N). Do vậy với cách thực hiện thứ nhất ta có một hàm băm không tối ưu.
Cách thực hiện thứ 2:
Ta sẽ dùng cách khác để tính toán chỉ số cho các chuỗi, với cách này, chỉ số của một chuỗi sẽ bằng tổng mã ASCII của từng ký tự nhân với thứ tự sắp xếp của ký 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 trong 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 cho 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ì trong 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 xem 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 khi 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 ở 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ự trong 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;/* 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 khi chạy chương trình trên.
Kết luận
Bởi vì hàm băm trả về một khóa có giá trị nhỏ hơn khóa gốc (là một số nguyên lớn hoặc một chuỗi dài), điều này dẫn đến việc hai khóa có thể có chung một giá trị.
Xem thêm: Butcher Là Gì – Butcher Trong Tiếng Tiếng Việt
Tình huống khi một phần tử mới được chèn vào bảng băm có khóa ánh xạ tới một vị trí đã có dữ liệu (ánh xạ tới chung một giá trị với một khóa khác) được gọi là sự xung đột. Và chúng ta phải giải quyết vấn đề này bằng các kỹ thuật giải quyết xung đột.
Chuyên mục: Hỏi Đáp
