| Mejor | Amortizado | Peor | |
|---|---|---|---|
| find | O(1) | O(1) | O(n) |
| insert | O(1) | O(1) | O(n) |
| get | O(1) | O(1) | O(n) |
| delete | O(1) | O(1) | O(n) |
Queremos que todo sea O(1) (en el peor caso)
Dos técnicas de hashing:
h(x) → num
K: tamaño del vecindario
Vecindario: los k números después de mi (además de mi), que también hashean al mismo número
Ejemplo k = 3, n = 8
Así el find se vuelve O(k) en el peor caso, porque me fijo en el valor del hash y en su vecindario
Al final me queda
| 0 | A | 100 |
|---|---|---|
| 1 | D | 000 |
| 2 | 000 | |
| 3 | F | 101 |
| 4 | C | 101 |
| 5 | G | 000 |
| 6 | E | 000 |
| 7 | B | 101 |
Si ahora quiero insertar H en 6, como el único vacío es el 2, muevo A al 2 e inserto H en 0
| 0 | H | 001 |
|---|---|---|
| 1 | D | 000 |
| 2 | A | 000 |
| 3 | F | 101 |
| 4 | C | 101 |
| 5 | G | 000 |
| 6 | E | 000 |
| 7 | B | 101 |