english Icono del idioma   español Icono del idioma  

  1. Colibri
  2. Facultad de Ingeniería
  3. Instituto de Computación
  4. Reportes Técnicos
Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12008/3481 How to cite
Full metadata record
DC FieldValueLanguage
dc.contributor.authorDevroye, Luces
dc.contributor.authorMorin, Pates
dc.contributor.authorViola, Alfredoes
dc.date.accessioned2014-12-02T16:06:42Z-
dc.date.available2014-12-02T16:06:42Z-
dc.date.issued2002es
dc.date.submitted20141202es
dc.identifier.citationDEVROYE, L., MORIN, P., VIOLA, A. "On Worst Case Robin-Hood Hashing". Reportes Técnicos 02-12. UR. FI – INCO, 2002.es
dc.identifier.issn0797-6410es
dc.identifier.urihttp://hdl.handle.net/20.500.12008/3481-
dc.description.abstractWe consider open addressing hashing, and implement it by using the Robin Hood strategy, that is, in case of collision, the element that has traveled the furthest can stay in the slot. We hash elements into a table of size n where each probe is independent and uniformly distributed over the table, and [ 1 is a constant. Let Mn be the maximum search time for any of the elements in the table. We show that with probability tending to one, Mn E [kig2 logn + s, log2 logn + T] for some constants s, T depending upon alfa only. Tis is an exponential improvement over the maximum search time in case of the standard FCFS (first come first served) collision strategy, and virtually matches the performance of multiple choice hash methods.es
dc.format.extent18 p.es
dc.format.mimetypeapplication/pdfes
dc.languageines
dc.publisherUR. FI – INCO.es
dc.relation.ispartofReportes Técnicos 02-12es
dc.rightsLas obras depositadas en el Repositorio se rigen por la Ordenanza de los Derechos de la Propiedad Intelectual de la Universidad De La República. (Res. Nº 91 de C.D.C. de 8/III/1994 – D.O. 7/IV/1994) y por la Ordenanza del Repositorio Abierto de la Universidad de la República (Res. Nº 16 de C.D.C. de 07/10/2014)es
dc.subjectOPEN ADRESSINGes
dc.subjectHASHINGes
dc.subjectROBIN HOODes
dc.subjectWORST-CASE SEARCH TIMEes
dc.subjectCOLLISION RESOLUTIONes
dc.subjectPROBABILISTIC ANALYSIS OF ALGORITHMSes
dc.titleOn Worst Case Robin-Hood Hashinges
dc.typeReporte técnicoes
dc.rights.licenceLicencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0)es
Appears in Collections:Reportes Técnicos - Instituto de Computación

Files in This Item:
File Description SizeFormat  
TR0212.pdf168,68 kBAdobe PDFView/Open
Show simple item record


This item is licensed under a Creative Commons License Creative Commons