Khi phân tích cú pháp (parse) mã nguồn của người lập trình, đối với các tên dạng không gian tên gồm các thành phần cách nhau bởi dấu chấm (.), hoặc đường dẫn kiểu dữ liệu qua toán tử phạm vi (::), chương trình dịch phải thực hiện nhiều vòng xử lý. Mỗi vòng xử lý một tên thành phần, thực hiện tìm đối tượng tương ứng với xâu kí tự của tên.
Có nhiều cách tìm kiếm xâu kí tự như tuần tự, cây nhị phân, nhưng nhanh hơn cả là ánh xạ xâu kí tự vào một bảng băm.
Chúng ta xét một ví dụ
struct DATA
{
int m_i;
struct PAIR
{
Number m_n;
String m_string;
};
PAIR m_pair;
};
struct FUNC
{
::DATA::PAIR GetPair(Number n)
{
::DATA::PAIR pair;
pair.m_n = n;
return pair;
}
};
FUNC array[100];
print array[0].GetPair(5).m_n;
Cấu trúc PAIR được lồng trong cấu trúc DATA, vì vậy cấu trúc FUNC muốn sử dụng kiểu PAIR phải sử dụng toán tử phạm vi :: (::DATA::PAIR và DATA::PAIR là tương đương, Fuzzy 1.3 chỉ áp dụng toán tử phạm vi :: cho kiểu người lập trình định nghĩa).
Ở dòng mã dưới cùng, mảng array lấy phần tử thứ nhất (chỉ số 0) là một phần tử kiểu FUNC. Phần tử này gọi hàm GetPair của nó, nhận giá trị trả về là một đối tượng kiểu PAIR. Cuối cùng, dòng mã thực hiện in biến thành phần m_n của đối tượng này.
Khi mã nguồn của bạn khá lớn và cần xử lý nhiều không gian tên thì bảng băm tỏ rõ hiệu quả.
Kỹ thuật bảng băm không có gì mới nhưng áp dụng là rất khác nhau. Hàm băm mật mã là hàm băm tốt nhưng tốn chi phí tính toán. Thông thường, băm một xâu kí tự chỉ đơn giản là lần lượt cộng dồn các kí tự của xâu trong khi dịch trái kết quả đi một số bits sau mỗi bước.
Tìm kiếm trong bảng băm như thế là tuyệt đối chính xác vì nếu có hai xâu kí tự có cùng mã băm (hay chỉ số) thì chúng sẽ được so sánh để phân biệt theo cách so sánh hai xâu kí tự thông thường.
Để biết chi tiết kỹ thuật bảng băm, mời bạn xem bài Hash và chiến lược tìm kiếm.
Share on Twitter Share on Facebook Share on Linked In
Contact: tuyen@omarine.org
Comments
There are currently no comments
New Comment