Armazenamento de chaves com valores associados em mapas de hash

A última de nossas coleções comuns é o mapa hash. O tipo HashMap<K, V> armazena um mapeamento de chaves de tipo K para valores de tipo V. Ele faz isso por meio de uma função hash, que determina como ele coloca essas chaves e valores na memória. Muitas linguagens de programação suportam esse tipo de estrutura de dados, mas geralmente usam um nome diferente, como hash, mapa, objeto, tabela hash, dicionário ou matriz associativa, apenas para citar alguns.

Os mapas hash são úteis quando você deseja pesquisar dados não usando um índice, como você pode fazer com vetores, mas usando uma chave que pode ser de qualquer tipo. Por exemplo, em um jogo, você pode acompanhar a pontuação de cada equipe em um mapa hash no qual cada chave é o nome de uma equipe e os valores são a pontuação de cada equipe. Dado o nome de uma equipe, você pode recuperar sua pontuação.

Examinaremos a API básica de mapas hash nesta seção, mas muitos outros recursos estão escondidos nas funções definidas em HashMap<K, V> pela biblioteca padrão. Como sempre, verifique a documentação da biblioteca padrão para obter mais informações.

Criando um Novo Mapa Hash

Você pode criar um mapa hash vazio com new e adicionar elementos com insert. Na Listagem 8-20, estamos acompanhando as pontuações de duas equipes cujos nomes são Azul e Amarelo. O time Azul começa com 10 pontos, e o time Amarelo começa com 50.

fn main() {
    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 mapa de hash e inserindo algumas chaves e valores

Observe que primeiro precisamos usar o HashMap da porção de coleções da biblioteca padrão. De nossas três coleções comuns, esta é a menos usada, portanto, não está incluída nos recursos trazidos ao escopo automaticamente no prelúdio. Os mapas hash também têm menos suporte da biblioteca padrão; não há macro embutida para construí-los, por exemplo.

Assim como os vetores, os mapas hash armazenam seus dados no heap. Esse HashMap tem chaves de tipo String e valores de tipo i32. Como os vetores, os mapas hash são homogêneos: todas as chaves devem ter o mesmo tipo e todos os valores devem ter o mesmo tipo.

Outra maneira de construir um mapa hash é usando iteradores e o método collect em um vetor de tuplas, onde cada tupla consiste em uma chave e seu valor. Entraremos em mais detalhes sobre os iteradores e seus métodos associados na seção “Processando uma série de itens com iteradores” do Capítulo 13. O método collect reúne dados em vários tipos de coleção, incluindo HashMap. Por exemplo, se tivéssemos os nomes dos times e pontuações iniciais em dois vetores separados, poderíamos usar o método zip para criar um vetor de tuplas onde “Azul” é pareado com 10 e assim por diante. Então, poderíamos usar o método collect para transformar esse vetor de tuplas em um mapa hash, conforme mostrado na Listagem 8-21.

fn main() {
    use std::collections::HashMap;

    let teams = vec![String::from("Blue"), String::from("Yellow")];
    let initial_scores = vec![10, 50];

    let mut scores: HashMap<_, _> =
        teams.into_iter().zip(initial_scores.into_iter()).collect();
}

Listagem 8-21: Criando um mapa hash de uma lista de equipes e uma lista de pontuações

A anotação de tipo HashMap<_, _> é necessária aqui porque é possível collect entrar em muitas estruturas de dados diferentes e Rust não sabe qual você deseja, a menos que você especifique. Para os parâmetros dos tipos de chave e valor, no entanto, usamos sublinhados e Rust pode inferir os tipos que o mapa de hash contém com base nos tipos de dados nos vetores. Na Listagem 8-21, o tipo de chave será String e o tipo de valor será i32, exatamente como os tipos eram na Listagem 8-20.

Mapas Hash e propriedade

Para tipos que implementam a característica Copy, como i32, os valores são copiados para o mapa hash. Para valores de propriedade como String, os valores serão movidos e o mapa de hash será o proprietário desses valores, conforme demonstrado na Listagem 8-22.

fn main() {
    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 e field_value são inválidos nesse ponto, tente usalos e
    // veja que erro você recebe
}

Listagem 8-22: Mostrando que as chaves e valores são de propriedade do mapa hash, uma vez que são inseridos

Não podemos usar as variáveis field_name e field_value depois que elas forem movidas para o mapa hash com a chamada para insert.

Se inserirmos referências a valores no mapa hash, os valores não serão movidos para o mapa hash. Os valores para os quais as referências apontam devem ser válidos pelo menos enquanto o mapa de hash for válido. Falaremos mais sobre esses problemas na seção “Validando referências com tempos de vida” no Capítulo 10.

Acessando Valores em um Mapa Hash

Podemos obter um valor do mapa de hash fornecendo sua chave para o método get, conforme mostrado na Listagem 8-23.

fn main() {
    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);
}

Listagem 8-23: Acessando a pontuação da equipe Blue armazenada no mapa hash

Aqui, score terá o valor que está associado ao time Blue, e o resultado será Some(&10). O resultado é agrupado em Some porque get retorna um Option<&V>; se não houver valor para essa chave no mapa hash, get retornará None. O programa precisará lidar com a Opção (Option) de uma das maneiras que abordamos no Capítulo 6.

Podemos iterar sobre cada par de chave / valor em um mapa hash de maneira semelhante à que fazemos com vetores, usando um loop for:

fn main() {
    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

Atualizando um Hash Map

Embora o número de chaves e valores possam ser aumentados, cada chave pode ter apenas um valor associado a ela por vez. Quando você deseja alterar os dados em um mapa hash, você deve decidir como lidar com o caso em que uma chave já possui um valor atribuído. Você pode substituir o valor antigo pelo novo valor, desconsiderando completamente o valor antigo. Você poderia manter o valor antigo e ignorar o novo valor, apenas adicionando o novo valor se a chave ainda não tiver um valor. Ou você pode combinar o valor antigo e o novo valor. Vejamos como fazer cada um deles!

Sobrescrever um valor

Se inserirmos uma chave e um valor em um mapa de hash e, em seguida, inserirmos a mesma chave com um valor diferente, o valor associado a essa chave será substituído. Mesmo que o código na Listagem 8-24 chame insert duas vezes, o mapa de hash conterá apenas um par de chave / valor porque estamos inserindo o valor para a chave da equipe Blue nas duas vezes.

fn main() {
    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-24: Substituindo um valor armazenado por uma chave específica

Este código imprimirá {"Blue": 25}. O valor original de 10 foi substituído.

Inserindo apenas um valor se a chave não tiver valor

É comum verificar se uma determinada chave tem um valor e, se não tiver, inserir um valor para ela. Os mapas hash têm uma API especial para isso chamada, entry que usa a chave que você deseja verificar como 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 da equipe amarela tem um valor associado a ela. Caso contrário, 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-25.

fn main() {
    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-25: Usando o método entry para inserir apenas se a chave ainda não tiver um valor

O método or_insert em Entry é definido para retornar uma referência mutável ao valor da chave Entry correspondente se essa chave existir e, caso não exista, 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 mais bem com o verificador de empréstimo.

A execução do código na Listagem 8-25 será impressa {"Yellow": 50, "Blue": 10}. A primeira chamada para entry irá inserir a chave para o time Amarelo com o valor 50 porque o time Amarelo ainda não tem um valor. A segunda chamada para entry não mudará o hash map porque a equipe Blue já tem o valor 10.

Atualizando um valor com base no valor antigo

Outro caso de uso comum para mapas de hash é pesquisar o valor de uma chave e atualizá-lo com base no valor antigo. Por exemplo, a Listagem 8-26 mostra o código que conta quantas vezes cada palavra aparece em algum texto. Usamos um mapa hash com as palavras como chaves e incrementamos o valor para controlar quantas vezes vimos essa palavra. Se for a primeira vez que vimos uma palavra, primeiro inseriremos o valor 0.

fn main() {
    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-26: Contando ocorrências de palavras usando um mapa hash que armazena palavras e contagens

Este código será impresso {"world": 2, "hello": 1, "wonderful": 1}. O método or_insert realmente retorna uma referência mutável ( &mut V) para o valor desta chave. Aqui, armazenamos essa referência mutável na variável count, portanto, 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, portanto, todas essas alterações são seguras e permitidas pelas regras de empréstimo.

Funções de hash

Por padrão, HashMap usa uma função de hashing “criptograficamente forte” que pode oferecer resistência a ataques de negação de serviço (DoS). Este não é o algoritmo de hash mais rápido disponível, mas a compensação por melhor segurança que vem com a queda no desempenho vale a pena. Se você analisar seu código e descobrir que a função hash padrão é muito lenta para seus propósitos, você pode alternar para outra função especificando um hasher diferente. Um hasher é um tipo que implementa o traço BuildHasher. Falaremos sobre características e como implementá-las no Capítulo 10. Você não precisa necessariamente implementar seu próprio hasher do zero; crates.io tem bibliotecas compartilhadas por outros usuários do Rust que fornecem hashers que implementam muitos algoritmos de hash comuns.

Resumo

Vetores, strings e mapas hash fornecerão uma grande quantidade de funcionalidade necessária em programas quando você precisar armazenar, acessar e modificar dados. Aqui estão alguns exercícios que você deve estar preparado para resolver:

• Dada uma lista de inteiros, use um vetor e retorne a média (o valor médio), a mediana (quando classificado, o valor na posição intermediária) e o modo (o valor que ocorre com mais frequência; um mapa hash será útil aqui) da lista.
• Converta strings em latim pig. A primeira consoante de cada palavra é movida para o final da palavra e "ay" é adicionado, então "primeiro" se torna "primeiro-fay". Palavras que começam com uma vogal têm “feno” adicionado ao final (“maçã” torna-se “maçã-feno”). Lembre-se dos detalhes sobre a codificação UTF-8!
• Usando um mapa hash e vetores, crie uma interface de texto para permitir que um usuário adicione nomes de funcionários a um departamento de uma empresa. Por exemplo, “Adicionar Sally à Engenharia” ou “Adicionar Amir às Vendas”. Em seguida, deixe o usuário recuperar uma lista de todas as pessoas em um departamento ou todas as pessoas na empresa por departamento, classificadas em ordem alfabética.

A documentação da API da biblioteca padrão descreve métodos que vetores, strings e mapas hash têm que serão úteis para esses exercícios!

Estamos entrando em programas mais complexos nos quais as operações podem falhar, portanto, é o momento perfeito para discutir o tratamento de erros. Faremos isso a seguir!

Traduzido por Acervo Lima. O original pode ser acessado aqui.

Licença

• Apache License, Version 2.0
• MIT license

<< Anterior Próximo >>