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://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 Wed Mar 13 12:42:46 2019.
Cite this as:
Paul E. Black, "hashbelt", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 22 August 2013. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/hashbelt.html