| dbo:abstract
|
- Une table de hachage est, en informatique, une structure de données qui permet une association clé–valeur, c'est-à-dire une implémentation du type abstrait tableau associatif.Son but principal est de permettre de retrouver une clé donnée très rapidement, en la cherchant à un emplacement de la table correspondant au résultat d'une fonction de hachage calculée en O(1). Cela constitue un gain de temps très important pour les grosses tables, lors d'une recherche ou d'un besoin d'accès aux données en utilisant la clé définie. Il s'agit d'un tableau ne comportant pas d'ordre (contrairement à un tableau ordinaire qui est indexé par des entiers).On accède à chaque valeur du tableau par sa clé, qui transformée par une fonction de hachage en une valeur de hachage (un nombre) indexe les éléments de la table, ces derniers étant appelés alvéoles (en anglais, buckets ou slots). Le fait de créer une valeur de hachage à partir d'une clé peut engendrer un problème de collision, c’est-à-dire que deux clés différentes, voire davantage, pourront se retrouver associées à la même valeur de hachage et donc à la même alvéole (les fonctions de hachage ne sont pas injectives). Pour diminuer les risques de collisions, il faut donc premièrement choisir avec soin sa fonction de hachage. Ensuite, un mécanisme de résolution des collisions sera à implémenter si nécessaire. Il faudra alors stocker dans les alvéoles la paire clé–valeur et pas uniquement la valeur, afin de pouvoir comparer la clé avec celle qui sera donnée en entrée. Tout comme les tableaux ordinaires, les tables de hachage permettent un accès en O(1) en moyenne, quel que soit le nombre de paires clé–valeur dans la table. Toutefois, comme plusieurs paires clé–valeur peuvent se trouver dans la même alvéole, le temps d'accès dans le pire des cas peut être de O(n). Comparées aux autres tableaux associatifs, les tables de hachage sont surtout utiles lorsque le nombre de paires clé–valeur est très important[réf. nécessaire]. La position des paires clé–valeur dans une table de hachage est pseudo-aléatoire mais dépend de la fonction de hachage choisie et des clés utilisées. Cette structure n'est donc pas adaptée au feuilletage (browsing) de données voisines. Des types de structures de données comme les arbres équilibrés, généralement plus lents (en O(log n)) et un peu plus complexes à implémenter, maintiennent une structure ordonnée. (fr)
- Une table de hachage est, en informatique, une structure de données qui permet une association clé–valeur, c'est-à-dire une implémentation du type abstrait tableau associatif.Son but principal est de permettre de retrouver une clé donnée très rapidement, en la cherchant à un emplacement de la table correspondant au résultat d'une fonction de hachage calculée en O(1). Cela constitue un gain de temps très important pour les grosses tables, lors d'une recherche ou d'un besoin d'accès aux données en utilisant la clé définie. Il s'agit d'un tableau ne comportant pas d'ordre (contrairement à un tableau ordinaire qui est indexé par des entiers).On accède à chaque valeur du tableau par sa clé, qui transformée par une fonction de hachage en une valeur de hachage (un nombre) indexe les éléments de la table, ces derniers étant appelés alvéoles (en anglais, buckets ou slots). Le fait de créer une valeur de hachage à partir d'une clé peut engendrer un problème de collision, c’est-à-dire que deux clés différentes, voire davantage, pourront se retrouver associées à la même valeur de hachage et donc à la même alvéole (les fonctions de hachage ne sont pas injectives). Pour diminuer les risques de collisions, il faut donc premièrement choisir avec soin sa fonction de hachage. Ensuite, un mécanisme de résolution des collisions sera à implémenter si nécessaire. Il faudra alors stocker dans les alvéoles la paire clé–valeur et pas uniquement la valeur, afin de pouvoir comparer la clé avec celle qui sera donnée en entrée. Tout comme les tableaux ordinaires, les tables de hachage permettent un accès en O(1) en moyenne, quel que soit le nombre de paires clé–valeur dans la table. Toutefois, comme plusieurs paires clé–valeur peuvent se trouver dans la même alvéole, le temps d'accès dans le pire des cas peut être de O(n). Comparées aux autres tableaux associatifs, les tables de hachage sont surtout utiles lorsque le nombre de paires clé–valeur est très important[réf. nécessaire]. La position des paires clé–valeur dans une table de hachage est pseudo-aléatoire mais dépend de la fonction de hachage choisie et des clés utilisées. Cette structure n'est donc pas adaptée au feuilletage (browsing) de données voisines. Des types de structures de données comme les arbres équilibrés, généralement plus lents (en O(log n)) et un peu plus complexes à implémenter, maintiennent une structure ordonnée. (fr)
|
| rdfs:comment
|
- Une table de hachage est, en informatique, une structure de données qui permet une association clé–valeur, c'est-à-dire une implémentation du type abstrait tableau associatif.Son but principal est de permettre de retrouver une clé donnée très rapidement, en la cherchant à un emplacement de la table correspondant au résultat d'une fonction de hachage calculée en O(1). Cela constitue un gain de temps très important pour les grosses tables, lors d'une recherche ou d'un besoin d'accès aux données en utilisant la clé définie. (fr)
- Une table de hachage est, en informatique, une structure de données qui permet une association clé–valeur, c'est-à-dire une implémentation du type abstrait tableau associatif.Son but principal est de permettre de retrouver une clé donnée très rapidement, en la cherchant à un emplacement de la table correspondant au résultat d'une fonction de hachage calculée en O(1). Cela constitue un gain de temps très important pour les grosses tables, lors d'une recherche ou d'un besoin d'accès aux données en utilisant la clé définie. (fr)
|
