Static hashing is a form of hashing where lookups are performed on a finalized dictionary set (all objects in the dictionary are final and not changing).
Since static hashing requires that the database, its objects, and reference remain the same, its applications are limited.
Databases which contain information which changes rarely are also eligible as it would only require a full rehash of the entire database on rare occasion.
Examples of this include sets of words and definitions of specific languages, sets of significant data for an organization's personnel, etc.
elements can be stored in a hash table of equal size and can have lookups done in constant time.
It was specifically discovered and discussed by Fredman, Komlos and Szemeredi (1984) and has therefore been nicknamed "FKS hashing".
[2] FKS hashing makes use of a hash table with two levels in which the top level contains
FKS hashing requires that if collisions occur they must do so only on the top level.
The top level contains a randomly created hash function,
, which fits within the constraints of a Carter and Wegman hash function from universal hashing.
Following this pattern, all of the buckets hold a hash table of size
The hash function will be decided by setting
and randomly going through functions until there are no collisions.
pairs of elements, of which have a probability of collision equal to
, FKS hashing can expect to have strictly less than
was selected so that the number of collisions would be at most
, the size of each table on the lower level will be no greater than