What is a hash map in Python?
I'm a Python beginner, 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.
Steps:
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
Return True "
Wanted to understand what the hash map is actually and why I should create the algorithm following this approach.
2 answers
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.
See the above question for more complete information, but in summary a hash is a numerical value calculated from an algorithm over an arbitrary size value and is expected to that hash be 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 the form 1 to 1 a hash, which is used as a key, to any value associated with that key. This structure works very well when we need to search for elements, because we just calculate the hash of the searched value and access the table in that position.
In English the table of hash is commonly referenced as a dictionary (and works as such: whenever you need a meaning, just search for the word in the dictionary). Here it is important to point out that the dictionary that is given as a table synonym of hash is not exactly the Python dictionary. The Python dictionary is actually an implementation of the hash table, but not the only one. Other structures, such as set, they are also implemented over tables of hash.
So the answer as to why using 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 made and, thus, using a structure that allows a quick search is ideal.
Basically the exercise asks you to scroll through the text and for each letter make sure it is already present in the table of hash ; if it is, the letter is duplicated and should 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 Python's set:
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 inclusive is more used when you want to manage duplicate values in its sequence, because it reproduces the same behavior that a set has in mathematics and, by definition, it has no duplicate values.
Is just another name for a Dictionary that Python already has so you just map the letters as keys to that dictionary.
Why should I use this I do not know, you have to ask who sent it because it is a very strange exercise since it maps and does nothing else, but I believe it is because it is a half automatic way to get the result since you need to have only one entry per different character and this is exactly what be.
Has even simpler forms, but the exercise commands to do so. It has more manual ways if it is to exercise logic and ability to solve problems in every detail.