Premium
Near‐perfect hashing of large word sets
Author(s) -
Brain Marshall D.,
Tharp Alan L.
Publication year - 1989
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380191005
Subject(s) - word (group theory) , hash function , computer science , perfect hash function , dynamic perfect hashing , simplicity , function (biology) , algorithm , universal hashing , hash table , theoretical computer science , arithmetic , mathematics , double hashing , programming language , philosophy , geometry , epistemology , evolutionary biology , biology
Abstract This article presents a procedure for constructing a near‐perfect hashing function. The procedure, which is a modification of Cichelli's algorithm, builds the near‐perfect hashing function sufficiently fast to allow larger word sets to be used than were previously possible. The improved procedure is the result of examining the original algorithm for the causes of its sluggish performance and then modifying them. In doing so an attempt was made to preserve the basic simplicity of th original algorithm. The improved performance comes at the expense of more storage. The six modifications used to improve performance are explained in detail and experimental results are given for word sets of varying sizes.