Probabilistic behavior of hash tables

Simple item page
dc.creatorHong, Dawei
dc.creatorBirget, Jean-Camille
dc.creatorMan, Shushuang
dc.date2003-03-21
dc.date.accessioned2026-07-07T03:19:32Z
dc.date.available2026-07-07T03:19:32Z
dc.descriptionWe extend a result of Goldreich and Ron about estimating the collision probability of a hash function. Their estimate has a polynomial tail. We prove that when the load factor is greater than a certain constant, the estimator has a gaussian tail. As an application we find an estimate of an upper bound for the average search time in hashing with chaining, for a particular user (we allow the overall key distribution to be different from the key distribution of a particular user). The estimator has a gaussian tail.
dc.identifierhttps://arxiv.org/abs/cs/0303022
dc.identifierhttp://arxiv.org/abs/cs/0303022
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31499
dc.subjectData Structures and Algorithms
dc.subjectDatabases
dc.subjectE.2
dc.titleProbabilistic behavior of hash tables
dc.typetext

Files

Collections

arXiv