Static hashing

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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).

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).

Application

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.

Perfect hashing

Perfect hashing is a model of hashing in which any set of n 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".

FKS hashing

FKS hashing makes use of a hash table with two levels in which the top level contains n buckets which each contain their own hash table. FKS hashing requires that if collisions occur they must do so only on the top level.

Implementation

The top level contains a randomly created hash function, h(x) , which fits within the constraints of a Carter and Wegman hash function from universal hashing. Having done so the top level shall contain n buckets labeled k_1, k_2, k_3, ..., k_n . Following this pattern, all of the buckets hold a hash table of size s_i and a respective hash function h_i(x) . The hash function will be decided by setting s_i to k_i^2 and randomly going through functions until there are no collisions. This can be done in constant time.

Performance

Because there are n \choose 2 pairs of elements, of which have a probability of collision equal to 1/n , FKS hashing can expect to have strictly less than n/2 collisions. Based on this fact and that each h(x) was selected so that the number of collisions would be at most n/2 , the size of each table on the lower level will be no greater than 2n .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1327998911 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001327998911 · captured 1765957703.0 · version history

Cite this page as: encyclopegia.org, “Static hashing”, snapshot enwiki-001327998911. https://encyclopegia.org/a/static-hashing

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.