An algorithm for storage and retrieval in a small dynamic cache is presented. This algorithm is based on C.C. Chang’s ordered minimal perfect hashing scheme. Our algorithm has the property that it divides the set of objects that could occupy the cache into an arbitrary number of equivalence classes. The only restriction on which objects can occupy the cache are that no two objects in the same equivalence class can be in the cache at the same time. Retrieval from the cache is performed in constant time. Update of the cache is performed in logarithmic time.
Sager, Thomas J., "A Dynamic Caching Algorithm based on C. C. Chang's Ordered Minimal Perfect Hashing Scheme" (1987). Computer Science Technical Reports. 11.
© 1987 University of Missouri--Rolla, All rights reserved.