| Complejidad | |
|---|---|
| Find(key) → bool | O(1) |
| Insert(key, value) | O(1) |
| Get(key) → value | O(1) |
| Delete(key) → value | O(1) |
Ejemplo:
insert(“Gian”, 4) → h(“Gian”) = … % tamaño de la tabla
Obs: se trata que el largo inicial de la lista sea primo
find(“Gian”) → h(“Gian”)%k = 3 → if tabla[3] = “Gian” return true
En caso de una colisión (querer guardar en un lugar ocupado) hay dos opciones:
paso a la posición siguiente o alguna otra posición
se enlaza un nuevo nodo (formando una especie de lista)
Probing → Estrategias de dirigir los inserts en posiciones ocupadas
$H(x, i) = (H(x)+i)mod M$
i = arranca cero y va aumentando si los encuentra ocupados. arranca en posición a la que me manda el hash, y lo voy aumentando en caso de colisión