Есть таблица (маршрутизации, но это не важно) в ней максимум несколько сотен записей, часть из них используются часто, часть - редко. При добавлении новой записи нужно выкинуть самую редко используемую и на ее место вставить новую.

Помогите придумать простой алгоритм не основанный на таймерах, а только на факте использования записи. Абсолютная точность не нужна, достаточно чтобы записи, которые используются часто не затирались.

Ресурсы ограничены, поэтому на каждую запись желательно потратить не более одного байта под это дело. Применение связанных списков и прочих сложных структур данных тоже отпадает.