Linear probing là gì?

Dò tuyến tính (linear probing) là một phương pháp để giải quyết xung đột băm (collision) trong bảng băm (hash table), dò tuyến tính (linear probing) là một dạng của địa chỉ mở (open addressing). Trong phương pháp này khi hàm băm (hash function) gây ra xung đột bằng cách ánh xạ (map) một khóa (key) mới đến một slot của bảng băm đã bị chiếm bởi một khóa khác, tính năng thăm dò tuyến tính (linear probing) sẽ tìm kiếm vị trí trống gần nhất sau đó và chèn khóa mới vào đó. Việc tìm kiếm được thực hiện theo cách tuần tự, bằng cách tìm kiếm tuần tự bắt đầu từ slot được cung cấp bởi hàm băm, cho đến khi tìm thấy slot có khóa khớp hoặc slot trống.