Matematicamente.it

Ciao a tutti, posto questo esercizio in quanto non riesco a capire la metodologia tramite cui si può ricavare la funzione di hashing osservandone gli effetti su di una tabella, ovvero:



L'esercizio chiede sostanzialmente una possibile funzione di hashing che potrebbe causare il comportamento riportato in figura. Ovviamente la metodologia utilizzata in tal caso per gestire le collissione è quella della concatenamento lineare, ho pensato che quindi una funzione di hashing in questo caso potrebbe essere del tipo:

$k mod m$

In cui:
- $k$ è la chiave
- $m$ potrebbe essere la dimensione della tabella, cioè 20

Tuttavia, provando a sostituire i valori per verificare se sia effettivamente questa la funzione di hashing che risolve l'esercizio i numeri che ottengo sono diversi. Ad esempio: $30 mod 20 = 10 != 0$.
Inoltre, quale potrebbe essere una funzione di hashing migliore?
Grazie per l'aiuto.

Ciao, premesso che sono argomenti che non conosco, sembra che la seguente funzione vada bene per ogni chiave:

$k%(m/2)*2$

A prima vista mi sembra sia qualcosa come \( (2 \times k) \pmod m \)