Individual Displacements in Hashing with Coalesced Chains

DOI10.1017/S0963548308009395MaRDI QIDQ3608336zbMATH OpenFDO

Authors Svante Janson

Publication date 4 March 2009

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0502232

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Abstract: We study the asymptotic distribution of the displacements in hashing with coalesced chains, for both late-insertion and early-insertion. Asymptotic formulas for means and variances follow. The method uses Poissonization and some stochastic calculus.

Recommendations

• Individual displacements for linear probing hashing with different insertion policies
• Exact distribution of individual displacements in linear probing hashing
• On probabilistic analysis of a coalesced hashing algorithm
• Asymptotic distribution for the cost of linear probing hashing
• Publication:4886028

Cites work

• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• Analysis of Early-Insertion Standard Coalesced Hashing
• Direct-chaining with coalescing lists
• Exact distribution of individual displacements in linear probing hashing
• Individual displacements for linear probing hashing with different insertion policies

Cited in

(4)

• On Search Times for Early-Insertion Coalesced Hashing
• scientific article; zbMATH DE number 910855 (Why is no real title available?)
• Deviation results for sparse tables in hashing with linear probing
• scientific article; zbMATH DE number 7525476 (Why is no real title available?)

This page was built for publication: Individual Displacements in Hashing with Coalesced Chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608336)