Comment trouver la fonction de hachage la plus efficace (moins de chances de collision possibles) pour l'ensemble des chaînes.
Supposons que nous soyons donnés avec des cordes .. La longueur des chaînes n'est pas non plus définie. Ajay Vijay Rakhi ....
Nous connaissons le nombre de non. des cordes disponibles, nous pouvons donc concevoir une table de hachage de taille (comptez disponible). Quelle pourrait être la fonction de hachage parfaite que nous pourrions concevoir pour un tel problème ??
Multiplier chaque caractère de la valeur ASCII de caractères de 31 (NO PREMIER no Solution ....
J'ai peu de jeux de chaînes, disons compter = 10. Je dois mettre en œuvre une fonction de hachage de telle sorte que toutes ces 10 chaînes s'adaptent de manière unique dans la table de hachage ... toute fonction de hachage parfaite O ( 1) disponible, pour ce genre de problème ?? La taille de la table de hachage sera de 10, pour ce cas ...
Seulement C Programmation ...
Veuillez expliquer la logique sur le site Web .... http://burttburtttow.net/bob/c/perfect.c Cela semble très compliqué mais parfait pour moi .. !! Quel est l'algorithme utilisé ici ... lire le code tout de suite, est très difficile !!
merci ....
4 Réponses :
Les tables de hachage sont censées pouvoir gérer une entrée dynamique. Si vous ne pouvez garantir qu'un ensemble particulier d'entrées et que vous souhaitez garantir une fente particulière pour chaque entrée, pourquoi Hash du tout?
Il suffit de faire une matrice indexée pour chaque entrée disponible connue.
Pour un grand jeu de données avec presque seulement un accès en lecture, il peut être sensible à utiliser quelque chose comme un hachage parfait.
Pourquoi aurait-il un sens au hasch lorsque vous avez un ensemble d'entrées connu et garantissant une fente pour chaque entrée? Vous pouvez simplement ignorer le coût d'une fonction de hachage et effectuer une recherche de tableau avec des index #definefin pour chaque "entrée connue".
"Entrée connue" est relatif. Si vous savez que vous effectuerez un accès aléatoire à 5 Gibib de données fournis à l'exécution , il serait peut-être une bonne idée de la parfaite bonne chance à obtenir O (1) accès.
Il reste toujours la question de transformer une chaîne dans un entier afin que vous puissiez le regarder dans une table. Comment proposez-vous d'utiliser une chaîne comme indice de tableau?
@Jim, bon point. Les commentaires de Phillip sont valables. J'ai vu que la question a été modifiée un peu pour ne pas prendre en compte la connaissance complète de chaque entrée, donc non ma réponse semble très non pertinente.
Vous voudrez peut-être examiner hachage parfait.
Philip , Pouvez-vous soutenir cela avec un exemple ... si nous avons des chaînes ... Comment pouvons-nous obtenir un entier (unique) sur ces listes de cordes?
@Ageek: Si vous regardez la section «Liens externes» de l'article que Philipp a lié, vous verrez plusieurs implémentations gratuites de générateurs de hachage parfaits.
J'ai besoin d'un code .... exemple ... dans le programme C ... et besoin d'une fonction de hachage parfaite .. Cela pourrait donner le résultat dans O (1) heure ..
Vérifiez certains de ces éléments, ils ont apparemment de bonnes distributions
http://www.partow.net/programming/hashfonctions/#hashingMethodologies
Vous voudrez peut-être consulter GPERF , vous pourriez un peu faire cela sur le Volez si vous ne l'avez pas fait trop souvent et que vos données ont un petit. Si les chaînes sont connues à l'avance, ceci est la méthode
Ohh, ces solutions ne sont pas d'aide cher .... Est-ce que une solution existe-t-il qui pourrait donner une valeur de hachage parfaite pour une série de cordes donnée ... Nombre de cordes pourraient être très grandes .... Solution de hash parfaite !! Est-ce qu'il existe du tout ...?
Le programme GPERF recommandé par @necrolis est un programme de travail open source réel. Vous pouvez télécharger et voir la source pour voir comment cela se fait. Il est difficile d'imaginer un meilleur exemple que cela.
Et qu'en est-il du code sur ce site ...
BURLETURTLET.net/bob/c/perfect.c Ce site semble bon .. parfait Fonction de hachage ... mais je ne suis pas capable de le comprendre .. S'il vous plaît aider ...