Admin: Created page with "The best currently known minimal perfect hashing schemes can be represented using less than 2.1 bits per key if given enough time. ===Order preservation=== A minimal perfect..."

2019-03-23T07:34:53Z

Created page with "The best currently known minimal perfect hashing schemes can be represented using less than 2.1 bits per key if given enough time. ===Order preservation=== A minimal perfect..."

New page

The best currently known minimal perfect hashing schemes can be represented using less than 2.1 bits per key if given enough time.

===Order preservation===
A minimal perfect hash function is ''order preserving'' if keys are given in some order and for any keys and , implies . In this case, the function value is just the position of each key in the sorted ordering of all of the keys. A simple implementation of order-preserving minimal perfect hash functions with constant access time is to use an (ordinary) perfect hash function or [[cuckoo hashing]] to store a lookup table of the positions of each key. If the keys to be hashed are themselves stored in a sorted array, it is possible to store a small number of additional bits per key in a data structure that can be used to compute hash values quickly. Order-preserving minimal perfect hash functions require necessarily bits to be represented.

==Related constructions==
A simple alternative to perfect hashing, which also allows dynamic updates, is [[cuckoo hashing]]. This scheme maps keys to two or more locations within a range (unlike perfect hashing which maps each key to a single location) but does so in such a way that the keys can be assigned one-to-one to locations to which they have been mapped. Lookups with this scheme are slower, because multiple locations must be checked, but nevertheless take constant worst-case time.

==Source==
[http://wikipedia.org/ http://wikipedia.org/]

[[Category:Cryptography]]

Perfect hash function - Revision history

Admin: Created page with "The best currently known minimal perfect hashing schemes can be represented using less than 2.1 bits per key if given enough time. ===Order preservation=== A minimal perfect..."