Topic: perfect hash table

topics > computer science > information > Group: information retrieval

search algorithms
hash table and hash functions


A perfect hash table has one element per hash slot. A perfect hash function maps a set of elements to unique values. (cbb 11/07)
Subtopic: perfect hashing up

Quote: single disk access by perfect hashing; very small internal table; most insertions fast, some require a local reorganization [»ramaMV6_1989]
Quote: a composite perfect hashing scheme uses perfect hashing after a normal hash identifies a segment [»ramaMV6_1989]
Quote: FKS perfect hashing is an efficient variation of Fredman et. al's algorithm; within 2x of linear probing [»silvC_2002]

Subtopic: perfect hash function up

Quote: mod_p is a space-efficient, perfect hash for n up to 30; useful for extensible records with links to a type header [»remyD6_1992]
Quote: interactive system to find a perfect hash function; user selects letter positions/key length that form hash key [»cercN11_1985]
Quote: perfect hashing functions are easier to find if buckets are large
Quote: Chichelli's algorithm for perfect hash functions degenerates quickly if more than 50 keys [»cercN11_1985]
Quote: order-preserving minimal perfect hash functions for relatively static collections; construct in linear time and space [»foxEA7_1991]
Quote: floor(C/Dw+E) mod n is a minimal perfect hash function of any set of n w's

Related Topics up

Topic: search algorithms (40 items)
Topic: hash table and hash functions
(41 items)

Updated barberCB 10/04
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.