An ordered minimal perfect hashing scheme based upon Euler's theorem (Q1060014): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 00:48, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An ordered minimal perfect hashing scheme based upon Euler's theorem |
scientific article |
Statements
An ordered minimal perfect hashing scheme based upon Euler's theorem (English)
0 references
1984
0 references
A hashing function is a function h on a key set \(K=\{k_ 1,k_ 1,...,k_ n\}\) into the set \(\{\) 1,2,3,...,m\(\}\) of locations. A hashing function can hence be considered as a mapping of a given set of records into a set of addresses. If no collisions occur and the mapping is into unique addresses a single probe is sufficient to retrieve each record. Such a transformation is called a perfect hashing function. If the cardinality of the set of records is equal to the cardinality of the address space a perfect hashing function is called a minimal perfect hashing function. As such hashing functions avoid collisions of keys and do not waste memory locations their study is of considerable importance. The author proposes a hashing scheme based upon Fermat's number and Euler's theorem. This hashing function stores the records in order. Furthermore it is shown that the proposed hashing scheme is a minimal perfect hashing scheme.
0 references
searching
0 references
hashing function
0 references
perfect hashing
0 references
address space
0 references