Sprugnoli R. Pseudo hash tables. Internal note IEI-B75-13, 1975. |

Abstract (English) |
This paper is devoted to a refiniment of hashing, allowing to retrieve and identifier in a static table by a single probe. Given a set I of identifiers, we present two methods to build, in a mechanical way, pseudo-hash functions, i.e. functions transforming the elements of I into unique addresses. The first method, the "quotient reduction" method, is shown to be complete, i.e for every set I we can find the smallest table, in which the elements of I can stored and from which they can be retrieved by a pseudo-hash function constructed by our method. However, for odd distributed sets, this method can give rather sparse tables. The second methods, the "remainder reduction" method, is not complete in the above sense, but it seems to give full (or almost full) tables for every kinds of sets. Presently, the two techniques are applicable directly to very small sets, so we have develloped some methods to extend our results to larger tables This approach to searching has a strong theoretical interest;however,we give a rough comparison with hashing, showing that our method can be used conveniently in several practical applications. | |

Subject | hashing methods hash coding direct addressing |

1) Download Document PDF |

Open access Restricted Private