Esercizio: Hash Table

Messaggioda Walter97lor » 26/05/2020, 15:58

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:

Immagine


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.
Walter97lor
Junior Member
Junior Member
 
Messaggio: 105 di 105
Iscritto il: 07/03/2016, 21:26

Re: Esercizio: Hash Table

Messaggioda Super Squirrel » 27/05/2020, 10:27

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

$k%(m/2)*2$
Super Squirrel
Junior Member
Junior Member
 
Messaggio: 403 di 418
Iscritto il: 16/05/2013, 22:05

Re: Esercizio: Hash Table

Messaggioda apatriarca » 29/05/2020, 23:41

A prima vista mi sembra sia qualcosa come \( (2 \times k) \pmod m \)
apatriarca
Moderatore
Moderatore
 
Messaggio: 5419 di 5455
Iscritto il: 08/12/2008, 20:37
Località: Londra


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 42 ospiti