Che cos'è il clustering primario e secondario in hash?

Question

Sono confuso per gli ultimi giorni nel trovare la differenza tra clustering primario e secondario nell'argomento di gestione delle collisioni di hash nel libro di testo che sto leggendo.

Answer 1

Il clustering primario significa che se c'è un cluster e la posizione iniziale di un nuovo record cadrà ovunque nel cluster, la dimensione del cluster aumenta. Il sondaggio lineare porta a questo tipo di clustering.

Il clustering secondario è meno grave, due record hanno solo la stessa catena di collisione se la posizione iniziale è la stessa. Ad esempio il sondaggio quadratico porta a questo tipo di clustering.

Answer 2

stavo facendo ricerche su questo e vorrei condividere alcune note:

1. clustering primario è la tendenza per uno schema di risoluzione di collisione, come la scansione lineare per creare lunghi tratti di slot pieni vicino la posizione hash dei tasti.
2. Se l'indice hash primario è x, sonde successive vanno a x+1, x+2, x+3 e così via, questo si traduce in Primaria clustering.
3. Una volta creato il cluster primario, più grande diventa il cluster, lo più veloce cresce. E riduce le prestazioni.

---

1. Clustering secondaria è la tendenza per uno schema di risoluzione di collisione come quadratica sondando per creare lunghi tratti di slot pieni via dalla posizione hash delle chiavi.
2. Se l'indice hash primario è x, le sonde vanno a x+1, x+4, x+9, x+16,x+25 e così via, questo si traduce in Clustering secondaria.
3. Il clustering secondario è meno grave in termini di prestazioni rispetto al clustering primario ed è un tentativo di impedire la formazione di cluster utilizzando Quadratic Probing. L'idea è di sondare celle più separate, invece di quelle adiacenti al sito di hash primario.