Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 12: Bảng và truy xuất thông tin

Trong chương 7 chúng ta đã thấy rằng, bằng cách so sánh khóa, trung bình việc tìm kiếm trong n phần tử không thể có ít hơn lg n lần so sánh. Nhưng kết quả này chỉ nói đến việc tìm kiếm bằng cách so sánh các khóa. Bằng một vài phương pháp khác, chúng ta có thể tổ chức các dữ liệu sao cho vị trí của một phần tử có thể được xác định nhanh hơn.

Thật vậy, chúng ta thường làm thế. Nếu chúng ta có 500 phần tử khác nhau có các khóa từ 0 đến 499, thì chúng ta sẽ không bao giờ nghĩ đến việc tìm kiếm tuần tự hoặc tìm kiếm nhị phân để xác định vị trí một phần tử. Đơn giản chúng ta chỉ lưu các phần tử này trong một mảng kích thước là 500, và sử dụng chỉ số n để xác định phần tử có khóa là n bằng cách tra cứu bình thường đối với một bảng.