hachage constante de temps pour les chaînes?

Question

Une autre question sur le SO élevé des installations dans certaines langues à des chaînes de hachage pour leur donner une recherche rapide dans une table. Deux exemples sont dictionnaire <> dans .NET et la structure de stockage {} en Python. D'autres langues soutiennent certainement un tel mécanisme. C ++ a sa carte, LISP a un équivalent, comme le font la plupart des autres langues modernes.

Il a été soutenu dans les réponses à la question que les algorithmes de hachage sur les chaînes peuvent être réalisées en HEUREM constante avec un membre SO qui a 25 ans d'expérience dans la programmation affirmant que tout peut être haché en temps constant. Mon affirmation personnelle est que ce n'est pas vrai, à moins que votre application particulière impose une limite sur la longueur de la chaîne. Cela signifie que certains constante K dicterait la longueur maximale d'une chaîne.

Je connais l'algorithme Rabin-Karp qui utilise une fonction de hachage pour son fonctionnement, mais cet algorithme ne dicte pas une fonction de hachage spécifique à utiliser, et l'un des auteurs ont suggéré est O (m), où m est la longueur de la chaîne hachée.

Je vois d'autres pages comme celle-ci ( http: // www. cse.yorku.ca/~oz/hash.html ) qui affichent des algorithmes de hachage, mais il semble que chacun d'eux itère sur toute la longueur de la chaîne pour arriver à sa valeur.

De ma lecture relativement limitée sur le sujet, il semble que la plupart des tableaux pour des types de chaîne sont effectivement créés à l'aide d'une fonction de hachage qui fonctionne avec un arbre de quelque sorte sous le capot. Cela peut être un arbre AVL ou arbre rouge / noir qui pointe vers l'emplacement de l'élément de valeur dans la paire clé / valeur.

Même avec cette structure d'arbre, si nous voulons rester de l'ordre de thêta (log (n)), n étant le nombre d'éléments dans l'arbre, nous devons avoir un algorithme de hachage à temps constant. Dans le cas contraire, nous avons la peine additif de itérer sur la chaîne. Même si thêta (m) serait éclipsée par thêta (log (n)) pour les index contenant de nombreuses chaînes, nous ne pouvons pas l'ignorer si nous sommes dans un tel domaine que les textes que nous la recherche contre sera très grande.

Je suis conscient du fait que les arbres suffixe / tableaux et Aho-Corasick peuvent apporter la recherche jusqu'à thêta (m) pour une plus grande dépense en mémoire, mais ce que je vous demande précisément si une méthode de hachage constante de temps existe pour les chaînes d'arbitraire longueurs comme cela a été revendiqué par l'autre élément SO.

Merci.

Answer 1

En général, je crois que tout hachage de chaîne complète doit utiliser tous les caractères de la chaîne et aurait donc besoin de croître comme O (n) pour n caractères. Cependant, je pense que pour la chaîne pratique hachages vous pouvez utiliser hash approximatives qui peuvent facilement être O (1).

Considérons un hachage de chaîne qui utilise toujours min (n, 20) caractères pour calculer un hachage standard. Il est évident que cela augmente à mesure que O (1) avec la taille de la chaîne. Est-il fonctionner de manière fiable? Cela dépend de votre domaine ...

Answer 2

Une fonction de hachage ne doit pas (et ne peut pas) retourner une valeur unique pour chaque chaîne.

Vous pouvez utiliser les 10 premiers caractères pour initialiser un générateur de nombres aléatoires et l'utiliser ensuite pour tirer 100 caractères aléatoires de la chaîne, et hachage. Ce serait temps constant.

Vous pouvez aussi simplement retourner la valeur constante 1. Au sens strict, cela est encore une fonction de hachage, mais pas très utile.

Answer 3

Vous ne pouvez pas obtenir facilement un algorithme de hachage constante de temps général pour les chaînes sans risquer de cas graves de collisions de hachage.

Pour qu'elle soit constante de temps, vous ne serez pas en mesure d'accéder à tous les caractères de la chaîne. A titre d'exemple simple, supposons que nous prenons les 6 premiers caractères. Puis vient quelqu'un et tente de hachage un tableau d'URL. La fonction a verra « http: / ». Pour chaque chaîne unique

Des scénarios semblables peuvent se produire pour d'autres caractères sélections systèmes. Vous pouvez choisir des caractères à base pseudo-aléatoire sur la valeur du caractère précédent, mais vous courez toujours le risque d'échec spectaculaire si les cordes pour une raison quelconque ont le modèle « mauvais » et beaucoup finissent avec la même valeur de hachage.

Answer 4

Vous pouvez espoir pour asymptotiquement moins que le temps de hachage linéaire si vous utilisez

Bien que je ne peux pas imaginer une fonction de hachage à temps fixe pour les chaînes de longueur illimitée, il n'y a vraiment pas besoin.

L'idée derrière l'aide d'une fonction de hachage est de générer une distribution des valeurs de hachage qui le rend peu probable que de nombreuses chaînes se heurteraient - pour le domaine considéré. Cette clé permettrait un accès direct dans un magasin de données. Ces deux résultats combinés en une constante de temps recherche -. En moyenne

Si jamais cette collision se produit, l'algorithme de recherche retombe sur une sous-stratégie de recherche plus flexible.

Certes, cela est faisable, tant que vous assurer que vous êtes « interné », avant de les transmettre toutes vos chaînes à quelque chose nécessitant hash. Interner est le processus consistant à insérer la chaîne dans une table de chaînes, de telle sorte que toutes les chaînes internés ayant la même valeur sont en fait le même objet. Ensuite, vous pouvez simplement le pointeur de hachage (longueur fixe) à la chaîne interné, au lieu de hachage de la chaîne elle-même.

Vous pouvez être intéressé par le résultat mathématique suivante je suis venu avec l'an dernier.

Considérons le problème de hachant un nombre infini de clés tels que l'ensemble de toutes les chaînes de toute longueur à l'ensemble des nombres dans {1,2, ..., b}. produit de hachage au hasard par la première cueillette à une fonction de hachage h aléatoire dans une famille de fonctions H.

Je vais montrer qu'il ya toujours un nombre infini de clés qui sont certains d'entrer en collision sur toutes les fonctions de H, qui est, ils ont toujours la même valeur de hachage pour toutes les fonctions de hachage.

Choisissez une fonction de hachage h: il y a au moins une valeur de hachage y telle que l'ensemble A = {s: h (s) = y} est infini, qui est, vous avez une infinité de chaînes entrant en collision. Choisir une autre fonction de hachage h « et hacher les clés dans l'ensemble A. Il y a au moins une valeur de hachage y » de telle sorte que l'ensemble A « = {s est dans A: h » (s) = y '} est infini, qui est, il y a une infinité de chaînes entrant en collision sur deux fonctions de hachage. Vous pouvez répéter cet argument un certain nombre de fois. Répétez H fois. Ensuite, vous avez un ensemble infini de chaînes où toutes les chaînes entrent en collision sur toutes vos fonctions de hachage H. CQFD.

Pour en savoir plus : hash de chaînes de Sensible longueur variable est impossible http: // lemire.me/blog/archives/2009/10/02/sensible-hashing-of-variable-length-strings-is-impossible/

Answer 5

Answer 6

Answer 7

Bien que je ne peux pas imaginer une fonction de hachage à temps fixe pour les chaînes de longueur illimitée, il n'y a vraiment pas besoin.

L'idée derrière l'aide d'une fonction de hachage est de générer une distribution des valeurs de hachage qui le rend peu probable que de nombreuses chaînes se heurteraient - pour le domaine considéré. Cette clé permettrait un accès direct dans un magasin de données. Ces deux résultats combinés en une constante de temps recherche -. En moyenne

Si jamais cette collision se produit, l'algorithme de recherche retombe sur une sous-stratégie de recherche plus flexible.

Answer 8

Certes, cela est faisable, tant que vous assurer que vous êtes « interné », avant de les transmettre toutes vos chaînes à quelque chose nécessitant hash. Interner est le processus consistant à insérer la chaîne dans une table de chaînes, de telle sorte que toutes les chaînes internés ayant la même valeur sont en fait le même objet. Ensuite, vous pouvez simplement le pointeur de hachage (longueur fixe) à la chaîne interné, au lieu de hachage de la chaîne elle-même.

Answer 9

Certes, cela est faisable, tant que vous assurer que vous êtes « interné », avant de les transmettre toutes vos chaînes à quelque chose nécessitant hash. Interner est le processus consistant à insérer la chaîne dans une table de chaînes, de telle sorte que toutes les chaînes internés ayant la même valeur sont en fait le même objet. Ensuite, vous pouvez simplement le pointeur de hachage (longueur fixe) à la chaîne interné, au lieu de hachage de la chaîne elle-même.

Answer 10

Vous pouvez être intéressé par le résultat mathématique suivante je suis venu avec l'an dernier.

Considérons le problème de hachant un nombre infini de clés tels que l'ensemble de toutes les chaînes de toute longueur à l'ensemble des nombres dans {1,2, ..., b}. produit de hachage au hasard par la première cueillette à une fonction de hachage h aléatoire dans une famille de fonctions H.

Je vais montrer qu'il ya toujours un nombre infini de clés qui sont certains d'entrer en collision sur toutes les fonctions de H, qui est, ils ont toujours la même valeur de hachage pour toutes les fonctions de hachage.

Choisissez une fonction de hachage h: il y a au moins une valeur de hachage y telle que l'ensemble A = {s: h (s) = y} est infini, qui est, vous avez une infinité de chaînes entrant en collision. Choisir une autre fonction de hachage h « et hacher les clés dans l'ensemble A. Il y a au moins une valeur de hachage y » de telle sorte que l'ensemble A « = {s est dans A: h » (s) = y '} est infini, qui est, il y a une infinité de chaînes entrant en collision sur deux fonctions de hachage. Vous pouvez répéter cet argument un certain nombre de fois. Répétez H fois. Ensuite, vous avez un ensemble infini de chaînes où toutes les chaînes entrent en collision sur toutes vos fonctions de hachage H. CQFD.

Pour en savoir plus : hash de chaînes de Sensible longueur variable est impossible http: // lemire.me/blog/archives/2009/10/02/sensible-hashing-of-variable-length-strings-is-impossible/

Answer 11

Answer 12

Vous pouvez être intéressé par le résultat mathématique suivante je suis venu avec l'an dernier.

Considérons le problème de hachant un nombre infini de clés tels que l'ensemble de toutes les chaînes de toute longueur à l'ensemble des nombres dans {1,2, ..., b}. produit de hachage au hasard par la première cueillette à une fonction de hachage h aléatoire dans une famille de fonctions H.

Je vais montrer qu'il ya toujours un nombre infini de clés qui sont certains d'entrer en collision sur toutes les fonctions de H, qui est, ils ont toujours la même valeur de hachage pour toutes les fonctions de hachage.

Choisissez une fonction de hachage h: il y a au moins une valeur de hachage y telle que l'ensemble A = {s: h (s) = y} est infini, qui est, vous avez une infinité de chaînes entrant en collision. Choisir une autre fonction de hachage h « et hacher les clés dans l'ensemble A. Il y a au moins une valeur de hachage y » de telle sorte que l'ensemble A « = {s est dans A: h » (s) = y '} est infini, qui est, il y a une infinité de chaînes entrant en collision sur deux fonctions de hachage. Vous pouvez répéter cet argument un certain nombre de fois. Répétez H fois. Ensuite, vous avez un ensemble infini de chaînes où toutes les chaînes entrent en collision sur toutes vos fonctions de hachage H. CQFD.

Answer 13

Pour en savoir plus : hash de chaînes de Sensible longueur variable est impossible