What is a Python hash map?

Question

I’m a beginner in Python, and I’m doing an exercise that says the following:

Considering a string,

"We will keep a hash map (set) to track the unique characters we find.

Footsteps:

Scan each character

For each character:

• If the character does not exist in a hash map, add the character to a hash map

• If not, return False

True return"

I wanted to understand what the hash map really is and why I should create the algorithm by following this approach.

Answer 1

The hash map is an abstraction that is not unique to Python. It is a larger concept, which has been used in several implementations in Python that can be used in the solution of the exercise.

• How the implementation of hash tables works?

See the above-mentioned question for more complete information, but in summary form a hash is a numerical value calculated from an algorithm over an arbitrary size value and is expected to hash is unique for such a value. That is, if we calculated the hash of each letter of the alphabet we would have a different value for each.

The table of hash is a structure that relates in form 1 to 1 a hash, which is used as a key for any value associated with that key. This structure works very well when we need to search for elements, because it is enough to calculate the hash and access the table at that position.

In Portuguese a tabela de hash is commonly referred to as a dictionary (and functions as such: whenever you need a meaning, just look up the word in the dictionary). Here it is important to note that the dictionary which is given as synonymous with table of hash is not exactly the Python dictionary. Python’s dictionary is actually an implementation of the hash, but not the only one. Other structures, such as the set, are also implemented on tables of hash.

So the answer about why to use this approach to solve the problem is due to the fact that you will have to do constant searches in your structure. For each letter of the input text a search will be done and thus using a structure that allows a quick search is ideal.

Basically the exercise asks you to go through the text and for each letter check if it is already present in the table hash; if it is, the letter is duplicated and must return false, but when it is not (first occurrence of the letter), you should add it to the table.

Using the Python dictionary would look something like:

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

Or you can use the set 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

The structure set is even more used when it is intended to manage duplicated values in its sequence, because it reproduces the same behavior that a set has in mathematics and, by definition, does not have duplicated values.

• Check that all items in a string are different?

Answer 2

It’s just another name for one dictionary that Python already has so you just map the letters as keys to that dictionary.

Why should I use this I don’t know, have to ask who sent it because it’s a really weird exercise since it maps and does nothing else, but I believe it is because it is an automatic way to get the result since you need to have only one entry per different character and this is exactly what the keys of a dictionary are.

It has even simpler forms, but the exercise orders to do so. It has more manual ways if it is to exercise the logic and ability to solve problems in every detail.