Individual Displacements in Hashing with Coalesced Chains

DOI10.1017/S0963548308009395zbMATH Open1168.68606arXivmath/0502232MaRDI QIDQ3608336FDOQ3608336

Authors: Svante Janson 

Publication date: 4 March 2009

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

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.

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

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

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Cites Work

• Title not available (Why is that?)
• Individual displacements for linear probing hashing with different insertion policies
• Exact distribution of individual displacements in linear probing hashing
• Direct-chaining with coalescing lists
• Analysis of Early-Insertion Standard Coalesced Hashing

Cited In (4)

• On Search Times for Early-Insertion Coalesced Hashing
• Title not available (Why is that?)
• Deviation results for sparse tables in hashing with linear probing
• Title not available (Why is that?)

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)