Robin Hood hashing really has constant average search cost and variance in full tables

MaRDI QIDQ4632496zbMATH OpenFDO

Authors Alfredo Viola

Publication date 29 April 2019

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

zbMATH Keywords

constant expected search timeconstant variancefull tablesRobin Hood hashing

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Analysis of algorithms (68W40)

Recommendations

• Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions
• A new approach to analyzing Robin Hood hashing
• On Worst-Case Robin Hood Hashing
• The effect of deletions on different insertion disciplines for hash tables
• On deletions in open addressing hashing

Cited in

(3)

• The effect of deletions on different insertion disciplines for hash tables
• On Worst-Case Robin Hood Hashing
• A new approach to analyzing Robin Hood hashing

This page was built for publication: Robin Hood hashing really has constant average search cost and variance in full tables

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