Um guia para hashmaps em Python

Quando os profissionais de dados falam sobre armazenamento de dados atualmente, na maioria das vezes, eles se referem ao local onde os dados são armazenados, sejam arquivos locais, bancos de dados SQL ou NoSQL ou a nuvem. No entanto, outro aspecto importante relacionado ao armazenamento de dados é como os dados são armazenados.

A forma de armazenamento de dados geralmente ocorre em um nível mais baixo, no próprio núcleo das linguagens de programação. Isso tem a ver com o design das ferramentas que usamos, e não com a forma de usar essas ferramentas. No entanto, saber como os dados são armazenados é fundamental para entender os mecanismos subjacentes que tornam o trabalho possível. Além disso, esse conhecimento pode nos ajudar a tomar decisões melhores para aprimorar o desempenho da computação.

Se você estiver realmente interessado em hashmaps, bem como em listas vinculadas, pilhas, filas e gráficos, inscreva-se no DataCamp para fazer nosso curso Data Structures and Algorithms in Python.

O que é um Hashmap?

Para definir um hashmap, primeiro precisamos entender o que é hashing. Hashing é o processo de transformar uma determinada chave ou uma cadeia de caracteres em outro valor. O resultado normalmente é um valor mais curto, de comprimento fixo, que facilita o trabalho computacional do que a chave original.

Hashmaps, também conhecidos como hashtables, representam uma das implementações mais comuns de hashing. O Hashmaps armazena pares de valores-chave (por exemplo, ID e nome do funcionário) em uma lista que pode ser acessada por meio de seu índice. Podemos dizer que um hashmap é uma estrutura de dados que utiliza técnicas de hashing para armazenar dados de forma associativa. São estruturas de dados otimizadas que permitem operações de dados mais rápidas, incluindo inserção, exclusão e pesquisa.

A ideia por trás dos hashmaps é distribuir as entradas (pares de chave/valor) em uma matriz de buckets. Dada uma chave, uma função de hashing calculará um índice distinto que sugere onde a entrada pode ser encontrada. O uso de um índice em vez da chave original torna os hashmaps particularmente adequados para várias operações de dados, incluindo inserção, remoção e pesquisa de dados.

Como funciona um hashmap. Imagem do autor

Para calcular o valor de hash, ou simplesmente hash, uma função de hash gera novos valores de acordo com um algoritmo matemático de hash. Como os pares de valores-chave são, em teoria, ilimitados, a função de hash mapeará as chaves com base em um determinado tamanho de tabela.

Há várias funções de hash disponíveis, cada uma delas com seus prós e contras. O principal objetivo de uma função hash é sempre retornar o mesmo valor para a mesma entrada.

Os mais comuns são os seguintes:

• Método de divisão: É a maneira mais simples e rápida de calcular valores de hash. Isso é feito dividindo a chave pelo tamanho da tabela e, em seguida, usando o restante como hash.
• Método Mid Square: Ele encontrará o quadrado da chave fornecida e, em seguida, pegará os dígitos do meio e usará esses dígitos como índice do elemento.
• Método de multiplicação: Ele define o índice de hash a partir da parte fracionária da multiplicação da chave por um número real grande.
• Método de dobragem: Primeiro, a chave é dividida em partes iguais, o resultado é adicionado e o resultado é dividido pelo tamanho da tabela. O hash é o lembrete.

Hashmap em Python

O Python implementa hashmaps por meio do tipo de dados dicionário interno. Assim como os hashmaps, os dicionários armazenam dados em {key:value} pares. Depois que você criar o dicionário (consulte a próxima seção), o Python aplicará uma função de hash conveniente sob o capô para calcular o hash de cada chave.

Os dicionários Python vêm com os seguintes recursos:

• Os dicionários são mutáveis: Isso significa que podemos alterar, adicionar ou remover itens depois que o dicionário for criado.
• Os elementos são ordenados: No Python 3.6 e versões anteriores, os dicionários não eram ordenados, o que significa que os itens não tinham uma ordem definida. Entretanto, após o lançamento do Python 3.7, os dicionários passaram a preservar a ordem. Agora, quando você criar um dicionário Python, as chaves seguirão a ordem listada no código-fonte. Para saber mais sobre os motivos por trás dessa mudança, leia esta nota de Raymond Hettinger, um dos principais desenvolvedores do Python.
• As chaves são imutáveis: Isso significa que as chaves são sempre tipos de dados que não podem ser alterados. Em outras palavras, os dicionários só permitirão tipos de dados que sejam hashable, como strings, números e tuplas. Ao contrário, as chaves nunca podem ser um tipo de dados mutável, como uma lista.
• As chaves são exclusivas: As chaves são exclusivas em um dicionário e não podem ser duplicadas em um dicionário. Se for usado mais de uma vez, as entradas subsequentes substituirão o valor anterior.

Portanto, se você já se perguntou sobre as diferenças entre hashmaps e dicionários, a resposta é simples. Um dicionário é apenas a implementação nativa de hashmaps do Python. Enquanto um hashmap é uma estrutura de dados que pode ser criada usando várias técnicas de hashing, um dicionário é um hashmap específico baseado em Python, cujo design e comportamento são especificados na classe dict do Python.

Muitas linguagens de programação modernas, como Python, Java e C++, suportam hashmaps. Em Python, os hashmaps são implementados por meio de dicionários, uma estrutura de dados amplamente usada que você provavelmente conhece. Nas seções a seguir, abordaremos os conceitos básicos de dicionários, como eles funcionam e como implementá-los usando diferentes pacotes Python.

Como usar dicionários Python

Vamos ver algumas das operações de dicionário mais comuns. Para saber mais sobre como usar dicionários, confira nosso Tutorial de dicionários do Python.

Criando um dicionário

Criar dicionários em Python é bastante simples. Você só precisa usar chaves e inserir os pares de valores-chave separados por vírgulas. Como alternativa, você pode usar a função integrada dict(). Vamos criar um dicionário que mapeie as capitais para os países:

# Create dictionary
dictionary_capitals = {'Madrid": 'Spain", 'Lisboa': 'Portugal', 'London': 'United Kingdom'}

Para imprimir o conteúdo do dicionário:

print(dictionary_capitals)

{'Madrid': 'Spain', 'Lisboa': 'Portugal', 'London': 'United Kingdom'}

É importante lembrar que uma chave deve ser exclusiva em um dicionário; não são permitidas duplicatas. No entanto, no caso de chaves duplicadas, em vez de emitir um erro, o Python considerará válida a última instância da chave e simplesmente ignorará o primeiro par chave-valor. Veja você mesmo:

dictionary_capitals = {'Madrid': 'China', 'Lisboa': 'Portugal', 
                       'London': 'United Kingdom','Madrid':'Spain'}

print(dictionary_capitals)

{'Madrid': 'Spain', 'Lisboa': 'Portugal', 'London': 'United Kingdom'}

Pesquisando em um dicionário

Para pesquisar informações em nosso dicionário, precisamos especificar a chave entre colchetes, e o Python retornará o valor associado, como segue:

# Search for data
dictionary_capitals['Madrid']

'Spain'

Se você tentar acessar uma chave que não esteja presente no dicionário, o Python emitirá um erro. Para evitar isso, você pode acessar as chaves alternativamente usando o método .get(). No caso de uma chave inexistente, você retornará apenas um valor None:

print(dictionary_capitals.get('Prague'))

None

Adição e exclusão de valores em um dicionário

Vamos adicionar um novo par capital-país:

# Create a new key-value pair
dictionary_capitals['Berlin'] = 'Italy'

A mesma sintaxe pode ser usada para atualizar o valor associado a uma chave. Vamos corrigir o valor associado a Berlim:

# Update the value of a key
dictionary_capitals['Berlin'] = 'Germany'

Agora, vamos excluir um dos pares do nosso dicionário

# Delete key-value pair
del dictionary_capitals['Lisboa']

print(dictionary_capitals)

{'Madrid': 'Spain', 'London': 'United Kingdom', 'Berlin': 'Germany'}

Ou, se você quisesse excluir todos os pares de valores-chave do dicionário, poderia usar o método .clear():

dictionary_capitals.clear()

Percorrer dicionários

Se você quiser recuperar todos os pares de valores-chave, use o método .items(), e o Python recuperará uma lista iterável de tuplas:

dictionary_capitals.items()

dict_items([('Madrid', 'Spain'), ('London', 'United Kingdom'), ('Berlin', 'Germany')])

# Iterate over key-value pairs
for key, value in dictionary_capitals.items():
    print('the capital of {} is {}'.format(value, key))

the capital of Spain is Madrid
the capital of United Kingdom is London
the capital of Germany is Berlin

Da mesma forma, se você quiser recuperar uma lista iterável com as chaves e os valores, poderá usar os métodos .keys() e .values(), respectivamente:

dictionary_capitals.keys()

dict_keys(['Madrid', 'London', 'Berlin'])

for key in dictionary_capitals.keys():
    print(key.upper())

MADRID
LONDON
BERLIN

dictionary_capitals.values()

dict_values(['Spain', 'United Kingdom', 'Germany'])

for value in dictionary_capitals.values():
    print(value.upper())

SPAIN
UNITED KINGDOM
GERMANY

Aplicações reais de hashmaps

Os hashmaps são estruturas de dados poderosas que são usadas em quase todos os lugares no mundo digital. Abaixo, você encontra uma lista de aplicações reais de hashmaps:

• Indexação de banco de dados: Os hashmaps são usados com frequência para indexação e pesquisa de grandes volumes de dados. Os navegadores da Web comuns usam hashmaps para armazenar páginas da Web indexadas.
• Gerenciamento de cache: Os sistemas operacionais modernos usam hashmaps para organizar a memória cache e permitir o acesso rápido às informações usadas com frequência.
• Criptografia: Os hashmaps desempenham uma função essencial no campo da criptografia. Os algoritmos criptográficos aproveitam os hashmaps para permitir a integridade dos dados, a validação dos dados e as transações seguras nas redes.
• Blockchain: Os hashmaps são o núcleo do blockchain. Sempre que ocorre uma transação na rede, os dados dessa transação são levados como entrada para a função hash, que produz uma saída exclusiva. Cada bloco do blockchain contém o hash do bloco anterior, formando uma cadeia de blocos.

Práticas recomendadas e erros comuns do Hashmap

Os hashmaps são estruturas de dados incrivelmente versáteis e eficientes. No entanto, eles também apresentam problemas e limitações. Para enfrentar os desafios comuns associados aos hashmaps, é importante que você tenha em mente algumas considerações e boas práticas.

As chaves devem ser imutáveis

Isso faz sentido: se o conteúdo da chave mudar, a função hash retornará um hash diferente, de modo que o Python não conseguirá encontrar o valor associado à chave.

Como lidar com colisões de hashmap

O hashing só funciona se cada item for mapeado para um local exclusivo na tabela de hash. Mas, às vezes, as funções hash podem retornar a mesma saída para entradas diferentes. Por exemplo, se você estiver usando uma função de hash de divisão, diferentes números inteiros podem ter a mesma função de hash (eles podem retornar o mesmo resto ao aplicar a divisão do módulo), criando assim um problema chamado colisão. As colisões devem ser resolvidas, e existem várias técnicas. Felizmente, no caso dos dicionários, o Python lida com as possíveis colisões de forma inteligente.

Entendendo o fator de carga

O fator de carga é definido como a relação entre o número de elementos na tabela e o número total de compartimentos. É uma medida para estimar a boa distribuição dos dados. Como regra geral, quanto mais uniformemente os dados forem distribuídos, menor será a probabilidade de colisões. Novamente, no caso dos dicionários, o Python adapta automaticamente o tamanho da tabela no caso de novas inserções ou exclusões de pares de valores-chave.

Estar ciente do desempenho

Uma boa função de hash minimizaria o número de colisões, seria fácil de calcular e distribuiria uniformemente os itens na tabela de hash. Isso pode ser feito aumentando o tamanho da tabela ou a complexidade da função hash. Embora isso seja prático para pequenos números de itens, não é viável quando o número de itens possíveis é grande, pois resultaria em hashmaps que consumiriam muita memória e seriam menos eficientes.

Você precisa de dicionários?

Os dicionários são ótimos, mas outras estruturas de dados podem ser mais adequadas para seus dados e necessidades específicos. No final, os dicionários não oferecem suporte a operações comuns, como indexação, divisão e concatenação, o que os torna menos flexíveis e mais difíceis de trabalhar em determinados cenários.

Implementações alternativas de hashmap em Python

Como já mencionado, o Python implementa hashmaps por meio de dicionários incorporados. No entanto, é importante observar que há outras ferramentas nativas do Python, bem como bibliotecas de terceiros, para aproveitar o poder dos hashmaps.

Vamos ver alguns dos exemplos mais populares.

Padrão

Toda vez que você tentar acessar uma chave que não está presente no dicionário, o Python retornará um KeyError. Uma maneira de evitar isso é pesquisar informações usando o método .get(). No entanto, uma maneira otimizada de fazer isso é usar Defaultdict, disponível no módulo collections. Defaultdict e dicionários são praticamente os mesmos. A única diferença é que o site Defaultdict nunca gera um erro porque fornece um valor padrão para chaves inexistentes.

from collections import defaultdict 

# Defining the dict 
capitals = defaultdict(lambda: "The key doesn't exist") 
capitals['Madrid'] = 'Spain'
capitals['Lisboa'] = 'Portugal'
  
print(capitals['Madrid']) 
print(capitals['Lisboa']) 
print(capitals['Ankara']) 

Spain
Portugal
The key doesn't exist 

Balcão

Counter é uma subclasse de um dicionário Python projetado especificamente para contar objetos com hash. É um dicionário em que os elementos são armazenados como chaves e suas contagens são armazenadas como valores.

Há várias maneiras de inicializar o site Counter:

• Por uma sequência de itens.

• Por chaves e contagens em um dicionário.

• Usando o mapeamento name:value.

from collections import Counter 

# a new counter from an iterable
c1 = Counter(['aaa','bbb','aaa','ccc','ccc','aaa'])
# a new counter from a mapping
c2 = Counter({'red': 4, 'blue': 2})     
# a new counter from keyword args
c3 = Counter(cats=4, dogs=8)       
# print results
print(c1)
print(c2)
print(c3)

Counter({'aaa': 3, 'ccc': 2, 'bbb': 1})
Counter({'red': 4, 'blue': 2})
Counter({'dogs': 8, 'cats': 4})

A classe de contador vem com uma série de métodos úteis para fazer cálculos comuns.

print('keys of the counter: ', c3.keys())
print('values of the counter: ',c3.values()) 
print('list with all elements: ', list(c3.elements())) 
print('number of elements: ', c3.total()) # number elements
print('2 most common occurrences: ', c3.most_common(2)) # 2 most common occurrences 

dict_keys(['cats', 'dogs'])
dict_values([4, 8])
['cats', 'cats', 'cats', 'cats', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs']
12
[('dogs', 8), ('cats', 4)]

Métodos de hash do Scikit-learn

O Scikit-learn, também conhecido como sklearn, é uma biblioteca de aprendizado de máquina Python robusta e de código aberto. Ele foi criado para ajudar a simplificar o processo de implementação de aprendizado de máquina e modelos estatísticos em Python.

O Sklearn vem com vários métodos de hash que podem ser muito úteis para os processos de engenharia de recursos.

Um dos mais comuns é o método CountVectorizer. Ele é usado para transformar um determinado texto em um vetor com base na frequência de cada palavra que ocorre em todo o texto. CountVectorizer é particularmente útil em contextos de análise de texto.

from sklearn.feature_extraction.text import CountVectorizer
 
documents = ["Welcome to this new DataCamp Python course",
            "Welcome to this new DataCamp R skill track",
            "Welcome to this new DataCamp Data Analyst career track"]
 
# Create a Vectorizer Object
vectorizer = CountVectorizer()

X = vectorizer.fit_transform(documents)

# print unique values 
print('unique words: ', vectorizer.get_feature_names_out())


#print sparse matrix with word frequency
pd.DataFrame(X.toarray(), columns = vectorizer.get_feature_names_out())

unique words:  ['analyst' 'career' 'course' 'data' 'datacamp' 'new' 'python' 'skill' 'this' 'to' 'track' 'welcome']

Há outros métodos de hashing no sklearn, incluindo FeatureHasher e DictVectorizer. Nosso estudo de caso School Budgeting with Machine Learning in Python é um ótimo exemplo em que você pode aprender como eles funcionam na prática.

Conclusão

Parabéns por você ter concluído este tutorial sobre hashmaps. Esperamos que agora você tenha uma melhor compreensão dos hashmaps e dicionários Python. Se você quiser saber mais sobre dicionários e como usá-los em cenários reais, recomendamos que leia nosso tutorial dedicado sobre dicionários Python, bem como nosso tutorial sobre compreensão de dicionários Python.

Por fim, se você está começando a usar Python e gostaria de saber mais, faça o curso Introdução à ciência de dados em Python da DataCamp e confira nosso Tutorial de Python para iniciantes.