On the expected longest length probe sequence for hashing with separate chaining

• Hashing is a widely used technique for data organization. Hash tables enable a fast search of the stored data and are used in a variety of applications ranging from software to network equipment and computer hardware. One of the main issues associated with hashing are collisions that cause an increase in the search time. A number of alternatives have been proposed to deal with collisions. One of them is separate chaining, in which for each hash value an independent list of the elements that have that value is stored. In this scenario, the worst case search time is given by the maximum length of that list across all hash values. This worst case is often referred to as Longest Length Probe Sequence (llps) in the literature. Approximations for the expected longest length probe sequence when the hash table is large have been proposed and an exact analytical solution has also been presented in terms of a set of recurring equations. In this paper, a novel analytical formulation of the expected longest length probe sequence is introduced. The new formulation does not require a recursive computation and can be easily implemented in a symbolic computation tool.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences (hsv//eng)

Nyckelord

Analysis of algorithms

Hashing

Separate chaining

Table search

Analytical formulation

Data organization

Exact analytical solutions

Fast search

Hash table

Hash value

Network equipment

Probe sequence

Recursive computation

Search time

Symbolic computation

Worst case

Computer hardware

Probes

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)