Aide sur les tables de hachage et le sondage quadratique en Java

Question

J'ai vraiment besoin d'aide pour l'insertion dans une table de hachage. Je ne comprends tout simplement pas tout de suite. Quelqu'un pourrait-il expliquer le sondage quadratique et linéaire en termes simples?

public void insert(String key) 
{ 
    int homeLocation = 0; 
    int location = 0; 
    int count = 0; 

    if (find(key).getLocation() == -1) // make sure key is not already in the table 
    { 
     //****** ADD YOUR CODE HERE FOR QUADRATIC PROBING ******** 
    } 
} 

Ceci est le code sur lequel je travaille. Je ne demande à personne de le faire, j'ai juste vraiment besoin d'aide pour apprendre le concept entier

Toute aide serait grandement appréciée.

Answer 1

d'abord, nous parlons d'un adressage ouvert (ou fermé hachant) approche. Vous devez gérer les collisions en calculant un nouveau code de hachage si le précédent est déjà utilisé par un autre, car tout seau de hashamap peut contenir au plus 1 élément.

Vous avez donc une fonction de hachage avec deux paramètres:

• v, la valeur de l'objet utilisé pour calculer hashcode.
• t, il est i*f où i, appelé StepSize, est ce que vous ajoutez à chaque fois que vous fonction de hachage si une collision se produit et f est le nombre de collisions atteint jusqu'à présent.

A partir de cela, vous avez deux fonctions possibles:

H(v, t) = (H(v) + t) % n 
H(v, t) = (H(v) + c*t + d*t*t) % n 

La première est une fonction linéaire, tandis que le second est un quadratique un (ici il vient le nom de cette tecnique). où vous devriez savoir ce que % n est, c et d sont des constantes choisies pour avoir un meilleur hashfunction ..

En pratique pour linéaire de sondage:

• vous caculate H(x, 0)
• • si la cellule est un lieu libre l'élément il
• • si la cellule est occupée calculate H(x, i)
• • • si la cellule est l'élément place libre dans la nouvelle adresse
• • • si la cellule est occupée alors calculer H(x, i+i)
• • • • continuer jusqu'à ce que vous trouviez une cellule vide

pour le sondage du second degré ce que vous faites est identique, vous commencez à partir H(x,0), puis H(x,i) puis H(x,i+i), ce qui diffère est la fonction de hachage impliquée qui donnera un poids différent à la taille du pas.