{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T19:48:41Z","timestamp":1766087321621},"reference-count":17,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2018,8,14]],"date-time":"2018-08-14T00:00:00Z","timestamp":1534204800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,7]]},"abstract":"<jats:p>Thirty years ago, the Robin Hood collision resolution strategy was introduced for open addressing hash tables, and a recurrence equation was found for the distribution of its search cost. Although this recurrence could not be solved analytically, it allowed for numerical computations that, remarkably, suggested that the variance of the search cost approached a value of 1.883 when the table was full. Furthermore, by using a non-standard mean-centred search algorithm, this would imply that searches could be performed in expected constant time even in a full table.<\/jats:p><jats:p>In spite of the time elapsed since these observations were made, no progress has been made in proving them. In this paper we introduce a technique to work around the intractability of the recurrence equation by solving instead an associated differential equation. While this does not provide an exact solution, it is sufficiently powerful to prove a bound of \u03c0<jats:sup>2<\/jats:sup>\/3 for the variance, and thus obtain a proof that the variance of Robin Hood is bounded by a small constant for load factors arbitrarily close to 1. As a corollary, this proves that the mean-centred search algorithm runs in expected constant time.<\/jats:p><jats:p>We also use this technique to study the performance of Robin Hood hash tables under a long sequence of insertions and deletions, where deletions are implemented by marking elements as <jats:italic>deleted<\/jats:italic>. We prove that, in this case, the variance is bounded by 1\/(1\u2212\u03b1), where \u03b1 is the load factor.<\/jats:p><jats:p>To model the behaviour of these hash tables, we use a unified approach that we apply also to study the First-Come-First-Served and Last-Come-First-Served collision resolution disciplines, both with and without deletions.<\/jats:p>","DOI":"10.1017\/s0963548318000408","type":"journal-article","created":{"date-parts":[[2018,8,14]],"date-time":"2018-08-14T08:14:31Z","timestamp":1534234471000},"page":"600-617","source":"Crossref","is-referenced-by-count":1,"title":["Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions"],"prefix":"10.1017","volume":"28","author":[{"given":"P. V.","family":"POBLETE","sequence":"first","affiliation":[]},{"given":"A.","family":"VIOLA","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,8,14]]},"reference":[{"key":"S0963548318000408_ref3","author":"Balakrishnan","year":"2013","journal-title":"Handbook of the Logistic Distribution"},{"key":"S0963548318000408_ref10","doi-asserted-by":"publisher","DOI":"10.1137\/0208038"},{"key":"S0963548318000408_ref5","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","article-title":"Universal classes of hash functions","volume":"18","author":"Carter","year":"1979","journal-title":"J. Comput. Syst. Sci."},{"key":"S0963548318000408_ref14","unstructured":"Mitzenmacher M. (2014) A new approach to analyzing Robin Hood hashing. arXiv:1401.7616"},{"key":"S0963548318000408_ref1","author":"Abramowitz","year":"1964","journal-title":"Handbook of Mathematical Functions: With Formulas, Graphs, and Mathematical Tables"},{"key":"S0963548318000408_ref11","volume-title":"The Analysis of Hashing Algorithms","author":"Guibas","year":"1976"},{"key":"S0963548318000408_ref16","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/0196-6774(89)90014-X","article-title":"Last-Come-First-Served hashing","volume":"10","author":"Poblete","year":"1989","journal-title":"J. Algorithms"},{"key":"S0963548318000408_ref2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/17.2.135"},{"key":"S0963548318000408_ref4","first-page":"105","article-title":"Reducing the retrieval time of scatter storage techniques","volume":"16","author":"Brent","year":"1973","journal-title":"Comm. Assoc. Comput. Mach."},{"key":"S0963548318000408_ref6","author":"Celis","year":"1986"},{"key":"S0963548318000408_ref7","doi-asserted-by":"crossref","unstructured":"Celis P. , Larson P.-A. and Munro J. (1985) Robin Hood hashing. In 26th IEEE Symposium on the Foundations of Computer Science, IEEE, pp. 281\u2013288.","DOI":"10.1109\/SFCS.1985.48"},{"key":"S0963548318000408_ref9","volume-title":"An Introduction to Probability Theory and Its Applications","author":"Feller","year":"1968"},{"key":"S0963548318000408_ref12","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1145\/322092.322096","article-title":"The analysis of hashing techniques that exhibit k-ary clustering","volume":"25","author":"Guibas","year":"1978","journal-title":"J. Assoc. Comput. Mach."},{"key":"S0963548318000408_ref13","volume-title":"The Art of Computer Programming","author":"Knuth","year":"1998"},{"key":"S0963548318000408_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0653(04)00246-X"},{"key":"S0963548318000408_ref15","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1137\/060658400","article-title":"Uniform hashing in constant time and optimal space","volume":"38","author":"Pagh","year":"2008","journal-title":"SIAM J. Comput"},{"key":"S0963548318000408_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-19487-8_12"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000408","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,25]],"date-time":"2019-07-25T09:19:47Z","timestamp":1564046387000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000408\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,14]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["S0963548318000408"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000408","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,14]]}}}