(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. Available at http://www.onjava.com/pub/a/onjava/2002/01/30/dataexp2.html (Accessed 3 Dec 2007).
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 22 August 2013.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "hashbelt", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 22 August 2013. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/hashbelt.html