Explication sur le hachage et son utilisation pour la compression de données

Question

Je suis confronté à une application qui utilise le hachage, mais je ne peux toujours pas comprendre comment cela fonctionne. Voici mon problème, le hachage est utilisé pour générer un index, et avec ces index, j’accède à différentes tables, et ensuite j’ajoute la valeur de chaque table que j’obtiens en utilisant les index et avec lequel j’obtiens ma valeur finale. Ceci est fait pour réduire les besoins en mémoire. L’entrée de la fonction de hachage fait le XOR entre un nombre constant aléatoire et certains paramètres de l’application.

Est-ce une application de hachage typique ?. Ce que je ne comprends pas, c'est comment utiliser le hachage peut-on réduire les besoins en mémoire ?. Quelqu'un peut-il clarifier cela?.

Merci

Answer 1

Le hachage seul n’a rien à voir avec la mémoire.

Ce qui est souvent utilisé est une table de hachage. Les tables de hachage fonctionnent en calculant le hachage de ce que vous saisissez, qui est ensuite utilisé comme index dans une structure de données.

Le hachage vous permet de réduire la clé (chaîne, etc.) à une valeur plus compacte, telle qu'un entier ou un ensemble de bits.

Cela pourrait être les économies de mémoire dont vous parlez - réduire une grande clé en un simple entier.

Notez cependant que les hachages ne sont pas uniques! Un bon algorithme de hachage minimise les collisions mais ne vise pas à réduire à une valeur unique - cela n’est pas possible (par exemple, si votre hachage génère un entier de 32 bits, votre hachage n’aurait que 2 ^ 32 valeurs uniques).

Answer 2

S'agit-il d'un filtre de bloom ? Ceci utilise des fonctions de hachage pour obtenir un moyen efficace de tester l’appartenance à un ensemble. Si oui, voir le lien pour une explication.

Answer 3

La plupart des bonnes implémentations de hachage sont inefficaces en termes de mémoire. Sinon, l'informatique impliquerait davantage d'informatique - et ce serait justement manquer le point de hachage.

Les implémentations de hachage sont utilisées pour l'efficacité du traitement, car elles vous fournissent un temps d'exécution constant pour des opérations telles que l'insertion, le retrait et la récupération.

Vous pouvez penser à la qualité du hachage de manière à ce que toutes vos données, quel que soit leur type ou leur taille, soient toujours représentées dans un seul formulaire de longueur fixe.

Answer 4

Cela pourrait s’expliquer si le hachage effectué n’est pas destiné à construire une table de hachage réelle, mais consiste simplement à créer un index dans une table de bloc chaîne / mémoire. Si vous aviez la même chaîne (ou la même séquence mémoire) 20 fois dans vos données et que vous remplaciez ensuite les 20 occurrences de cette chaîne par son index hachage / table uniquement, vous pourriez obtenir une compression des données de cette façon. Cependant, si ce tableau contient une chaîne de collisions pour chaque valeur de hachage, ce que je viens de décrire n’est pas ce qui se passe; dans ce cas, la raison du hachage serait probablement d’accélérer l’exécution (en fournissant un accès rapide aux valeurs stockées), plutôt que par la compression.