{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T22:45:39Z","timestamp":1648766739580},"reference-count":21,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2013,1,24]],"date-time":"2013-01-24T00:00:00Z","timestamp":1358985600000},"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":[[2013,5]]},"abstract":"<jats:p>In this paper we study the maximum displacement for linear probing hashing. We use the standard probabilistic model together with the insertion policy known as First-Come-(First-Served). The results are of asymptotic nature and focus on dense hash tables. That is, the number of occupied cells<jats:italic>n<\/jats:italic>and the size of the hash table<jats:italic>m<\/jats:italic>tend to infinity with ratio<jats:italic>n\/m<\/jats:italic>\u2192 1. We present distributions and moments for the size of the maximum displacement, as well as for the number of items with displacement larger than some critical value. This is done via process convergence of the (appropriately normalized) length of the largest block of consecutive occupied cells, when the total number of occupied cells<jats:italic>n<\/jats:italic>varies.<\/jats:p>","DOI":"10.1017\/s0963548312000582","type":"journal-article","created":{"date-parts":[[2013,1,24]],"date-time":"2013-01-24T12:43:47Z","timestamp":1359031427000},"page":"455-476","source":"Crossref","is-referenced-by-count":0,"title":["The Maximum Displacement for Linear Probing Hashing"],"prefix":"10.1017","volume":"22","author":[{"given":"NICLAS","family":"PETERSSON","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2013,1,24]]},"reference":[{"key":"S0963548312000582_ref4","doi-asserted-by":"crossref","first-page":"1755","DOI":"10.1214\/aop\/1015345771","article-title":"A Vervaat-like path transformation for the reflected Brownian bridge conditioned on its local time at 0.","volume":"29","author":"Chassaing","year":"2001","journal-title":"Ann. Probab."},{"key":"S0963548312000582_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90015-X"},{"key":"S0963548312000582_ref16","volume-title":"Sorting and Searching","author":"Knuth","year":"1998"},{"key":"S0963548312000582_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316962"},{"key":"S0963548312000582_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90014-X"},{"key":"S0963548312000582_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/0471715816"},{"key":"S0963548312000582_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10039"},{"key":"S0963548312000582_ref11","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103964"},{"key":"S0963548312000582_ref20","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<221::AID-RSA12>3.0.CO;2-B"},{"key":"S0963548312000582_ref12","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1245676109"},{"key":"S0963548312000582_ref10","doi-asserted-by":"publisher","DOI":"10.1145\/322248.322254"},{"key":"S0963548312000582_ref6","doi-asserted-by":"crossref","first-page":"#R14","DOI":"10.37236\/1558","article-title":"Parking functions, empirical processes, and the width of rooted labeled trees","volume":"8","author":"Chassaing","year":"2001","journal-title":"Electron. J. Combin."},{"key":"S0963548312000582_ref21","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103965"},{"key":"S0963548312000582_ref8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403372"},{"key":"S0963548312000582_ref17","doi-asserted-by":"crossref","DOI":"10.1515\/9783110941975","volume-title":"Random Forests","author":"Pavlov","year":"2000"},{"key":"S0963548312000582_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009236"},{"key":"S0963548312000582_ref1","volume-title":"Poisson Approximation","author":"Barbour","year":"2003"},{"key":"S0963548312000582_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-4015-8"},{"key":"S0963548312000582_ref3","first-page":"281","volume-title":"26th Annual Symposium on Foundations of Computer Science","author":"Celis","year":"1985"},{"key":"S0963548312000582_ref18","doi-asserted-by":"crossref","first-page":"1091","DOI":"10.1214\/aoap\/1035463325","article-title":"On the distribution of Brownian areas.","volume":"6","author":"Perman","year":"1996","journal-title":"Ann. Appl. Probab."},{"key":"S0963548312000582_ref15","volume-title":"Brownian Motion and Stochastic Calculus","author":"Karatzas","year":"2004"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548312000582","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,21]],"date-time":"2020-07-21T04:40:24Z","timestamp":1595306424000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548312000582\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,24]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["S0963548312000582"],"URL":"https:\/\/doi.org\/10.1017\/s0963548312000582","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1,24]]}}}