The Reconstruction and Optimization of Trie Hashing Functions
Leen Torenvliet, Peter van Emde Boas · Very Large Data Bases · 1983
We propose an adaptation to the trie hashing algorithm published by W. Litwin in 1980. This adaptation extends the algorithm so that it will save necessary information on secondary storage to reconstruct the hashing function after loss of information (E.G., system crash or termination of a find/insert program). An algorithm is given to reconstruct the trie from the information saved, and another for optimizing the reconstructed trie. A mathematical analysis of the trie data structure is given, making visible the essential structural properties of these tries; based on this analysis correctness of the algorithms presented can be established.