que signifie clustering (dans la collision) en hachage?

Question

Le problème principal du sondage linéaire est le regroupement, de nombreux éléments consécutifs forment des groupes et il faut du temps pour trouver un emplacement libre ou pour rechercher un élément.

Pourquoi élément consécutif du groupe & comment il affecte le temps de trouver slot libre?

Answer 1

La sortie voulait de la fonction de hachage est de disperser SAY 100 chaînes à plus de dire au hasard 200 « pigeonslots ». En cas de collision, c'est-à-dire de fente déjà occupée, le balayage linéaire va chercher l'emplacement inoccupé suivant, faisant immédiatement un groupe d'au moins deux (il peut également connecter deux groupes). Lorsqu'il y a une collision avec un cluster, le sondage linéaire ajoute le cluster par une nouvelle clé, dont la position d'origine aurait dû être n'importe où dans le cluster.

Beaucoup rapide pour évaluer les fonctions de hachage souffrent du problème de ne pas distribuer les clés de façon uniforme. Lorsque les données d'entrée ne sont pas distribuées uniformément, ces deux phénomènes se renforcent mutuellement et, en cas de sondage linéaire, peuvent conduire à une quantité importante de clés à graver. En effet, cela fera non seulement de l'insertion mais aussi de la recherche d'un problème O (n) au lieu de O (1).

Answer 2

Ce n'est pas le cas où les éléments consécutifs formeront des clusters.

exemple Condictory

Supposons que vous ayez une table de hachage de 100 entrées: et la fonction de hachage est:

h(x) = x mod 100; 

Dites que vous insérez des éléments:

948,748,172,973,473,572,72 

Les groupes formés sera:

groupe 1: 948(position 48),748(position 49) (clairement les éléments ne sont pas consécutifs)

groupe 2: 172(position 72),973(position 73),473(position 74),572(position 75),72(position 76) (clairement des éléments non consécutifs).

OUI, le regroupement affecte le temps de trouver un emplacement libre, parce que dans linear probing, nous parcourons la table de hachage pour trouver la fente libre suivante, donc en raison de clusters, balayage linéaire prendra plus de temps en raison de groupes formés , mais sa seule raison de balayage linéaire en cas de collision .