Je veux implémenter une table de hachage à l'aide d'arbres de recherche binaires pour réduire la complexité de la recherche dans le processus de chaînage séparé de O (n) (en utilisant la liste chaînée) à O (log n) (en utilisant BST). Cela peut-il être fait, et si oui, comment? Il serait plus facile de comprendre si la solution est étape par étape, la mise en œuvre de la logique.
Je veux réduire le temps de recherche dans la table de hachage (génération en utilisant un chaînage séparé), mais en même temps, je ne veux pas que le temps d'insertion augmente. Pour mon projet, je ne peux pas changer la fonction de hachage pour réduire les collisions. Mais en raison de l'évolutivité, des collisions se produisent. J'essaie de trouver un moyen de contourner le problème, afin que je puisse en quelque sorte travailler avec le meilleur accès et insérer le temps en cas de collision ... c'est-à-dire pour gérer l'état actuel des choses plutôt que pour restructurer l'algorithme entier. S'il ne fonctionne pas, il devra se restructurer. Alors des idées?
Réponses:
Ce que vous demandez est possible compte tenu de vos contraintes.
Une analyse
La force d'une table de hachage est sa vitesse de recherche et d'insertion rapide. Pour obtenir cette vitesse, il faut renoncer à tout semblant d'ordre dans le tableau: les entrées sont toutes mélangées. Une liste est acceptable à utiliser comme entrée de table car bien que la traversée soit O (n), les listes ont tendance à être courtes en supposant que la table de hachage est suffisamment grande et que les objets stockés dans la table sont hachés à l'aide d'un algorithme de hachage de bonne qualité.
Un arbre de recherche binaire (BST) a une insertion et une recherche rapides sur O (log 2 n). Il impose également une restriction sur les éléments qu'il stocke: il doit y avoir un moyen de classer les éléments. Étant donné deux éléments A et B stockés dans l'arborescence, il doit être possible de déterminer si A précède B ou s'ils ont un ordre équivalent.
Une table de hachage n'impose aucune restriction de ce type: les éléments d'une table de hachage doivent avoir deux propriétés. Premièrement, il doit y avoir un moyen de déterminer si elles sont équivalentes; deuxièmement, il doit exister un moyen de calculer un code de hachage déterministe. La commande n'est pas une exigence.
Si vos éléments de table de hachage ont une commande, vous pouvez utiliser un BST comme entrée de table de hachage pour contenir des objets avec le même code de hachage (collisions). Cependant, en raison d'un BST ayant une recherche et une insertion O (log 2 n), cela signifie que le pire des cas pour la structure entière (table de hachage plus BST) est techniquement meilleur que d'utiliser une liste comme entrée de table. Selon l'implémentation de BST, il faudra plus de stockage qu'une liste, mais probablement pas beaucoup plus.
Veuillez noter que normalement le surcoût et le comportement d'un BST n'apportent rien à la table dans des situations du monde réel comme des compartiments de table de hachage, c'est pourquoi les mauvaises performances théoriques d'une liste sont acceptables. En d'autres termes, la table de hachage compense la faiblesse de la liste en plaçant moins d'éléments dans chaque liste (compartiment). Cependant : le problème indiquait spécifiquement que la table de hachage ne peut pas augmenter en taille, et les collisions sont plus fréquentes que ce qui est typique dans une table de hachage.
la mise en oeuvre
Je ne vais pas mettre de code ici car honnêtement ce n'est pas vraiment nécessaire et vous n'avez pas donné de langue de toute façon.
Ce que je ferais, c'est simplement copier la table de hachage standard que contient la bibliothèque standard de votre langue dans une nouvelle classe, puis changer le type de compartiment de table d'une liste à un arbre. Selon la langue et sa bibliothèque standard, cela peut être une chose très triviale à faire.
Normalement, je ne recommanderais pas le copier-coller du codage comme celui-ci. Cependant, c'est un moyen facile d'obtenir une structure de données testée au combat très rapidement.
la source
L'utilisation d'un arbre binaire pour la gestion des collisions dans une table de hachage n'est pas seulement possible - cela a été fait.
Walter Bright est surtout connu comme l'inventeur du langage de programmation D , mais a également écrit une variante ECMAScript appelée DMDScript . Dans le passé, une revendication principale de DMDScript (ou peut-être un ancêtre - je semble me souvenir du nom DScript) était que ses tables de hachage avaient tendance à surpasser celles de beaucoup de langues similaires. La raison - la gestion des collisions à l'aide d'arbres binaires.
Je ne me souviens pas exactement d'où cela vient, mais les arbres utilisés étaient des arbres binaires naïfs, sans schéma d'équilibre partiel (pas AVL, rouge-noir ou autre), ce qui est logique car en supposant que la table de hachage elle-même est redimensionnée lorsqu'elle devient trop pleine et vous n'obtenez pas des taux de collisions de hachage incroyablement improbables, les arbres binaires doivent toujours être petits. Fondamentalement, le pire des cas est toujours le même que l'utilisation d'une liste chaînée pour la gestion des collisions (sauf que vous payez le prix de deux pointeurs par nœud au lieu d'un), mais le cas moyen réduit la quantité de recherche dans chaque compartiment de hachage.
la source