On Worst Case Robin-Hood Hashing

Por favor, use este identificador para citar o enlazar este ítem: https://hdl.handle.net/20.500.12008/3481 Cómo citar

Registro completo de metadatos

Campo DC	Valor	Lengua/Idioma
dc.contributor.author	Devroye, Luc	es
dc.contributor.author	Morin, Pat	es
dc.contributor.author	Viola, Alfredo	es
dc.date.accessioned	2014-12-02T16:06:42Z	-
dc.date.available	2014-12-02T16:06:42Z	-
dc.date.issued	2002	es
dc.date.submitted	20141202	es
dc.identifier.citation	DEVROYE, L., MORIN, P., VIOLA, A. "On Worst Case Robin-Hood Hashing". Reportes Técnicos 02-12. UR. FI – INCO, 2002.	es
dc.identifier.issn	0797-6410	es
dc.identifier.uri	http://hdl.handle.net/20.500.12008/3481	-
dc.description.abstract	We 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.extent	18 p.	es
dc.format.mimetype	application/pdf	es
dc.language	in	es
dc.publisher	UR. FI – INCO.	es
dc.relation.ispartof	Reportes Técnicos 02-12	es
dc.rights	Las 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.subject	OPEN ADRESSING	es
dc.subject	HASHING	es
dc.subject	ROBIN HOOD	es
dc.subject	WORST-CASE SEARCH TIME	es
dc.subject	COLLISION RESOLUTION	es
dc.subject	PROBABILISTIC ANALYSIS OF ALGORITHMS	es
dc.title	On Worst Case Robin-Hood Hashing	es
dc.type	Reporte técnico	es
dc.rights.licence	Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0)	es
Aparece en las colecciones:	Reportes Técnicos - Instituto de Computación

Ficheros en este ítem:

Fichero	Descripción	Tamaño	Formato
TR0212.pdf		168,68 kB	Adobe PDF	Visualizar/Abrir

Mostrar el registro sencillo del ítem

Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons