Tabelas de hash e mapas de hash em Python

Os dados exigem várias maneiras de serem acessados ​​ou armazenados. Hash Tables e Hashmaps são as melhores estruturas de dados para implementar isso em Python por meio do tipo de dados integrado conhecido como dicionário.

Um Hashmap ou uma tabela Hash na estrutura de dados mapeia chaves para seus pares de valores e usa uma função que calcula qualquer valor de índice que contenha os elementos a serem inseridos, pesquisados ​​ou removidos. Isso ajuda a tornar o acesso aos dados mais fácil e rápido. As tabelas de hash geralmente armazenam pares de valores-chave e usam a função de hash para gerar uma chave.

Neste artigo, você aprenderá o que são Hash Tables e Hashmaps e como eles são implementados em Python.

Aprenda ciência de dados para ganhar vantagem sobre seus concorrentes

O que é uma tabela Hash ou um Hashmap Python?

Uma tabela de hash ou hashmap Python é uma estrutura de dados indexada. Ele usa funções de hash para calcular um índice usando uma chave em uma matriz de slots ou buckets. Você pode mapear seu valor para um bucket usando o índice correspondente, e a chave é imutável e exclusiva.

Hashmaps são semelhantes a um armário de gavetas rotulado com as coisas que eles armazenam. Por exemplo, os hashmaps podem armazenar informações do usuário, como nome e sobrenome, etc., no bucket.

A função hash é integral para a implementação de um hashmap. Ele usa a chave e a traduz para o índice do bucket na lista de buckets. O hash ideal produz um índice separado para cada chave. No entanto, tenha em mente que podem ocorrer colisões. Quando o hash produz um índice já existente, um bucket para vários valores pode ser facilmente usado rehashing ou anexando uma lista. Em Python, um exemplo de mapas de hash são os dicionários.

Vamos analisar a implementação do hashmap em detalhes para aprender a personalizar e construir estruturas de dados para otimização de pesquisa.

Hashmap em Python

O hashmap inclui as seguintes funções:

• set_val(chave, valor): Esta função é usada para inserir um par chave-valor no mapa de hash. Se já houver um valor existente no mapa de hash, você deverá atualizar o valor.
• get_val(key): Esta função retorna o valor para a chave especificada que está mapeada ou “Nenhum registro encontrado” se este mapa não tiver mapeamento para a chave.
• delete_val(key): Exclui o mapeamento para a chave específica se o hashmap tiver o mapeamento para a chave.

Implementação:-

classe Hashtable:

# Cria uma lista de buckets vazia de determinado tamanho

def __init__(self, tamanho):

self.size = tamanho

self.hash_table = self.create_buckets()

def create_buckets(self):

return [[] for _ in range(self.size)]

# Insere valores no mapa de hash

def set_val(self, key, val):

# Obtém o índice da chave

# usando a função hash

hashed_key = hash(chave) % self.size

# Obtém o bucket correspondente ao índice

bucket = self.hash_table[hashed_key]

found_key = False

para índice, registre em enumerate(bucket):

record_key, record_val = registro

# verifica se o bucket tem a mesma chave que

# a chave a ser inserida

if record_key == key:

found_key = Verdadeiro

parar

# Se o bucket tiver a mesma chave que a chave a ser inserida,

# Atualiza o valor da chave

# Caso contrário, anexe o novo par de valores-chave ao bucket

se encontrado_chave:

bucket[índice] = (chave, valor)

senão:

bucket.append((chave, val))

# Retorna o valor pesquisado com chave específica

def get_val(self, chave):

# Obtém o índice da chave usando

#função hash

hashed_key = hash(chave) % self.size

# Obtém o bucket correspondente ao índice

bucket = self.hash_table[hashed_key]

found_key = False

para índice, registre em enumerate(bucket):

record_key, record_val = registro

# verifica se o bucket tem a mesma chave que

# a chave que está sendo pesquisada

if record_key == key:

found_key = Verdadeiro

parar

# Se o bucket tiver a mesma chave que a chave que está sendo pesquisada,

# Retorna o valor encontrado

# Caso contrário, indique que não foi encontrado nenhum registro

se encontrado_chave:

retornar record_val

senão:

return “Nenhum registro encontrado”

# Remove um valor com chave específica

def delete_val(self, key):

# Obtém o índice da chave usando

#função hash

hashed_key = hash(chave) % self.size

# Obtém o bucket correspondente ao índice

bucket = self.hash_table[hashed_key]

found_key = False

para índice, registre em enumerate(bucket):

record_key, record_val = registro

# verifica se o bucket tem a mesma chave que

# a chave a ser deletada

if record_key == key:

found_key = Verdadeiro

parar

se encontrado_chave:

bucket.pop(índice)

Retorna

# Para imprimir os itens do mapa de hash

def __str__(self):

return “”.join(str(item) para item em self.hash_table)

hash_table = HashTable(50)

#inserir alguns valores

hash_table.set_val([email protected]', 'algum valor')

print(tabela_hash)

imprimir()

hash_table.set_val('[email protected]', 'algum outro valor')

print(tabela_hash)

imprimir()

# busca/acessa um registro com chave

print(hash_table.get_val('[email protected]'))

imprimir()

# exclui ou remove um valor

hash_table.delete_val('[email protected]')

print(tabela_hash)

Resultado:-

[][][][][][][][][][][][][][][][][][][] ([email protected]', 'algum valor') ][][][][][][][][][][][][][][][][][][][][] [][][][]

[][][][][][][][][][][][][][][][][][][] ([email protected]', 'algum valor') ][][][][][][('[email protected]', 'algum outro valor')][][][][][][][][][ ][][][][][][][][][][][]

Algum outro valor

[][][][][][][][][][][][][][][][][][][] ([email protected]', 'algum valor') ][][][][][][][][][][][][][][][][][][][][] [][][][]

Confira nossos EUA - Programas de Ciência de Dados

Executando operações em tabelas de hash usando dicionários:

Existem inúmeras operações que podem ser executadas em Python em tabelas de hash por meio de dicionários. São os seguintes:-

• Acessando valores
• Atualizando valores
• Excluindo elemento

Acessando Valores:

Você pode acessar facilmente os valores de um dicionário das seguintes maneiras:-

• Usando valores-chave
• Usando funções
• Implementando o loop for

Usando valores de chave:

Você pode acessar os valores do dicionário usando os valores de chave como abaixo: -

Saída: '002'

Usando funções:

Existem inúmeras funções internas, como get(), keys(), values(), etc.

Resultado:-

dict_keys(['Elsa', 'Anna', 'Olaf'])

dict_values(['001', '002', '003'])

001

Implementando o loop for:

O loop fornece acesso aos pares chave-valor de um dicionário, iterando sobre eles. Por exemplo:

Resultado:

Todas as chaves

Elsa

Ana

Olaf

Todos os valores

001

002

003

Todas as chaves e valores

Elsa: 001

Ana: 002

Olaf: 003

Atualizando valores:

Os dicionários são tipos de dados mutáveis ​​que podem ser atualizados quando necessário. Você pode fazer o seguinte: -

Saída : {'Elsa': '001' , 'Anna': '002' , 'Olaf': '004', 'Kristoff': '005'}

Excluindo itens de um dicionário:

Você pode excluir itens de um dicionário com funções como del(), pop(), popitem(), clear(), etc. Por exemplo:

Saída : {'Olaf': '003'}

Conclusão

Podemos concluir facilmente que os hashmaps e a tabela de hash Python são integrais para um acesso mais fácil e rápido a dados relevantes. É uma ferramenta valiosa para profissionais de ciência de dados, como cientistas de dados e analistas de dados. Se você está interessado em aprender mais sobre a área de Ciência de Dados, o upGrad tem o melhor Programa de Certificação Profissional em Ciência de Dados para Tomada de Decisões de Negócios .