betaFeedback

WorksComputer Science

A Sharp Analysis of Fixed Offset Hash Tables

Abstract

We consider the class of open addressing hash tables that uses a fixed offset sequence r0,r1,…,rn−1r_0,r_1,\ldots,r_{n-1} to find an open slot in the table. As special cases this subsumes linear probing (ri=ir_i=i) and quadratic probing (ri=i2r_i=i^2). We give a simple analysis that the expected insertion time when the load factor is 1−ε1-ε is O(ε−2)O(ε^{-2}). This bound is tight for linear probing (but not for quadratic probing), so the analysis cannot be improved at this level of generality.

Paper details

vlnc:W_knz92akz
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…