Moyen efficace pour réduire le nombre de recherches?

Question

J'ai une table de hachage, avec des clés de chaîne et des valeurs.

La clé doit être construite en fonction de certains paramètres. Par exemple, param1: param2: param3: param4: param5: param6. Dans le cas où la valeur (la valeur la plus préférée) pour la clé complète n'est pas disponible dans le hachage, je chercherai juste la prochaine valeur préférée en construisant la clé ": param2: param3: param4: param5: param6".

S'il n'y a pas de valeur, je construis une clé avec une certaine combinaison de paramètres en supprimant un ou plusieurs des paramètres. Donc, fondamentalement, il existe une hiérarchie de recherches de clés basée sur certaines préférences.

Mon approche actuelle est de construire une clé, une recherche, puis si elle n'est pas trouvée dans le hachage, construire la clé suivante dans la hiérarchie et ainsi de suite ... Mais cela peut aboutir à de nombreuses recherches avant ou non valeur. Notez qu'il peut y avoir plus d'une clé retournant la valeur, par exemple à la fois "param1: param2: param3: param4: param5: param6" et ": param2: param3: param4: param5: param6" peuvent avoir la valeur, mais je préfère la valeur de la première clé et ne recherchera même pas la seconde.

Je pense qu'il pourrait y avoir un moyen plus efficace d'aborder cela. Quel est le moyen le plus efficace de faire ce genre de recherche?

Answer 1

Ce ne sera pas la meilleure façon de générer de bonnes clés de hachage. Mais voici l'idée.

Dites que vous avez le choix entre n chaînes. Vous pouvez générer h hashes pour chacune des chaînes. Donc, vous aurez h1, h2, h3, .... hn. Puis, lorsque vous avez généré une clé, la clé peut être une combinaison de hi^hj^... hk, où k sera le nombre de paramètres dans votre clé. Maintenant, pour rechercher, p1p2p3 ... pk, vous pouvez faire H = h (p1)^h (p2) ....^h (pk). Si la recherche échoue, faites simplement H = H^h (p1)^h (p_k + 1). Je ne suis pas sûr que la performance obtenue pour les collisions de hachage lors d'une telle personnalisation écrase la génération de clé en concaténant les chaînes et en les hachant.

Une autre approche:

Créer un tableau de caractères, où tous vos params sont concaténées en une seule chaîne. Vous pouvez avoir un autre tableau, qui garde trace de l'endroit où chaque paramètre se termine. Ensuite, il est facile de simplement extraire le tableau de param1 à param_k pour générer le hachage pour chaque itération. De cette façon, vous évitez de créer des chaînes concaténées, si votre performance provient de là.