English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Thirty years ago, the Robin Hood collision resolution strategy was introducedfor open addressing hash tables, and a recurrence equation was found for thedistribution of its search cost. Although this recurrence could not be solvedanalytically, it allowed for numerical computations that, remarkably, suggestedthat the variance of the search cost approached a value of $1.883$ when thetable was full. Furthermore, by using a non-standard mean-centered searchalgorithm, this would imply that searches could be performed in expectedconstant time even in a full table.  In spite of the time elapsed since these observations were made, no progresshas been made in proving them. In this paper we introduce a technique to workaround the intractability of the recurrence equation by solving instead anassociated differential equation. While this does not provide an exactsolution, it is sufficiently powerful to prove a bound for the variance, andthus obtain a proof that the variance of Robin Hood is bounded by a smallconstant for load factors arbitrarily close to 1. As a corollary, this provesthat the mean-centered search algorithm runs in expected constant time.  We also use this technique to study the performance of Robin Hood hash tablesunder a long sequence of insertions and deletions, where deletions areimplemented by marking elements as deleted. We prove that, in this case, thevariance is bounded by $1/(1-\alpha)+O(1)$, where $\alpha$ is the load factor.  To model the behavior of these hash tables, we use a unified approach thatcan be applied also to study the First-Come-First-Served andLast-Come-First-Served collision resolution disciplines, both with and withoutdeletions.

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