Direct address table là gì?

Bảng địa chỉ trực tiếp (direct address table) là một cấu trúc dữ liệu (data structure) có khả năng ánh xạ (map) các bản ghi (record) tới các khóa (key) tương ứng của chúng bằng cách sử dụng mảng (array). Trong bảng địa chỉ trực tiếp (direct address table), các bản ghi được đặt bằng cách sử dụng các giá trị khóa của chúng trực tiếp dưới dạng chỉ số (index). Chúng hỗ trợ các thao tác tìm kiếm, chèn và xóa nhanh chóng.

Chúng ta có thể hiểu khái niệm này bằng cách sử dụng ví dụ sau. Chúng ta tạo một mảng có kích thước bằng giá trị lớn nhất cộng với một (giả sử là chỉ số dựa trên 0) và sau đó sử dụng các giá trị làm chỉ số. Ví dụ trong sơ đồ sau, khóa 21 được sử dụng trực tiếp làm chỉ số.

Ưu điểm

• Tìm kiếm với độ phức tạp thời gian O(1): Bảng địa chỉ trực tiếp (direct address table) sử dụng mảng là cấu trúc dữ liệu truy cập ngẫu nhiên, do đó, các giá trị khóa (cũng là chỉ số của mảng) có thể dễ dàng được sử dụng để tìm kiếm các bản ghi trong độ phức tạp O(1).
• Chèn với độ phức tạp thời gian trong O(1): Chúng ta có thể dễ dàng chèn một phần tử (element) trong mảng với độ phức tạp thời gian O(1). Điều tương tự cũng xảy ra trong bảng địa chỉ trực tiếp (direct address table).
• Xóa với độ phức tạp thời gian O(1: Việc xóa một phần tử mất O(1) trong một mảng. Tương tự, để xóa một phần tử trong bảng địa chỉ trực tiếp (direct address table), chúng ta mất O (1).

Nhược điểm

• Kiến thức trước về giá trị khóa tối đa.
• Thực tế chỉ hữu ích nếu giá trị lớn nhất rất nhỏ.
• Nó gây lãng phí không gian bộ nhớ (memory space) nếu có sự khác biệt đáng kể giữa tổng số bản ghi và giá trị lớn nhất.