Change search
ReferencesLink to record
Permanent link

Direct link
On the expected longest length probe sequence for hashing with separate chaining
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
2011 (English)In: Journal of Discrete Algorithms, ISSN 1570-8667, Vol. 9, no 3, 307-312 p.Article in journal (Refereed) Published
Abstract [en]

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.
Keyword [en]
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
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-151153DOI: 10.1016/j.jda.2011.04.005ScopusID: 2-s2.0-79957864074OAI: diva2:747745

QC 20140917

Available from: 2014-09-17 Created: 2014-09-15 Last updated: 2015-10-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Holst, Lars
By organisation
Mathematics (Dept.)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 18 hits
ReferencesLink to record
Permanent link

Direct link