Temps d'exécution pour insérer n éléments dans une table de hachage vide

Question

Les gens disent qu'il faut un O (1) amorti pour pouvoir le mettre dans une table de hachage. Donc, mettre n éléments doit être O (n). Ce n’est pas le cas pour les grands n, cependant, car, comme l’a répondu le répondeur, "Tout ce dont vous avez besoin pour satisfaire l’amortissement attendu de O (1) est d’agrandir la table et de tout redéfinir à l’aide d’une nouvelle fonction de hachage aléatoire chaque fois qu’une collision se produit." ;

Donc: quel est le temps moyen d’insertion de n éléments dans une table de hachage? Je me rends compte que cela dépend probablement de la mise en œuvre, alors mentionnez le type de mise en œuvre dont vous parlez.

Par exemple, s'il existe (log n) des collisions équidistantes et que chaque collision prend O (k) à résoudre, où k est la taille actuelle de la table de hachage, vous obtiendrez cette relation de récurrence:

T(n) = T(n/2) + n/2 + n/2

(c’est-à-dire que vous prenez le temps d’insérer n / 2 éléments, puis vous avez une collision, prenant n / 2 à résoudre, puis vous faites les n / 2 inserts restants sans collision). Cela finit toujours par être O (n), alors oui. Mais est-ce raisonnable?

Answer 1

Cela dépend complètement de l’inefficacité de votre rediffusion. Plus précisément, si vous parvenez à estimer correctement la taille attendue de votre hashtable la deuxième fois, votre temps d’approximation approche toujours de O (n). Effectivement, vous devez spécifier l’inefficacité de votre calcul de la taille du rehash avant de pouvoir déterminer l’ordre attendu.

Answer 2

  

Les gens disent qu'il faut un O (1) amorti pour pouvoir le mettre dans une table de hachage.

D'un point de vue théorique, il est attendu amorti sur O (1).

Les tables de hachage sont fondamentalement une structure de données aléatoire, de la même manière que quicksort est un algorithme aléatoire. Vous devez générer vos fonctions de hachage de manière aléatoire, sinon il existe des entrées pathologiques qui ne sont pas O (1).

Vous pouvez obtenir un O (1) amorti attendu à l'aide de hachage dynamique parfait :

L’idée naïve que j’avais initialement affichée était de réorganiser l’opération avec une nouvelle fonction de hachage aléatoire à chaque collision. (Voir aussi fonctions de hachage parfait ) Le problème avec ceci est que cela nécessite O (n ^ 2 ) l'espace, du paradoxe de l'anniversaire.

La solution est d’avoir deux tables de hachage, avec la seconde table pour les collisions; résoudre les collisions sur cette deuxième table en le reconstruisant. Cette table aura des éléments O (\ sqrt {n}), donc elle passera à la taille O (n).

En pratique, vous utilisez souvent simplement une fonction de hachage fixe car vous pouvez supposer (ou ne pas vous en soucier) que votre entrée est pathologique, un peu comme vous triez souvent les commandes sans passer au prérandom de l'entrée.

Answer 3

Tout ce que O (1) dit, c’est que l’opération est effectuée en temps constant et qu'elle ne dépend pas du nombre d'éléments de votre structure de données.

En termes simples, cela signifie que vous devrez payer le même coût, quelle que soit la taille de votre structure de données.

Concrètement, cela signifie que les structures de données simples telles que les arbres sont généralement plus efficaces lorsque vous n’avez pas à stocker beaucoup de données. Dans mon expérience, je trouve les arbres plus rapides jusqu’à ~ 1k éléments (entiers 32 bits), puis les tables de hachage prennent le dessus. Mais comme d'habitude YMMW.

Answer 4

Pourquoi ne pas simplement exécuter quelques tests sur votre système? Si vous publiez la source, nous pourrons peut-être revenir en arrière et les tester sur nos systèmes, ce qui pourrait en faire une discussion très utile.

Ce n’est tout simplement pas l’implémentation, mais l’environnement également qui détermine le temps que prend réellement l’algorithme. Vous pouvez toutefois vérifier si des échantillons d'analyse comparative sont disponibles ou non. Le problème avec le fait que je publie mes résultats ne sera d'aucune utilité, car les utilisateurs n'ont aucune idée de ce qui se passe sur mon système, de la quantité de mémoire RAM disponible, etc. Vous ne pouvez avoir qu'une idée générale. Et c’est à peu près aussi bon que ce que le big-O vous donne.