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