Comment les tables de hachage O (1) prennent-elles en compte la vitesse de hachage?

Les tables de hachage sont censées être amorties utilisant, par exemple, un simple enchaînement et un doublement à une certaine capacité. $\Theta(1)$

Cependant, cela suppose que les longueurs des éléments sont constantes. Le calcul du hachage d'un élément nécessite de passer par l'élément, en prenant le temps où est la longueur. $\Theta(l)$ $l$

Mais pour distinguer entre éléments, nous avons besoin que les éléments aient au moins bits de longueur ; sinon, par principe de trou de pigeon, ils ne seront pas distincts. La fonction de hachage passant par bits d'élément va prendre du temps . $n$ $\lg n$ $\lg n$ $\Theta(\lg n)$

Pouvons-nous plutôt dire que la vitesse d'une table de hachage, en tenant compte d'une fonction de hachage raisonnable qui utilise toutes les parties de l'entrée, est en fait ? Pourquoi, dans la pratique, les tables de hachage sont-elles efficaces pour stocker des éléments de longueur variable, tels que des chaînes et de grands entiers? $\Theta(\lg n)$

hash-tables dictionaries ithisa
la source

Étroitement liés: (Quand) la recherche de table de hachage est-elle O (1)? , Pour quel type de données les opérations de table de hachage sont-elles O (1)?

Gilles 'SO- arrête d'être méchant'

La réponse est qu'ils ne le sont pas . Ce type d'analyse de hachage ne prend pas en compte la dimension (ou le nombre de bits) des éléments, mais uniquement leur multitude.

Nikos M.

Mais si une recherche de carte de hachage qui serait ne considérant pas la lecture et l'écriture des bits comme décrit, est , alors selon les mêmes critères, une recherche binaire ou tout autre processus que nous considérer normalement serait en fait n'est-ce pas?

Θ (1)

$\Theta (1)$

\in Θ (l g

$\in \Theta (lg$

n)

$n)$

\in Θ l g

$\in \Theta lg$

n

$n$

\in Θ (l g^{2}

$\in \Theta( lg^2$

n)

$n )$

@tAllan cf uniforme vs modèle de coût logarithmique .

Raphael

@tAllan Une recherche binaire régulière serait mais si vous gardez les éléments triés selon les séquences de bits de leurs clés et effectuez une recherche binaire en comparant "un bit à la fois" (détails délicats omis), vous pourriez être en mesure d'atteindre .

Θ (\log^{2} n)

$\Theta(\log^2 n)$

Θ (\log n)

$\Theta(\log n)$

Rétablir Monica le

Réponses:

L'histoire selon laquelle les tables de hachage sont amorties est ~~un mensonge~~ une simplification excessive. $\Theta(1)$

Cela n'est vrai que si:
- La quantité de données à hacher par élément est triviale par rapport au nombre de K eys et la vitesse de hachage d'un K ey est rapide - . - Le nombre de C ollisions est petit - . - Nous ne pas prendre en compte le temps nécessaire à la R edimension la table de hachage - . $k$
$c$
$r$

Grandes chaînes à hacher
Si la première hypothèse est fausse, le temps d'exécution ira jusqu'à . Cela est certainement vrai pour les grandes chaînes, mais pour les grandes chaînes, une comparaison simple aurait également un temps d'exécution de . Un hachage n'est donc pas asymptotiquement plus lent, bien que le hachage soit toujours plus lent qu'une simple comparaison, car la comparaison a une option de désactivation précoce ergo , et le hachage doit toujours hacher la chaîne complète , . $\Theta(k)$
$\Theta(k)$ $O(1)$ $\Omega(k)$ $O(k)$ $\Omega(k)$

Notez que les entiers croissent très lentement. 8 octets peuvent stocker des valeurs jusqu'à ; 8 octets est un montant trivial à hacher. Si vous voulez stocker des bigints, considérez-les simplement comme des chaînes. $10^{18}$

Algorithme de hachage lent
Si le montant dépensé pour le hachage n'est pas trivial par rapport au stockage des données, alors l' hypothèse devient évidemment intenable. À moins qu'un hachage cryptographique ne soit utilisé, cela ne devrait pas poser de problème. $\Theta(1)$

Ce qui importe, c'est que . Tant que cela contient est une déclaration juste. $n$ $>>$ $k$ $\Theta(1)$

De nombreuses collisions
Si la fonction de hachage est médiocre, ou la table de hachage est petite, ou la taille de la table de hachage est maladroite, les collisions seront fréquentes et le temps d'exécution ira à . La fonction de hachage doit être choisie de manière à ce que les collisions soient rares tout en étant aussi rapides que possible, en cas de doute, optez pour moins de collisions au détriment d'un hachage plus lent. En règle générale, la table de hachage doit toujours être remplie à moins de 75%. Et la taille de la table de hachage ne doit pas avoir de corrélation avec la fonction de hachage. Souvent, la taille de la table de hachage est (relativement) première. $O(log(n))$

Redimensionner la table de hachage
Puisqu'une table de hachage presque pleine donnera trop de collisions et qu'une grande table de hachage (vide) est un gaspillage d'espace, de nombreuses implémentations permettent à la table de hachage de croître (et de rétrécir!) Selon les besoins.
La croissance d'une table peut impliquer une copie complète de tous les éléments (et éventuellement un remaniement), car le stockage doit être continu pour des raisons de performances.
Ce n'est que dans des cas pathologiques que le redimensionnement de la table de hachage sera un problème, de sorte que les redimensionnements (coûteux mais rares) sont amortis sur de nombreux appels.

Temps d'exécution Le temps
réel d'exécution d'une table de hachage est donc . Chacun de , , en moyenne est supposé être une (petite) constante dans le temps de fonctionnement amorti et nous disons donc que est une déclaration juste. $\Theta(kcr)$
$k$ $c$ $r$ $\Theta(1)$

Pour revenir à vos questions
Veuillez m'excuser de paraphraser, j'ai essayé d'extraire différents ensembles de sens, n'hésitez pas à commenter si j'en ai oublié

Vous semblez préoccupé par la longueur de la sortie de la fonction de hachage. Appelons cela ( est généralement considéré comme le nombre d'éléments à hacher). sera car m doit identifier de manière unique une entrée dans la table de hachage. Cela signifie que m croît très lentement. À 64 bits, le nombre d'entrées de table de hachage occupera une partie importante de la mémoire RAM disponible dans le monde. À 128 bits, il dépassera de loin le stockage sur disque disponible sur la planète Terre. Produire un hachage 128 bits n'est pas beaucoup plus difficile qu'un hachage 32 bits, donc non , le temps de créer un hachage n'est pas (ou si vous voulez). $m$ $n$ $m$ $log(n)$

$O(m)$ $O(log(n))$

La fonction de hachage passant par bits d'élément va prendre temps. $log(n)$ $Θ(log(n))$

Mais la fonction de hachage ne passe pas par les bits des éléments. Pour un élément (!!), il ne passe que par les données . De plus, la longueur de l'entrée (k) n'a aucun rapport avec le nombre d'éléments. Cela est important, car certains algorithmes non hachés doivent examiner de nombreux éléments de la collection pour trouver un élément (non) correspondant. Le tableau de hachage ne fait en moyenne qu'une ou deux comparaisons par élément considéré avant d'arriver à une conclusion. $log(n)$
$O(k)$

Pourquoi les tables de hachage sont-elles efficaces pour stocker des éléments de longueur variable?

Parce que quelle que soit la longueur de l'entrée ( ), la longueur de la sortie ( ) est toujours la même, les collisions sont rares et le temps de recherche est constant. Cependant, lorsque la longueur de clé augmente par rapport au nombre d'éléments dans la table de hachage ( ), l'histoire change ... $k$ $m$
$k$ $n$

Pourquoi les tables de hachage sont-elles efficaces pour stocker de grandes chaînes?

Les tables de hachage ne sont pas très efficaces pour les très grandes chaînes.

Si ce (c'est-à-dire que la taille de l'entrée est plutôt grande par rapport au nombre d'éléments dans la table de hachage), nous ne pouvons plus dire que le hachage a un temps de fonctionnement constant, mais doit passer à un temps de fonctionnement de surtout parce qu'il n'y a pas de sortie anticipée. Vous devez hacher la clé complète. Si vous ne stockez qu'un nombre limité d'articles, il vaut mieux utiliser un stockage trié, car lorsque vous comparez vous pouvez vous désinscrire dès qu'une différence apparaît. $not$ $n >> k$ $\Theta(k)$ $k1$ $\ne$ $k2$

Cependant, si vous connaissez vos données, vous pouvez choisir de ne pas hacher la clé complète, mais uniquement la partie volatile (connue ou supposée) de celle-ci, en restaurant la propriété tout en gardant les collisions en échec. $\Theta(1)$

Constantes cachées
Comme tout le monde devrait le savoir signifie simplement que le temps par élément traité est une constante. Cette constante est un peu plus grande pour le hachage que pour la comparaison simple. Pour les petites tables, une recherche binaire sera plus rapide qu'une recherche de hachage, car par exemple 10 comparaisons binaires pourraient très bien être plus rapides qu'un seul hachage. Pour les petits ensembles de données, des alternatives aux tables de hachage doivent être envisagées. C'est sur de grands ensembles de données que les tables de hachage brillent vraiment. $\Theta(1)$

Johan
la source

Je ne comprends pas votre définition de . Ce n'est pas vrai que le redimensionnement augmente le temps d'exécution amorti. Tant que vous effectuez le redimensionnement de manière appropriée, le coût de la copie peut être amorti et n'augmente pas le temps d'exécution amorti. Je ne pense pas que la vitesse du hachage soit un problème (même les hachages cryptographiques sont très rapides; et en tout cas, ils s'exécutent en temps constant, si la longueur de l'entrée est limitée par une constante). Les revendications d'exécution dépendent toujours de l'utilisation d'une bonne fonction de hachage (les collisions seront donc peu nombreuses).

k, c, r

$k,c,r$

O (1)

$O(1)$

Donc, parmi les problèmes que vous avez mentionnés, je pense que seule la longueur de la contribution est vraiment un problème grave. De plus, cela ne répond pas vraiment à la question qui a été posée. La question parle de la longueur des sorties et cette longueur des sorties devrait être considérée comme des bits plutôt que des bits . C'est exact, mais ce qu'il néglige, c'est le modèle de calcul utilisé pour calculer le temps d'exécution . Cette réponse ne semble pas entrer dans tout cela, donc je ne suis pas sûr que cela aborde la question soulevée dans la question.

Ω (\lg n)

$\Omega(\lg n)$

O (1)

$O(1)$

O (1)

$O(1)$

Je voulais être complet avec tous les éléments du temps de course. Nous convenons que seule la longueur de la clé est vraiment une préoccupation lors du hachage. J'ai corrigé le problème de journal (n) que l'OP a soulevé. Je l'ai mal lu, parce que c'est un non-problème lors du hachage de l'OMI.

Johan

J'espère que la réponse est plus en phase avec la question du PO maintenant.

Johan

Commençons par une question plus simple. Considérez quelle est peut-être la structure de données la plus simple qui existe, un tableau . Pour être concret, imaginons un tableau d'entiers. Combien de temps dure l'opération ? La réponse dépend du modèle de calcul. Deux modèles sont pertinents ici: le modèle RAM (qui est plus courant) et le modèle binaire (qui est plus simple à expliquer). $A[i] = A[j]$

Dans le modèle binaire , une opération de base comportant bits de coûts . Donc, si les entiers ont une largeur de bits, l'opération va coûter environ . $N$ $N$ $w$ $A[i] = A[j]$ $2w$

Dans le modèle RAM , l'unité de base des données n'est pas un bit mais un mot (parfois appelé mot machine ). Un mot est un entier de largeur , où est la taille des entrées (en bits). Une opération de base impliquant mots coûts . Dans la plupart des cas, si vous avez un tableau d'entiers, les entiers dont vous avez besoin ont la largeur , et donc l'opération coûte . $\log n$ $n$ $N$ $N$ $O(\log n)$ $A[i] = A[j]$ $O(1)$

Comme je l'ai dit ci-dessus, nous analysons généralement les algorithmes en utilisant le modèle RAM. La seule exception courante est l'arithmétique des nombres entiers, en particulier la multiplication des nombres entiers, qui est souvent analysée en fonction du nombre d'opérations binaires.

Pourquoi utilisons-nous le modèle RAM? Puisqu'il a plus de pouvoir prédictif (vis à vis de la réalité). L'hypothèse selon laquelle la taille d'entrée est au plus exponentielle dans la taille d'un mot machine est généralement justifiée, en particulier pour les processeurs 64 bits modernes, et les opérations sur les mots machine prennent un temps constant dans les CPU réels.

Les tables de hachage sont des structures de données plus compliquées, et elles impliquent vraiment trois types: le type de clé, le type de hachage et le type de valeur. Du point de vue du type de valeur , une table de hachage n'est qu'un tableau glorifié, alors ignorons cet aspect. On peut toujours supposer que le type de hachage consiste en un petit nombre de mots machine. Le type de clé satisfait une propriété spéciale: il est lavable , ce qui signifie qu'il a une opération de hachage qui (au minimum) est une fonction déterministe (une fonction retournant toujours la même valeur).

Nous pouvons maintenant répondre à votre question: combien de temps faut-il pour hacher une clé? La réponse dépend du modèle de calcul. Cette fois, nous avons trois modèles communs: les deux précédents et le modèle Oracle.

Dans le modèle oracle , nous supposons que la fonction de hachage nous est donnée par un "oracle" qui peut calculer le hachage d'une clé arbitraire en temps constant.

Dans le modèle RAM et le modèle binaire , la fonction de hachage est une fonction réelle et la complexité temporelle de la table de hachage dépend de la complexité temporelle de la fonction de hachage. Les fonctions de hachage utilisées pour la table de hachage (plutôt qu'à des fins cryptographiques) sont généralement très rapides et prennent un temps linéaire dans l'entrée. Cela signifie que si le type de clé a une longueur bits (dans le modèle binaire) ou mots (dans le modèle RAM), la fonction de hachage prend le temps . Lorsque est une constante, la fonction de hachage prend un temps constant. $N$ $N$ $O(N)$ $N$

Lorsque nous analysons le temps d'exécution des algorithmes de table de hachage, nous utilisons généralement implicitement le modèle Oracle. Cela s'exprime souvent dans une langue différente: nous disons simplement que nous comptons le nombre d'appels de la fonction de hachage. Cela a du sens, car généralement les applications de la fonction de hachage sont le terme dominant dans le temps d'exécution des algorithmes de table de hachage, et donc pour analyser la complexité réelle du temps, tout ce que vous avez à faire est de multiplier le nombre d'appels de hachage par le temps d'exécution de la fonction de hachage.

Lorsque nous analysons le temps d'exécution d'un algorithme en utilisant une table de hachage comme structure de données, nous nous intéressons souvent au temps d'exécution réel, généralement dans le modèle RAM. Une option ici est de faire ce qui a été suggéré dans le paragraphe précédent, à savoir multiplier le temps d'exécution des opérations de table de hachage (donné en termes de nombre d'appels de fonctions de hachage) par le temps d'exécution de la fonction de hachage.

Cependant, ce n'est pas suffisant si les touches ont des longueurs variables. Par exemple, imaginez que nous avons des clés de taille , et nous calculons le hachage de chacune d'elles une fois. La complexité temporelle réelle est , mais le calcul ci-dessus ne donne que . Si tel est le cas dans certaines applications, nous pouvons en tenir compte au cas par cas, en utilisant une analyse affinée de la complexité de la table de hachage sous-jacente. $1,2,4,\ldots,2^m$ $O(2^m)$ $O(m2^m)$

Yuval Filmus
la source