Tables de hachage et traitement des collisions

Question

Supposons qu'une table de hachage soit représentée par un tableau de taille 7. Nous souhaitons stocker des chaînes composées de trois chiffres. La clé de hachage primaire est la valeur numérique du second chiffre modulo 7. La clé de hachage secondaire est la valeur numérique du troisième chiffre modulo 4 augmenté d'une unité. Insérez les chaînes suivantes dans la table de hachage initialement vide: "111", "222", "737", "323" et "234".

Ma réponse:

• 0 - 234
• 1-111
• 2-222
• 3-737
• 4-323
• 5-

• 6 -

• 111; 1 mod 7 = 1

• 222; 2 mod 7 = 2
• 737; 3 mod 7 = 3
• 323; 3 mod 4 + 1 = 4
• 234; 4 mod 4 + 1 = 4 (0)

est-ce exact?

Answer 1

Vous pourriez mentionner le type de hachage que vous utilisez. Je suppose de votre description que c'est cuckoo hashing. Si c'est le cas, vous allez bien jusqu'à la dernière insertion. Avant 234 est inséré, vous avez:

0: 
1: 111 
2: 222 
3: 737 
4: 323 
5: 
6: 

Essayer d'insérer 234 avec h1 donne une clé de 3 mod 7 = 3, mais 3 contient déjà 373. Passant à h2 nous obtenons 4 mod 4 + 1 = 1 mais 1 contient déjà 111. A ce stade, il y a pas plus de fonctions de hachage, de sorte que nous insérer 234 à 1 et ressasser 111.

0: 
1: 234 
2: 222 
3: 737 
4: 323 
5: 
6: 

hachage 111 avec h1 donne 1 à nouveau, h2 donne 1 mod 4 + 1 = 2, mais 2 contient déjà 222, donc nous stockons 111 à 2 et ressasser 222, etc. Dans ce cas, vous trouverez finalement toutes les clés en forme. Dans le cas où les entrées ne rentrent pas toutes (c'est-à-dire que la réinsertion entre dans un cycle infini), la table doit être redimensionnée et rehaussée avec de nouvelles fonctions de hachage.

Answer 2

Je ne suis pas sûr de ce que ce problème vous veut faire s'il y a encore une collision après que la clé de hachage secondaire est vérifiée, mais je pense qu'il va comme ceci:

• 111: 1 mod 7 = 1
• 222: 2 mod 7 = 2
• 737: 3 mod 7 = 3
• 323: 2 mod 7 = 2 => Collision: 3 mod 4 + 1 = 3 + 1 = 4
• 234 : 3 mod 7 = 3 => Collision: 4 mod 4 + 1 = 0 + 1 = 1 => Collision

Si vous avancez par un après la deuxième collision, le résultat serait

• 0 -
• 1-111
• 2-222
• 3-737
• 4 - 323
• 5 - 234
• 6 -
• 7 -