Introdução
Bem-vindo(a) a Armazenando Chaves com Valores Associados em Hash Maps. Este laboratório faz parte do Livro de Rust. Você pode praticar suas habilidades em Rust no LabEx.
Neste laboratório, exploraremos o conceito de hash maps (mapas de hash) e como eles podem ser usados para armazenar chaves com valores associados.
Armazenando Chaves com Valores Associados em Hash Maps
A última das nossas coleções comuns é o hash map (mapa de hash). O tipo HashMap<K, V> armazena um mapeamento de chaves do tipo K para valores do tipo V usando uma função de hashing (função de hash), que determina como ele coloca essas chaves e valores na memória. Muitas linguagens de programação suportam este tipo de estrutura de dados, mas frequentemente usam um nome diferente, como hash, map, object, hash table (tabela de hash), dictionary (dicionário) ou associative array (array associativo), só para citar alguns.
Hash maps são úteis quando você quer procurar dados não usando um índice, como pode fazer com vetores, mas usando uma chave que pode ser de qualquer tipo. Por exemplo, em um jogo, você pode manter o controle da pontuação de cada equipe em um hash map, no qual cada chave é o nome da equipe e os valores são a pontuação de cada equipe. Dado o nome de uma equipe, você pode recuperar sua pontuação.
Vamos analisar a API básica de hash maps nesta seção, mas muitas outras coisas boas estão escondidas nas funções definidas em HashMap<K, V> pela biblioteca padrão. Como sempre, verifique a documentação da biblioteca padrão para mais informações.
Criando um Novo Hash Map
Uma maneira de criar um hash map vazio é usar new e adicionar elementos com insert. Na Listagem 8-20, estamos acompanhando as pontuações de duas equipes cujos nomes são Blue (Azul) e Yellow (Amarelo). A equipe Azul começa com 10 pontos, e a equipe Amarela começa com 50.
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);
Listagem 8-20: Criando um novo hash map e inserindo algumas chaves e valores
Observe que precisamos primeiro use (usar) o HashMap da parte de coleções da biblioteca padrão. Das nossas três coleções comuns, esta é a menos usada, então ela não está incluída nos recursos trazidos para o escopo automaticamente no prelúdio. Hash maps também têm menos suporte da biblioteca padrão; não há uma macro embutida para construí-los, por exemplo.
Assim como os vetores, hash maps armazenam seus dados no heap. Este HashMap tem chaves do tipo String e valores do tipo i32. Como os vetores, hash maps são homogêneos: todas as chaves devem ter o mesmo tipo, e todos os valores devem ter o mesmo tipo.
Acessando Valores em um Hash Map
Podemos obter um valor do hash map fornecendo sua chave ao método get, como mostrado na Listagem 8-21.
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);
let team_name = String::from("Blue");
let score = scores.get(&team_name).copied().unwrap_or(0);
Listagem 8-21: Acessando a pontuação da equipe Azul armazenada no hash map
Aqui, score terá o valor que está associado à equipe Azul, e o resultado será 10. O método get retorna um Option<&V>; se não houver valor para essa chave no hash map, get retornará None. Este programa lida com o Option chamando copied para obter um Option<i32> em vez de um Option<&i32>, e então unwrap_or para definir score como zero se scores não tiver uma entrada para a chave.
Podemos iterar sobre cada par chave-valor em um hash map de maneira semelhante à que fazemos com vetores, usando um loop for:
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);
for (key, value) in &scores {
println!("{key}: {value}");
}
Este código imprimirá cada par em uma ordem arbitrária:
Yellow: 50
Blue: 10
Hash Maps e Propriedade (Ownership)
Para tipos que implementam o trait Copy, como i32, os valores são copiados para o hash map. Para valores próprios (owned values) como String, os valores serão movidos e o hash map será o proprietário desses valores, como demonstrado na Listagem 8-22.
use std::collections::HashMap;
let field_name = String::from("Favorite color");
let field_value = String::from("Blue");
let mut map = HashMap::new();
map.insert(field_name, field_value);
// field_name and field_value are invalid at this point, try
// using them and see what compiler error you get!
Listagem 8-22: Mostrando que as chaves e os valores são de propriedade do hash map assim que são inseridos
Não podemos usar as variáveis field_name e field_value depois que elas foram movidas para o hash map com a chamada para insert.
Se inserirmos referências a valores no hash map, os valores não serão movidos para o hash map. Os valores aos quais as referências apontam devem ser válidos por pelo menos o tempo que o hash map for válido. Falaremos mais sobre esses problemas em "Validando Referências com Lifetimes".
Atualizando um Hash Map
Embora o número de pares chave-valor seja expansível, cada chave única pode ter apenas um valor associado a ela por vez (mas não o contrário: por exemplo, tanto a equipe Azul quanto a equipe Amarela podem ter o valor 10 armazenado no hash map scores).
Quando você deseja alterar os dados em um hash map, você precisa decidir como lidar com o caso em que uma chave já tem um valor atribuído. Você pode substituir o valor antigo pelo novo valor, desconsiderando completamente o valor antigo. Você pode manter o valor antigo e ignorar o novo valor, adicionando o novo valor somente se a chave não já tiver um valor. Ou você pode combinar o valor antigo e o novo valor. Vamos ver como fazer cada um desses!
Sobrescrevendo um Valor
Se inserirmos uma chave e um valor em um hash map e, em seguida, inserirmos a mesma chave com um valor diferente, o valor associado a essa chave será substituído. Embora o código na Listagem 8-23 chame insert duas vezes, o hash map conterá apenas um par chave-valor porque estamos inserindo o valor para a chave da equipe Azul em ambas as vezes.
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Blue"), 25);
println!("{:?}", scores);
Listagem 8-23: Substituindo um valor armazenado com uma chave específica
Este código imprimirá {"Blue": 25}. O valor original de 10 foi sobrescrito.
Adicionando uma Chave e Valor Somente se uma Chave Não Estiver Presente
É comum verificar se uma chave específica já existe no hash map com um valor e, em seguida, tomar as seguintes ações: se a chave existir no hash map, o valor existente deve permanecer como está; se a chave não existir, insira-a e um valor para ela.
Hash maps têm uma API especial para isso chamada entry que recebe a chave que você deseja verificar como um parâmetro. O valor de retorno do método entry é um enum chamado Entry que representa um valor que pode ou não existir. Digamos que queremos verificar se a chave para a equipe Amarela tem um valor associado a ela. Se não tiver, queremos inserir o valor 50, e o mesmo para a equipe Azul. Usando a API entry, o código se parece com a Listagem 8-24.
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.entry(String::from("Yellow")).or_insert(50);
scores.entry(String::from("Blue")).or_insert(50);
println!("{:?}", scores);
Listagem 8-24: Usando o método entry para inserir somente se a chave já não tiver um valor
O método or_insert em Entry é definido para retornar uma referência mutável ao valor para a chave Entry correspondente se essa chave existir e, se não, ele insere o parâmetro como o novo valor para esta chave e retorna uma referência mutável ao novo valor. Essa técnica é muito mais limpa do que escrever a lógica nós mesmos e, além disso, funciona melhor com o verificador de empréstimo (borrow checker).
A execução do código na Listagem 8-24 imprimirá {"Yellow": 50, "Blue": 10}. A primeira chamada para entry inserirá a chave para a equipe Amarela com o valor 50 porque a equipe Amarela não tem um valor já. A segunda chamada para entry não alterará o hash map porque a equipe Azul já tem o valor 10.
Atualizando um Valor com Base no Valor Antigo
Outro caso de uso comum para hash maps é procurar o valor de uma chave e, em seguida, atualizá-lo com base no valor antigo. Por exemplo, a Listagem 8-25 mostra o código que conta quantas vezes cada palavra aparece em algum texto. Usamos um hash map com as palavras como chaves e incrementamos o valor para acompanhar quantas vezes vimos essa palavra. Se for a primeira vez que vemos uma palavra, primeiro inseriremos o valor 0.
use std::collections::HashMap;
let text = "hello world wonderful world";
let mut map = HashMap::new();
for word in text.split_whitespace() {
let count = map.entry(word).or_insert(0);
*count += 1;
}
println!("{:?}", map);
Listagem 8-25: Contando ocorrências de palavras usando um hash map que armazena palavras e contagens
Este código imprimirá {"world": 2, "hello": 1, "wonderful": 1}. Você pode ver os mesmos pares chave-valor impressos em uma ordem diferente: lembre-se de "Acessando Valores em um Hash Map" que a iteração sobre um hash map acontece em uma ordem arbitrária.
O método split_whitespace retorna um iterador sobre subslices, separados por espaços em branco, do valor em text. O método or_insert retorna uma referência mutável (&mut V) ao valor para a chave especificada. Aqui, armazenamos essa referência mutável na variável count, então, para atribuir a esse valor, devemos primeiro desreferenciar count usando o asterisco (*). A referência mutável sai do escopo no final do loop for, então todas essas alterações são seguras e permitidas pelas regras de empréstimo (borrowing rules).
Funções de Hashing
Por padrão, HashMap usa uma função de hashing chamada SipHash que pode fornecer resistência a ataques de negação de serviço (DoS) envolvendo tabelas hash. Este não é o algoritmo de hashing mais rápido disponível, mas a troca por melhor segurança que vem com a queda no desempenho vale a pena. Se você fizer o perfil do seu código e descobrir que a função hash padrão é muito lenta para seus propósitos, você pode mudar para outra função especificando um hasher diferente. Um hasher é um tipo que implementa o trait BuildHasher. Falaremos sobre traits e como implementá-los no Capítulo 10. Você não precisa necessariamente implementar seu próprio hasher do zero; https://crates.io tem bibliotecas compartilhadas por outros usuários do Rust que fornecem hashers implementando muitos algoritmos de hashing comuns.
Resumo
Parabéns! Você concluiu o laboratório Armazenando Chaves com Valores Associados em Hash Maps. Você pode praticar mais laboratórios no LabEx para aprimorar suas habilidades.