On the expected longest length probe sequence for hashing with separate chaining
2011 (English)In: Journal of Discrete Algorithms, ISSN 1570-8667, Vol. 9, no 3, 307-312 p.Article in journal (Refereed) Published
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.
Place, publisher, year, edition, pages
2011. Vol. 9, no 3, 307-312 p.
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
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-151153DOI: 10.1016/j.jda.2011.04.005ScopusID: 2-s2.0-79957864074OAI: oai:DiVA.org:kth-151153DiVA: diva2:747745
QC 201409172014-09-172014-09-152015-10-12Bibliographically approved