Cấu trúc dữ liệu ánh xạ (còn gọi là bảng băm; tiếng Anh mapped data structure) là cấu trúc dữ liệu trong đó vị trí lưu trữ của mỗi phần tử được xác định dựa trên ánh xạ từ giá trị khóa của chính phần tử. Thông thường, địa chỉ - vị trí lưu trữ - được tạo ra dựa trên biến đổi giá trị khóa của phần tử qua một hàm băm. Kết quả băm gọi là giá trị băm của khóa. Cấu trúc dữ liệu ánh xạ thường được cài đặt dưới dạng mảng một chiều (xt. cấu trúc dữ liệu tuyến tính). Khi đó, chỉ số của phần tử trong mảng chính là giá trị băm của khóa của phần tử.
Nguyên lý[sửa]
Hàm băm biến đổi đầu vào (giá trị khóa của phần tử) có độ dài bất kỳ thành đầu ra (giá trị băm) có độ dài xác định (tính theo đơn vị bit). Giá trị băm được quy đổi thành số nhị phân không dấu và được dùng làm địa chỉ lưu trữ phần tử. Chẳng hạn, xét trường hợp đầu ra của hàm băm là chuỗi nhị phân độ dài 32 bit, mảng sẽ có tất cả 4294967296 địa chỉ phần tử được sử dụng. Trong thực tế xây dựng cấu trúc dữ liệu ánh xạ, các hàm băm cơ bản được chọn tương ứng với các phép toán cơ bản như dịch bit, đảo bit, XOR, AND, OR, MOD và phép cộng. Do đó, tốc độ tính toán của hàm băm tổ hợp rất nhanh và có thể cài đặt trên mọi cấu trúc vi xử lý phổ biến.
Cấu trúc dữ liệu ánh xạ có dạng mảng một chiều, nên các thao tác đọc, ghi và cập nhật cập được thực hiện trực tiếp vào vùng nhớ thông qua địa chỉ mảng, không phải duyệt qua các phần tử trung gian. Ưu điểm lớn nhất của cấu trúc dữ liệu ánh xạ là cho phép truy cập vào nội dung vùng nhớ một cách độc lập với độ dài khóa, đặc biệt khi lấy toàn bộ nội dung của phần tử dữ liệu làm giá trị khóa.
Cấu trúc dữ liệu ánh xạ hỗ trợ các thao tác cơ bản sau:
- Thêm phần tử
- Đọc, sửa, xóa giá trị phần tử
- Duyệt toàn bộ phần tử
- Kiểm tra sự tồn tại của phần tử
Để xây dựng hiệu quả cấu trúc dữ liệu ánh xạ, hàm băm phải bảo đảm phân bố đều trên miền giá trị đầu ra, sao cho với hai giá trị đầu vào khác nhau, đầu ra cũng khác nhau. Do đó, thao tác thêm phần tử, truy cập phần tử trong mảng được thực hiện với độ phức tạp tính toán hằng số (xt. phân tích giải thuật). Việc loại bỏ một phần tử trong mảng được thực hiện bằng cách gán cho phần tử đó một giá trị khóa đặc biệt, ký hiệu là NULL hoặc NaN.
Trường hợp nhiều giá trị khóa khác nhau cho cùng một giá trị băm sẽ dẫn đến tình huống "xung đột", nghĩa là nhiều phần tử được gán chung một địa chỉ trong mảng. Xung đột được giải quyết theo hai cách:
- Tạo danh sách móc nối: các phần tử có cùng địa chỉ được liên kết với nhau trong danh sách móc nối (xt. Cấu trúc dữ liệu tuyến tính)
- Địa chỉ mở: Nếu địa chỉ được xác định bởi hàm băm đã được sử dụng, sẽ sử dụng một hàm băm khác để tính toán địa chỉ lưu trữ cho phần tử. Quá trình này được thực hiện cho đến khi tìm được địa chỉ lưu trữ cho phần tử tại đó chưa lưu gì.
Trong trường hợp chấp nhận được, xử lý xung đột chỉ đòi hỏi thực hiện thêm một số ít thao tác tính toán hàm băm và truy cập bộ nhớ. Trong trường hợp xấu nhất, thêm một phần tử có thể phải truy cập vào tất cả các phần tử của mảng. Việc tìm ra hàm băm tốt, bảo đảm ít xảy ra xung đột khi xây dựng cấu trúc dữ liệu ánh xạ, có thể được thực hiện theo nguyên lý thử sai ngẫu nhiên, phụ thuộc vào bản chất giá trị khóa và không có nguyên tắc tổng quát.
Lịch sử[sửa]
Cấu trúc dữ liệu ánh xạ được nghiên cứu và cài đặt lần đầu tiên trong thập niên 1950 bằng ngôn ngữ Assembly chạy trên máy IBM 701. Các tiếp cận xử lý xung đột được nghiên cứu và thử nghiệm trong thập niên 1970. Các ngôn ngữ lập trình bậc cao phổ biến vào thời điểm đó không cung cấp cấu trúc dữ liệu ánh xạ như một kiểu dữ liệu được cài đặt sẵn, lập trình viên cài đặt trực tiếp, sử dụng cấu trúc dữ liệu tuyến tính.
Về sau, một số ngôn ngữ lập trình bậc cao hỗ trợ cấu trúc dữ liệu ánh xạ thông qua các cấu trúc dữ liệu có sẵn như: unorderd_map trong thư viện STL của C++, Map của Java, Dictionary của Python.
Các ngôn ngữ lập trình bậc cao phổ biến hiện nay đều cung cấp cấu trúc dữ liệu ánh xạ như một lớp, kiểu dữ liệu có sẵn, với các chi tiết cài đặt và tối ưu hóa, hoàn toàn trong suốt với lập trình viên. Cấu trúc dữ liệu ánh xạ là nội dung cơ bản trong chương trình đào tạo kỹ sư, cử nhân công nghệ thông tin và khoa học máy tính, được giảng dạy trong môn cấu trúc dữ liệu và giải thuật, môn học về ngôn ngữ lập trình như Java, Python.
Ứng dụng và phát triển[sửa]
Cấu trúc dữ liệu ánh xạ được áp dụng cho các ứng dụng cần tối ưu chi phí cho hai thao tác tìm kiếm và truy cập thông tin, ví dụ:
- Đánh chỉ mục địa chỉ trang web phục vụ tìm kiếm trên Internet
- Xây dựng cơ sở dữ liệu quản lý (thư viện, hộ khẩu, biển số xe,...)
- Lưu trữ và quản lý mật khẩu
- Xây dựng các bảng tìm kiếm hỗ trợ phát hiện các phần tử
- Tiền xử lý cho tìm kiếm dựa trên đối sánh phức tạp.
Cấu trúc dữ liệu ánh xạ có thể được phát triển theo những hướng sau:
- Xây dựng hàm băm cho phép hạn chế tối đa xung đột với các bộ dữ liệu cụ thể
- Tính toán song song trên các bộ vi xử lý đồ họa đa lõi
- Xây dựng cơ chế tìm kiếm trong cơ sở dữ liệu phân tán cỡ lớn
Tài liệu tham khảo[sửa]
- Đỗ Xuân Lôi, Cấu Trúc Dữ Liệu và Giải Thuật, Nhà xuất bản Đại Học Quốc Gia Hà Nội, In lần thứ 9, 2006
- Niclaus Wirth, Algorithms + Data structures = Programs, Prentice-Hall, Inc (1976), ISBN 0-13-022418-9
- Donald Knuth, The Art of Computer Programming, Vol.3 Sorting and Searching, Massachusetts: Addison-Wesley, Second Edition, 1998, ISBN 0-201-89685-0
