(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://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 E. Black.
Entry modified 13 July 2009.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "hashbelt", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 13 July 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/hashbelt.html
