Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Identifiers
URN: urn:nbn:se:kth:diva-151153DOI: 10.1016/j.jda.2011.04.005Scopus ID: 2-s2.0-79957864074OAI: oai:DiVA.org:kth-151153DiVA: diva2:747745
Note

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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 26 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf