{"id":2780,"date":"2020-06-26T23:05:47","date_gmt":"2020-06-26T20:05:47","guid":{"rendered":"http:\/\/demensdeum.com\/blog\/?p=2780"},"modified":"2024-12-16T22:32:26","modified_gmt":"2024-12-16T19:32:26","slug":"hashmap","status":"publish","type":"post","link":"https:\/\/demensdeum.com\/blog\/fr\/2020\/06\/26\/hashmap\/","title":{"rendered":"Table de hachage"},"content":{"rendered":"<p>La table de hachage vous permet d&#8217;impl\u00e9menter une structure de donn\u00e9es de tableau associatif (dictionnaire) avec des performances moyennes O(1) pour les op\u00e9rations d&#8217;insertion, de suppression et de recherche.<\/p>\n<p>Vous trouverez ci-dessous un exemple de l&#8217;impl\u00e9mentation la plus simple d&#8217;une carte de hachage dans nodeJS\u00a0:<\/p>\n<p><iframe loading=\"lazy\" src=\"https:\/\/repl.it\/@demensdeum\/VitalGlitteringFrontpage?lite=true\" width=\"100%\" height=\"400px\" frameborder=\"no\" scrolling=\"no\" sandbox=\"allow-forms allow-pointer-lock allow-popups allow-same-origin allow-scripts allow-modals\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>Comment \u00e7a marche\u00a0? Surveillez vos mains\u00a0:<\/p>\n<ul>\n<li>\u00c0 l&#8217;int\u00e9rieur de la carte de hachage se trouve un tableau<\/li>\n<li>\u00c0 l&#8217;int\u00e9rieur de l&#8217;\u00e9l\u00e9ment du tableau se trouve un pointeur vers le premier n\u0153ud de la liste cha\u00een\u00e9e<\/li>\n<li>La m\u00e9moire est allou\u00e9e \u00e0 un tableau de pointeurs (par exemple, 65\u00a0535\u00a0\u00e9l\u00e9ments)<\/li>\n<li>Ils impl\u00e9mentent une fonction de hachage, la cl\u00e9 du dictionnaire est l&#8217;entr\u00e9e, et en sortie elle peut tout faire, mais \u00e0 la fin elle renvoie l&#8217;index de l&#8217;\u00e9l\u00e9ment du tableau<\/li>\n<\/ul>\n<p>Comment fonctionne l&#8217;enregistrement\u00a0:<\/p>\n<ul>\n<li>A l&#8217;entr\u00e9e, il y a une paire de cl\u00e9s &#8211; valeur<\/li>\n<li>La fonction de hachage renvoie l&#8217;index par cl\u00e9<\/li>\n<li>Obtenir un n\u0153ud de liste cha\u00een\u00e9e \u00e0 partir d&#8217;un tableau par index<\/li>\n<li>V\u00e9rifiez si cela correspond \u00e0 la cl\u00e9<\/li>\n<li>Si cela correspond, remplacez la valeur<\/li>\n<li>S&#8217;il ne correspond pas, passez au n\u0153ud suivant jusqu&#8217;\u00e0 ce que nous trouvions ou trouvions un n\u0153ud avec la cl\u00e9 requise.<\/li>\n<li>Si le n\u0153ud n&#8217;est toujours pas trouv\u00e9, cr\u00e9ez-le \u00e0 la fin de la liste cha\u00een\u00e9e<\/li>\n<\/ul>\n<p>Fonctionnement de la recherche par cl\u00e9\u00a0:<\/p>\n<ul>\n<li>A l&#8217;entr\u00e9e, il y a une paire de cl\u00e9s &#8211; valeur<\/li>\n<li>La fonction de hachage renvoie l&#8217;index par cl\u00e9<\/li>\n<li>Obtenir un n\u0153ud de liste cha\u00een\u00e9e \u00e0 partir d&#8217;un tableau par index<\/li>\n<li>V\u00e9rifiez si cela correspond \u00e0 la cl\u00e9<\/li>\n<li>Si cela correspond, renvoyez la valeur<\/li>\n<li>S&#8217;il ne correspond pas, passez au n\u0153ud suivant jusqu&#8217;\u00e0 ce que nous trouvions ou trouvions un n\u0153ud avec la cl\u00e9 requise.<\/li>\n<\/ul>\n<p>Pourquoi avons-nous besoin d&#8217;une liste cha\u00een\u00e9e dans un tableau\u00a0? En raison de collisions possibles lors du calcul de la fonction de hachage. Dans ce cas, plusieurs paires cl\u00e9-valeur diff\u00e9rentes seront situ\u00e9es au m\u00eame index dans le tableau, auquel cas la liste cha\u00een\u00e9e est parcourue pour trouver la cl\u00e9 requise.<\/p>\n<h3>Sources<\/h3>\n<p><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB% D0%B8%D1%86%D0%B0\" target=\"_blank\" rel=\"noopener noreferrer\">https:\/\/ru.wikipedia.org\/wiki\/Hash table<\/a><br \/><a href=\"https:\/\/www.youtube.com\/watch?v=wg8hZxMRwcw\" target=\"_blank\" rel=\"noopener noreferrer\">https:\/\/www.youtube.com\/watch?v=wg8hZxMRwcw<\/a><\/p>\n<h3>Code source<\/h3>\n<p><a href=\"https:\/\/gitlab.com\/demensdeum\/datastructures\" target=\"_blank\" rel=\"noopener noreferrer\">https:\/\/gitlab.com\/demensdeum\/datastructures<\/a><\/p >\n","protected":false},"excerpt":{"rendered":"<p>La table de hachage vous permet d&#8217;impl\u00e9menter une structure de donn\u00e9es de tableau associatif (dictionnaire) avec des performances moyennes O(1) pour les op\u00e9rations d&#8217;insertion, de suppression et de recherche. Vous trouverez ci-dessous un exemple de l&#8217;impl\u00e9mentation la plus simple d&#8217;une carte de hachage dans nodeJS\u00a0: Comment \u00e7a marche\u00a0? Surveillez vos mains\u00a0: \u00c0 l&#8217;int\u00e9rieur de la<a class=\"more-link\" href=\"https:\/\/demensdeum.com\/blog\/fr\/2020\/06\/26\/hashmap\/\">Continue reading <span class=\"screen-reader-text\">&#8220;Table de hachage&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[61,52],"tags":[157,161],"class_list":["post-2780","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-datastructures","tag-hashmap","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"fr","enabled_languages":["en","ru","zh","de","fr","ja","pt","hi"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false},"hi":{"title":false,"content":false,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/2780","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/comments?post=2780"}],"version-history":[{"count":6,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/2780\/revisions"}],"predecessor-version":[{"id":3909,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/2780\/revisions\/3909"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/media?parent=2780"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/categories?post=2780"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/tags?post=2780"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}