La cerca hashing és un mètode d’accés i recuperació de dades basat en una funció de dispersió (hash function). Aquesta funció transforma la clau de cerca (com un identificador o un NIF) en un valor numèric que apunta directament a una posició dins d’una taula hash.
- El temps mitjà de cerca és O(1), és a dir, constant.
- Si dues claus diferents generen el mateix hash (col·lisió), es resol amb tècniques com llistes enllaçades, open addressing o rehashing.
En el context de Bases de Dades Relacionals
- Alguns SGBD permeten crear índexs hash (per exemple, PostgreSQL).
- Són especialment útils en consultes d’igualtat (
WHERE id = 1500), ja que la funció hash condueix directament a la posició esperada. - Limitació: no conserven l’ordre dels valors, per això no són eficients en cerques per intervals (
BETWEEN,>,<) ni per operacions d’ordenació. - A la pràctica, molts motors de BDD prefereixen els índexs B-Tree, que combinen eficiència i flexibilitat.
Exemple senzill
Tenim la clau: NIF = "12345678A".
- La funció hash calcula:
hash("12345678A") = 42 - La cerca va directament a la posició 42 de la taula hash.
- Si el registre hi és → s’ha trobat ✔
- Si hi ha col·lisió (p. ex.
hash("98765432B") = 42), cal una estratègia de resolució.
Comparació amb la cerca dicotòmica
| Característica | Cerca dicotòmica (B-Tree) | Cerca hashing |
|---|---|---|
| Complexitat mitjana | O(log n) | O(1) |
| Necessita dades ordenades | ✔ Sí | ✘ No |
| Cerca per intervals | ✔ Eficaç | ✘ Ineficaç |
| Consultes d’igualtat | Bona | Excel·lent |
| Ús habitual a BDD | Índex B-Tree (per defecte) | Índex hash (casos concrets) |
