(data structure)
Definition: Use a short list or array of hash tables to implement a hash table with aging to expire items. To expire items, add a new table at the head of the list and drop the oldest table, along with its contents. To find an item, search all the tables.
Generalization (I am a kind of ...)
hash table.
See also move-to-front heuristic, priority queue.
Note: "The name is a combination of 'hashmap' and 'conveyor belt.'"
This data structure may be used for a least recently used (LRU) cache: move an item to the newest table when it is used. Other policies may be implemented by moving items according to other criteria.
Author: PEB
William Grosso, The Hashbelt Data Structure, O'Reilly ONJava.com, 9 January 2002.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 6 May 2019.
HTML page formatted Mon May 6 10:22:33 2019.
Cite this as:
Paul E. Black, "hashbelt", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 6 May 2019. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/hashbelt.html