Si je souhaite utiliser un hachage extensible pour stocker un maximum de 100 enregistrements, quelle est la taille de matrice minimale dont j'ai besoin?taille du tableau pour le hachage extensible
Je devine qu'un tableau de 100 serait suffisant, mais je pourrais me tromper. Je soupçonne également que je peux utiliser un plus petit tableau.
Que savez-vous de votre fonction de hachage?
Vous avez mentionné le hachage extensible.
Avec hachage extensible, vous regardez votre hachage comme une chaîne de caractères et généralement mettre en œuvre la recherche de seau via un trie. Au lieu d'une recherche basée sur Trie, je suppose que vous convertissez cela en un index dans votre tableau.
Vous avez mentionné que vous aurez au plus 100 éléments. Si vous vouliez tous les hachages distincts vous auriez 128 possibilités puisque c'est la combinaison la plus proche de bits avec 7 bits.
Si votre fonction de hachage peut hachage chaque élément pour avoir 7 bits sur 7 (ou plus) différents, alors vous avez la solution optimale avec une taille de godet de 1. Leaving 128 nœuds feuille, ou un tableau de taille 128.
Si votre fonction de hachage peut hachage chaque élément pour avoir 6 bits sur 7 (ou plus) différents, alors vous avez une taille de godet de 2. Vous auriez 64 nœuds feuilles/combinaisons/taille de tableau.
Si votre fonction de hachage peut faire en sorte que chaque élément possède 5 bits sur 7 (ou plus) différents, vous avez alors une taille de 4. Vous disposez de 32 nœuds/combinaisons/taille de tableau. Puisque vous avez dit que vous voulez une taille de seau de 4, je pense que votre réponse serait 32 et vous avez besoin d'une bonne fonction de hachage qui peut vous donner au moins 5 des premiers bits.
Même si c'est une clé unique, alors vous obtenez le reste après avoir divisé à 100. Et ce ne sera probablement pas toujours unique. Donc, je pense qu'il est difficile de déterminer que l'algorithme de hachage vous donnera un index unique par rapport au tableau :) – vodkhang
@vodkhang: Il est parfaitement possible d'avoir un mapping 1: 1 et spanning. –
J'ai manqué ce bit: le hachage extensible qui change complètement la réponse. J'ai réécrit ma réponse. –
Je pense que cela dépend de si vous avez besoin de haute performance ou d'économie de stockage. Vous pouvez simplement enregistrer des éléments dans un tableau de 100. Je ne sais pas grand-chose sur le hachage extensible, mais ma compréhension générale du hachage est qu'il aura quelques types de collision, et si vous utilisez un plus grand tableau pour le stocker, le le nombre de collisions peut diminuer et les performances d'ajout/de suppression et d'interrogation seront également plus rapides. Je pense que vous devriez utiliser au moins 128 (juste pour être 2^k, je ne suis pas un expert en hachage) :)
J'ai oublié d'ajouter que la taille du seau est de 4, ce qui compte. – neuromancer
comment imaginez-vous que vous pouvez utiliser un tableau inférieur à 100 pour stocker 100 enregistrements différents? – Stephen
Chaque entrée de tableau pointe vers un compartiment. La taille du godet est 4, ce qui signifie que 4 enregistrements au maximum peuvent tenir dans un godet. Ainsi, une entrée de tableau peut pointer vers 4 enregistrements. – neuromancer