Metraipolis › archive › dc_c3efbcb8d02f

Linear probing — Wikipedia (es)

Source: Wikipedia (es)
Original: https://es.wikipedia.org/wiki/Linear_probing
License (as archived): CC-BY-SA-4.0
Archived: 2026-11-10T07:45:11.791Z
SHA-256 of the archived text: 3808e710c37e7aebb35997810da026940cb3f5be7e8a6dc1af828852774d676a
Stable URL of this page: https://metraipolis.com/documento/dc_c3efbcb8d02f

How to cite

Linear probing — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Linear_probing (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_c3efbcb8d02f (Metraipolis archive dc_c3efbcb8d02f, sha256 3808e710c37e7aebb35997810da026940cb3f5be7e8a6dc1af828852774d676a)

BibTeX

@misc{dcc3efbcb8d02f,
  title = {Linear probing — Wikipedia (es)},
  howpublished = {Wikipedia (es)},
  url = {https://es.wikipedia.org/wiki/Linear_probing},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_c3efbcb8d02f; sha256 3808e710c37e7aebb35997810da026940cb3f5be7e8a6dc1af828852774d676a},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/Linear_probing. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Linear probing es un esquema de programación informática para resolver colisiones en tablas hash, estructuras de datos para mantener una colección de pares clave-valor y buscar el valor asociado a una clave determinada. Fue inventado en 1954 por Gene Amdahl, Elaine M. McGraw y Arthur Samuel y analizado por primera vez en 1963 por Donald Knuth. Junto con el sondeo cuadrático y el hashing doble, linear probing es una forma de direccionamiento abierto. En estos esquemas, cada celda de una tabla hash almacena un único par clave-valor. Cuando la función hash provoca una colisión al asignar una nueva clave a una celda de la tabla hash que ya está ocupada por otra clave, el linear probing busca en la tabla la siguiente ubicación libre más cercana e inserta allí la nueva clave. Las búsquedas se realizan de la misma manera, buscando en la tabla secuencialmente a partir de la posición dada por la función hash, hasta encontrar una celda con una clave coincidente o una celda vacía. Como escriben Thorup y Zhang (2012), "las tablas hash son las estructuras de datos no triviales más utilizadas, y la implementación más popular en hardware estándar utiliza el linear probing, que es rápido y sencillo". El linear probing puede proporcionar un alto rendimiento debido a su buena localidad de referencia, pero es más sensible a la calidad de su función hash que otros esquemas de resolución de colisiones. Requiere un tiempo esperado constante por búsqueda, inserción o borrado cuando se implementa utilizando una función hash aleatoria, una función hash independiente de 5 o un hashing de tabulación. En la práctica, también se pueden obtener buenos resultados con otras funciones hash, como MurmurHash.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in spagnolo, in ordine alfabetico).
Fonte: Wikipedia in spagnolo, voce «Linear probing» — https://es.wikipedia.org/wiki/Linear_probing
Wikidata Q2988094: «collision resolution scheme» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q2988094
Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Linear_probing?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 166527841, consultata il 2026-11-10T07:41:12.985Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 1ad02ae220fe6b8612d98b15a082338a27861b27fe4f86725a2d2284733b3c89