1

Sou iniciante em Python, e estou fazendo um exercício que diz o seguinte:

Considerando uma string,

"Manteremos um mapa hash (conjunto) para rastrear os caracteres únicos que encontramos.

Passos:

Faça um scan cada caracter

Para cada caracter:

  • Se o caracter não existir em um mapa de hash, adicione o caractere a um mapa de hash

  • Senão, retorne False

Retornar Verdadeiro"

Queria entender o que é de fato o mapa de hash e porque eu deveria criar o algoritmo seguindo essa abordagem.

2
  • 3
    isso é tudo bem bonito, mas careteres_unicos = set(texto) resolve o problema.
    – Isac
    9/10/2019 às 10:27
  • @Isac, você acabou de preencher o requisito "mapa hash (conjunto)" do enunciado da questão... :D 9/10/2019 às 12:59

2 Respostas 2

6

O mapa de hash é uma abstração que não é única do Python. É um conceito maior, que foi utilizado em várias implementações no Python que poderão ser utilizadas na solução do exercício.

Veja a pergunta supracitada para informações mais completas, mas de forma resumida um hash é um valor numérico calculado a partir de um algoritmo sobre um valor de tamanho arbitrário e espera-se que esse hash seja único para tal valor. Ou seja, se calculássemos a hash de cada letra do alfabeto teríamos um valor diferente para cada.

A tabela de hash é uma estrutura que relaciona na forma 1 para 1 uma hash, que é utilizada como chave, para um valor qualquer associado à essa chave. Essa estrutura funciona muito bem quando necessitamos fazer a busca de elementos, pois basta calcularmos a hash do valor buscado e acessar a tabela naquela posição.

Em português a tabela de hash é comumente referenciada como dicionário (e funciona como tal: sempre que precisa de um significado, basta buscar a palavra no dicionário). Aqui é importante salientar que o dicionário que é dado como sinônimo de tabela de hash não é exatamente o dicionário do Python. O dicionário do Python é, na verdade, uma implementação da tabela de hash, mas não a única. Outras estruturas, como o set, também são implementados sobre tabelas de hash.

Então a resposta sobre porquê utilizar essa abordagem para resolver o problema é devido ao fato que você terá que fazer buscas constantes na sua estrutura. Para cada letra do texto de entrada será feito uma busca e, assim, utilizar uma estrutura que permite uma busca rápida é o ideal.

Basicamente o exercício pede para que você percorra o texto e para cada letra verifique se ela já está presente na tabela de hash; se estiver, a letra está duplicada e deve retornar falso, mas quando não estiver (primeira ocorrência da letra), deve adicioná-la à tabela.

Utilizando o dicionário do Python ficaria algo como:

def caracteres_unicos(texto):
  tabela = {}

  for letra in texto:  # Percorre as letras do texto
    if letra in tabela:  # Verifica se a letra já está na tabela
      return False  # Letra duplicada, retorna falso
    tabela[letra] = letra  # Adiciona a letra na tabela

  return True  # Nenhuma letra duplicada, retorna verdadeiro

Ou pode utilizar o set do Python:

def caracteres_unicos(texto):
  tabela = set()

  for letra in texto:  # Percorre as letras do texto
    if letra in tabela:  # Verifica se a letra já está na tabela
      return False  # Letra duplicada, retorna falso
    tabela.add(letra)  # Adiciona a letra na tabela

  return True  # Nenhuma letra duplicada, retorna verdadeiro

A estrutura set inclusive é mais utilizada quando se pretende gerenciar valores duplicados na sua sequência, pois reproduz o mesmo comportamento que um conjunto possui na matemática e, por definição, não possui valores duplicados.

1
  • Deu certo. A única coisa que eu não havia previsto foi inserir o código: 'if string is None: return False' para passar no teste. Sabe me dizer o porque de eu ter que colocar essa linha de código? 15/10/2019 às 22:22
2

É só um outro nome para um dicionário que o Python já tem então é só você mapear as letras como chaves desse dicionário.

Por que deveria usar isso eu não sei, tem que perguntar para quem mandou porque é um exercício até bem esquisito já que mapeia e não faz mais nada, mas acredito que seja porque é uma forma meio automática de obter o resultado já que você precisa ter só uma entrada por caractere diferente e isto é exatamente o que as chaves de um dicionário são.

Tem formas até mais simples, mas o exercício manda fazer assim. Tem formas mais manuais se é para exercitar a lógica e capacidade de resolver problemas em todos os detalhes.

8
  • Pode melhorar alterando a primeira frase. Não é "só um outro nome" para dicionário. O dicionário é uma das implementações de mapa hash presentes na linguagem.
    – Woss
    9/10/2019 às 12:52
  • O enunciado especifica que o mapa hash a ser utilizado é o conjuto, então o set() seria a implementação que o exercício solicita. PS: A implementação de set em Python é semelhante a um dicionário (fonte). 9/10/2019 às 12:56
  • @AndersonCarlosWoss eu poderia mudar algo, mas é exatamente o oposto, dicionário é um conceito mais abstrato que Python resolveu usar como nome de algo mais concreto que por acasa usa uma hash table.
    – Maniero
    9/10/2019 às 13:03
  • @fernandosavio o exercício usa um termo genérico e não a forma exata de se fazer, pode ser feito com set, mas pode ser feito com um dicionário, eu não posso garantir que seja isto, eu posso dar alternativas
    – Maniero
    9/10/2019 às 13:05
  • Exatamente. Da maneira atual pareceu que são unicamente equivalentes.
    – Woss
    9/10/2019 às 13:05

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .