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 ...)
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.
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