Tables de hachage et dictionnaires - Historique des versions

Morgane farez : /* Première approche des fonctions de hachage */

2023-05-25T14:26:11Z

Première approche des fonctions de hachage

← Version précédente		Version du 25 mai 2023 à 14:26
Ligne 19 :		Ligne 19 :
	Par exemple la fonction ci-contre n’est pas une bonne fonction de hachage car :		Par exemple la fonction ci-contre n’est pas une bonne fonction de hachage car :
	*La table de hachage apparait dans la fonction, or la fonction de hachage doit en être '''indépendante'''.		*La table de hachage apparait dans la fonction, or la fonction de hachage doit en être '''indépendante'''.
	*Le ‘else’ permet d’associer un entier à une chaine de caractère : l’indice est la somme de chaque caractère de la chaine transformée en son numéro ASCII puis multipliée par sa position dans la chaine. Ainsi, chacun des premiers ~~caractère~~ des chaines ne sont pas pris en compte dans la somme (multiplication par 0) donc les chaines d’un caractère ont toutes pour indice 0 de la même façon, ‘mot’, ‘lot’, ‘got’ ont le même indice, etc…		*Le ‘else’ permet d’associer un entier à une chaine de caractère : l’indice est la somme de chaque caractère de la chaine transformée en son numéro ASCII puis multipliée par sa position dans la chaine. Ainsi, chacun des premiers caractères des chaines ne sont pas pris en compte dans la somme (multiplication par 0) donc les chaines d’un caractère ont toutes pour indice 0 de la même façon, ‘mot’, ‘lot’, ‘got’ ont le même indice, etc…
	*Pour ce qui est des entiers, tous les nombres entiers multiples de la taille de la table auront le même indice. La répartition des positions n’est pas suffisamment homogène.		*Pour ce qui est des entiers, tous les nombres entiers multiples de la taille de la table auront le même indice. La répartition des positions n’est pas suffisamment homogène.

Morgane farez : /* Espace libre et ajout d’un élément */

2023-05-25T14:25:05Z

Espace libre et ajout d’un élément

← Version précédente		Version du 25 mai 2023 à 14:25
Ligne 80 :		Ligne 80 :
	Après plusieurs tests en faisant varier la marge et l’augmentation de la taille, doubler la capacité de la table lorsque les deux tiers de sa taille sont occupés, est un compromis d’optimisation raisonnable. L’espace vide n’est pas gaspillé de manière excessive et le nombre de collisions n’est pas trop élevé. <br>		Après plusieurs tests en faisant varier la marge et l’augmentation de la taille, doubler la capacité de la table lorsque les deux tiers de sa taille sont occupés, est un compromis d’optimisation raisonnable. L’espace vide n’est pas gaspillé de manière excessive et le nombre de collisions n’est pas trop élevé. <br>

	Lors de l'ajout d'un élément il faudra parcourir la table afin de respecter l'unicité de la clé. Si celle-ci est déjà présente dans la table, alors seule la valeur associée sera ~~mis~~ à jour, sinon il faut ajouter le couple à la table en suivant la méthode de [https://www.lama.univ-savoie.fr/mediawiki/index.php/Tables_de_hachage_et_dictionnaires#Gestion_des_collisions gestion de collisions] utilisé.		Lors de l'ajout d'un élément il faudra parcourir la table afin de respecter l'unicité de la clé. Si celle-ci est déjà présente dans la table, alors seule la valeur associée sera mise à jour, sinon il faut ajouter le couple à la table en suivant la méthode de [https://www.lama.univ-savoie.fr/mediawiki/index.php/Tables_de_hachage_et_dictionnaires#Gestion_des_collisions gestion de collisions] utilisé.

	==== Suppression d’un élément ====		==== Suppression d’un élément ====

Morgane farez : /* Double Hachage */

2023-05-25T14:23:02Z

Double Hachage

← Version précédente		Version du 25 mai 2023 à 14:23
Ligne 136 :		Ligne 136 :

	==== Double Hachage ====		==== Double Hachage ====
	Le double hachage ([https://en.wikipedia.org/wiki/Double_hashing double hashing]) consiste à créer deux fonctions de hachage '''indépendantes'''. La valeur de hachage d’une clé est calculée par les deux fonctions puis, le couple sera placé où il y a le moins de collisions parmi les deux propositions. Cette version permet en théorie de réduire la taille des listes de collisions. Cette méthode est souvent ~~combiné~~ à l'adressage fermé afin de réduire la taille des sous-tableaux.		Le double hachage ([https://en.wikipedia.org/wiki/Double_hashing double hashing]) consiste à créer deux fonctions de hachage '''indépendantes'''. La valeur de hachage d’une clé est calculée par les deux fonctions puis, le couple sera placé où il y a le moins de collisions parmi les deux propositions. Cette version permet en théorie de réduire la taille des listes de collisions. Cette méthode est souvent combinée à l'adressage fermé afin de réduire la taille des sous-tableaux.

	=== Recherche d’un élément===		=== Recherche d’un élément===

Morgane farez : /* Adressage fermé */

2023-05-25T14:22:29Z

Adressage fermé

← Version précédente		Version du 25 mai 2023 à 14:22
Ligne 109 :		Ligne 109 :
	L’adressage fermé consiste à créer une chaine d’éléments de façon externe à la table. Pour le cas de Hash1, la table de hachage est un tableau de tableaux, ainsi il est possible d’insérer plusieurs couples au sein de chacun des sous-tableaux.		L’adressage fermé consiste à créer une chaine d’éléments de façon externe à la table. Pour le cas de Hash1, la table de hachage est un tableau de tableaux, ainsi il est possible d’insérer plusieurs couples au sein de chacun des sous-tableaux.

	Pour rechercher la valeur ~~associé~~ à une clé, il faut :		Pour rechercher la valeur associée à une clé, il faut :
	* Calculer la valeur de hachage de la clé		* Calculer la valeur de hachage de la clé
	* Réduire cette valeur pour obtenir un indice		* Réduire cette valeur pour obtenir un indice

Morgane farez : /* Adressage fermé */

2023-05-25T14:22:13Z

Adressage fermé

← Version précédente		Version du 25 mai 2023 à 14:22
Ligne 113 :		Ligne 113 :
	* Réduire cette valeur pour obtenir un indice		* Réduire cette valeur pour obtenir un indice
	* Effectuer un accès au sous-tableau se trouvant à l'indice obtenu, calcul de complexité <math>O(1)</math>		* Effectuer un accès au sous-tableau se trouvant à l'indice obtenu, calcul de complexité <math>O(1)</math>
	* Parcourir le sous-tableau de façon linéaire afin de comparer la clé ~~demandé~~ avec celles présentes dans le sous-tableau, calcul de complexité <math>O(m)</math> avec m la taille du sous-tableau		* Parcourir le sous-tableau de façon linéaire afin de comparer la clé demandée avec celles présentes dans le sous-tableau, calcul de complexité <math>O(m)</math> avec m la taille du sous-tableau
	* Récupérer la valeur et la renvoyer		* Récupérer la valeur et la renvoyer
	<br>		<br>

Morgane farez : /* Raccourcis utilisateur */

2023-05-25T14:18:25Z

Raccourcis utilisateur

← Version précédente		Version du 25 mai 2023 à 14:18
Ligne 164 :		Ligne 164 :
	=== Raccourcis utilisateur ===		=== Raccourcis utilisateur ===

	Pour effectuer une action sur une table, il est nécessaire d’appeler une méthode. En python, lors de l’utilisation des dictionnaires, il existe plusieurs raccourcis pour l’insertion, suppression et recherche d’un élément. Il est possible de redéfinir ces raccourcis pour qu’ils correspondent à une des méthodes des tables de hachage en renvoyant vers les méthodes ~~écrites~~ précédemment. <br>		Pour effectuer une action sur une table, il est nécessaire d’appeler une méthode. En python, lors de l’utilisation des dictionnaires, il existe plusieurs raccourcis pour l’insertion, suppression et recherche d’un élément. Il est possible de redéfinir ces raccourcis pour qu’ils correspondent à une des méthodes des tables de hachage en renvoyant vers les méthodes décrites précédemment. <br>
	Raccourcis possibles :		Raccourcis possibles :

Morgane farez : /* Invariants de boucles */

2023-05-25T14:17:33Z

Invariants de boucles

← Version précédente		Version du 25 mai 2023 à 14:17
Ligne 158 :		Ligne 158 :
	Ce sont des '''propriétés qui restent vraies''' à n’importe quel moment de la boucle. Par exemple pour compter le nombre d’occurrences de chaque caractère dans un texte, il est possible de créer un invariant de boucle qui vérifie si le nombre d’éléments inséré dans la table correspond au nombre d’éléments différents relevés.		Ce sont des '''propriétés qui restent vraies''' à n’importe quel moment de la boucle. Par exemple pour compter le nombre d’occurrences de chaque caractère dans un texte, il est possible de créer un invariant de boucle qui vérifie si le nombre d’éléments inséré dans la table correspond au nombre d’éléments différents relevés.
	<br>		<br>
	En python, les invariants de boucles peuvent se traduire par l’utilisation du assert qui permet d’arrêter l’exécution du programme dès qu’une propriété n’est pas vérifiée.		En python, les invariants de boucles peuvent se traduire par l’utilisation d' "assert" qui permet d’arrêter l’exécution du programme dès qu’une propriété n’est pas vérifiée.

	== Améliorations pour l'utilisateur ==		== Améliorations pour l'utilisateur ==

Morgane farez : /* Grand nombre d'insertions */

2023-05-25T14:16:38Z

Grand nombre d'insertions

← Version précédente		Version du 25 mai 2023 à 14:16
Ligne 152 :		Ligne 152 :
	En informatique, les tests ont une grande importance. Comme vu précédemment, ils peuvent permettre de prendre une décision quant au choix des valeurs des paramètres, ils permettent également de vérifier le bon fonctionnement du code, des différentes fonctions, etc… <br>		En informatique, les tests ont une grande importance. Comme vu précédemment, ils peuvent permettre de prendre une décision quant au choix des valeurs des paramètres, ils permettent également de vérifier le bon fonctionnement du code, des différentes fonctions, etc… <br>
	Il faut donc vérifier que chacune des méthodes associées aux tables de hachages fonctionnent individuellement, puis qu’il n’y a pas d’incohérence lors de l’utilisation globale. De la même façon les fonctions de hachage peuvent être testées indépendamment des tables. <br>		Il faut donc vérifier que chacune des méthodes associées aux tables de hachages fonctionnent individuellement, puis qu’il n’y a pas d’incohérence lors de l’utilisation globale. De la même façon les fonctions de hachage peuvent être testées indépendamment des tables. <br>
	Les tables de hachage permettent de gérer un grand nombre de données. Il est possible de tester les capacités des tables en parcourant un fichier et répertoriant le nombre d’occurrences de chaque caractère ou chaine de caractères rencontrés dans le fichier. Le retour de cette table peut être conséquent : pour vérifier qu’aucun élément n’a été oublié, il faut ~~d’effectuer~~ la même opération avec les outils proposés par l’éditeur de code. Ici, les dictionnaires python servent de références. Il ne reste plus qu’à comparer les éléments de chacun.		Les tables de hachage permettent de gérer un grand nombre de données. Il est possible de tester les capacités des tables en parcourant un fichier et répertoriant le nombre d’occurrences de chaque caractère ou chaine de caractères rencontrés dans le fichier. Le retour de cette table peut être conséquent : pour vérifier qu’aucun élément n’a été oublié, il faut effectuer la même opération avec les outils proposés par l’éditeur de code. Ici, les dictionnaires python servent de références. Il ne reste plus qu’à comparer les éléments de chacun.

	=== Invariants de boucles ===		=== Invariants de boucles ===

Morgane farez : /* Recherche d’un élément */

2023-05-25T14:11:43Z

Recherche d’un élément

← Version précédente		Version du 25 mai 2023 à 14:11
Ligne 141 :		Ligne 141 :

	Le but est de renvoyer la valeur associée à une clé donnée lorsque celle-ci existe. Pour retrouver le couple, il suffit de calculer la valeur de hachage de la clé. L’accès d’un élément dans un tableau à partir d’un indice a une complexité de <math>O(1)</math>. Comme il est possible que l’élément recherché ne soit pas à l’indice indiqué par la fonction de hachage, il est important de comparer les clés. <br>		Le but est de renvoyer la valeur associée à une clé donnée lorsque celle-ci existe. Pour retrouver le couple, il suffit de calculer la valeur de hachage de la clé. L’accès d’un élément dans un tableau à partir d’un indice a une complexité de <math>O(1)</math>. Comme il est possible que l’élément recherché ne soit pas à l’indice indiqué par la fonction de hachage, il est important de comparer les clés. <br>
	Dans le cas de Hash1, si la clé du premier élément du tableau n’est pas la bonne, alors il faut parcourir ce sous-tableau, la complexité dans le pire des cas est alors de O(n) avec n la taille du sous tableau. <br>		Dans le cas de Hash1, si la clé du premier élément du tableau n’est pas la bonne, alors il faut parcourir ce sous-tableau, la complexité dans le pire des cas est alors de O(n) avec n la taille du sous-tableau. <br>
	Dans le cas de l’utilisation du double hachage avec Hash1 par exemple, les sous-tableaux à parcourir seront plus petits, pratiquement de moitié de taille qu’avec l’utilisation d’une seule fonction de hachage. <br>		Dans le cas de l’utilisation du double hachage avec Hash1 par exemple, les sous-tableaux à parcourir seront plus petits, pratiquement de moitié de taille qu’avec l’utilisation d’une seule fonction de hachage. <br>
	Dans le cas de Hash2, si la clé n’est pas à l’emplacement indiqué, il faut alors parcourir la table en appliquant la même méthode que pour la gestion des collisions utilisée au moment de l’ajout d’élément. <br>		Dans le cas de Hash2, si la clé n’est pas à l’emplacement indiqué, il faut alors parcourir la table en appliquant la même méthode que pour la gestion des collisions utilisée au moment de l’ajout d’élément. <br>

Morgane farez : /* Double Hachage */

2023-05-25T14:06:54Z

Double Hachage

← Version précédente		Version du 25 mai 2023 à 14:06
Ligne 136 :		Ligne 136 :

	==== Double Hachage ====		==== Double Hachage ====
	Le double hachage ([https://en.wikipedia.org/wiki/Double_hashing double hashing]) consiste à créer deux fonctions de hachage '''indépendantes'''. La valeur de hachage d’une clé est calculée par les deux fonctions puis, le couple sera placé où il y a le moins de collisions parmi les deux propositions. Cette version permet en théorie de réduire la taille des listes de collisions.		Le double hachage ([https://en.wikipedia.org/wiki/Double_hashing double hashing]) consiste à créer deux fonctions de hachage '''indépendantes'''. La valeur de hachage d’une clé est calculée par les deux fonctions puis, le couple sera placé où il y a le moins de collisions parmi les deux propositions. Cette version permet en théorie de réduire la taille des listes de collisions. Cette méthode est souvent combiné à l'adressage fermé afin de réduire la taille des sous-tableaux.

	=== Recherche d’un élément===		=== Recherche d’un élément===

Tables de hachage et dictionnaires - Historique des versions

Morgane farez : /* Première approche des fonctions de hachage */

Morgane farez : /* Espace libre et ajout d’un élément */

Morgane farez : /* Double Hachage */

Morgane farez : /* Adressage fermé */

Morgane farez : /* Adressage fermé */

Morgane farez : /* Raccourcis utilisateur */

Morgane farez : /* Invariants de boucles */

Morgane farez : /* Grand nombre d'insertions */

Morgane farez : /* Recherche d’un élément */

Morgane farez : /* Double Hachage */

Morgane farez : /* Première approche des fonctions de hachage */

Morgane farez : /* Espace libre et ajout d’un élément */

Morgane farez : /* Double Hachage */

Morgane farez : /* Adressage fermé */

Morgane farez : /* Adressage fermé */

Morgane farez : /* Raccourcis utilisateur */

Morgane farez : /* Invariants de boucles */

Morgane farez : /* Grand nombre d'insertions */

Morgane farez : /* Recherche d’un élément */

Morgane farez : /* Double Hachage */