{"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\/pt\/2020\/06\/26\/hashmap\/","title":{"rendered":"Tabela hash"},"content":{"rendered":"<p>A tabela hash permite implementar uma estrutura de dados de array associativo (dicion\u00e1rio) com desempenho m\u00e9dio O(1) para opera\u00e7\u00f5es de inser\u00e7\u00e3o, exclus\u00e3o e pesquisa.<\/p>\n<p>Abaixo est\u00e1 um exemplo da implementa\u00e7\u00e3o mais simples de um mapa hash em nodeJS:<\/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>Como funciona? Cuidado com as m\u00e3os:<\/p>\n<ul>\n<li>Dentro do mapa hash h\u00e1 um array<\/li>\n<li>Dentro do elemento array h\u00e1 um ponteiro para o primeiro n\u00f3 da lista vinculada<\/li>\n<li>A mem\u00f3ria \u00e9 alocada para uma matriz de ponteiros (por exemplo, 65.535 elementos)<\/li>\n<li>Eles implementam uma fun\u00e7\u00e3o hash, a chave do dicion\u00e1rio \u00e9 a entrada e na sa\u00edda pode fazer qualquer coisa, mas no final retorna o \u00edndice do elemento do array<\/li>\n<\/ul>\n<p>Como funciona a grava\u00e7\u00e3o:<\/p>\n<ul>\n<li>Na entrada h\u00e1 um par de chaves &#8211; valor<\/li>\n<li>A fun\u00e7\u00e3o hash retorna \u00edndice por chave<\/li>\n<li>Obter um n\u00f3 de lista vinculada de um array por \u00edndice<\/li>\n<li>Verifique se corresponde \u00e0 chave<\/li>\n<li>Se corresponder, substitua o valor<\/li>\n<li>Se n\u00e3o corresponder, passe para o pr\u00f3ximo n\u00f3 at\u00e9 encontrarmos ou encontrarmos um n\u00f3 com a chave necess\u00e1ria.<\/li>\n<li>Se o n\u00f3 ainda n\u00e3o for encontrado, crie-o no final da lista vinculada<\/li>\n<\/ul>\n<p>Como funciona a pesquisa por chave:<\/p>\n<ul>\n<li>Na entrada h\u00e1 um par de chaves &#8211; valor<\/li>\n<li>A fun\u00e7\u00e3o hash retorna \u00edndice por chave<\/li>\n<li>Obter um n\u00f3 de lista vinculada de um array por \u00edndice<\/li>\n<li>Verifique se corresponde \u00e0 chave<\/li>\n<li>Se corresponder, retorne o valor<\/li>\n<li>Se n\u00e3o corresponder, passe para o pr\u00f3ximo n\u00f3 at\u00e9 encontrarmos ou encontrarmos um n\u00f3 com a chave necess\u00e1ria.<\/li>\n<\/ul>\n<p>Por que precisamos de uma lista vinculada dentro de um array? Devido a poss\u00edveis colis\u00f5es ao calcular a fun\u00e7\u00e3o hash. Nesse caso, v\u00e1rios pares de valores-chave diferentes estar\u00e3o localizados no mesmo \u00edndice da matriz, caso em que a lista vinculada \u00e9 percorrida para encontrar a chave necess\u00e1ria.<\/p>\n<h3>Fontes<\/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\/Tabela hash<\/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>C\u00f3digo fonte<\/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>A tabela hash permite implementar uma estrutura de dados de array associativo (dicion\u00e1rio) com desempenho m\u00e9dio O(1) para opera\u00e7\u00f5es de inser\u00e7\u00e3o, exclus\u00e3o e pesquisa. Abaixo est\u00e1 um exemplo da implementa\u00e7\u00e3o mais simples de um mapa hash em nodeJS: Como funciona? Cuidado com as m\u00e3os: Dentro do mapa hash h\u00e1 um array Dentro do elemento array<a class=\"more-link\" href=\"https:\/\/demensdeum.com\/blog\/pt\/2020\/06\/26\/hashmap\/\">Continue reading <span class=\"screen-reader-text\">&#8220;Tabela hash&#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":"pt","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\/pt\/wp-json\/wp\/v2\/posts\/2780","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/comments?post=2780"}],"version-history":[{"count":6,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/2780\/revisions"}],"predecessor-version":[{"id":3909,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/2780\/revisions\/3909"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/media?parent=2780"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/categories?post=2780"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/tags?post=2780"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}