Nesta lição, vamos abordar mapas, hash maps e conjuntos. Mas antes disso, vamos definir Tipos Abstratos de Dados. Um Tipo Abstrato de Dados (ADT) é uma representação conceitual de um tipo de dado, incluindo quais operações podem ser realizadas sobre os dados e as propriedades desses dados. Tipos Abstratos de Dados são como plantas que descrevem o que operações podem ser realizadas, não como elas são realizadas. Eles separam a interface da implementação real das operações. Um map é um ADT que gerencia coleções de pares chave-valor e suas operações de uma maneira muito específica e eficiente. Em um mapa, cada valor está associado a uma chave específica. Uma das principais características dos mapas é que cada chave deve ser única. Essa unicidade permite buscas diretas, o que torna o processo de recuperação de informações muito mais eficiente. Apenas as chaves devem ser únicas, os valores podem ser repetidos. O Tipo Abstrato de Dados map também define operações importantes, como inserir pares chave-valor, obter o valor associado a uma chave, atualizar o valor associado a uma chave, remover um par chave-valor e verificar se uma chave existe no map. Na verdade, não especifica como essas operações devem ser realizadas, apenas as lista como parte das operações disponíveis do tipo de dado. Um hash map, também conhecido como hash table, é uma implementação concreta do tipo abstrato de dados map. Mapas hash usam uma técnica chamada "hashing" para executar operações comuns de forma muito eficiente. Hashing funciona essencialmente gerando um valor hash para cada elemento usando uma função hash. O valor do hash é gerado com base na chave do par chave-valor e é usado para calcular um índice em um array subjacente, a estrutura de dados real onde os pares chave-valor são armazenados. Mas você pode estar se perguntando: O que acontece se duas chaves resultarem no mesmo índice? Mapas hash resolvem essas colisões com estratégias inteligentes. Uma opção é usar a estratégia de "chaining", onde cada índice do array aponta para uma lista encadeada (outra estrutura de dados), onde todos os elementos com o mesmo índice são armazenados. Outra estratégia é usar "open addressing", que envolve buscar o próximo índice disponível no array com base em uma sequência de busca predefinida. A complexidade de tempo no caso médio de hash maps é "Constant Time" O(1) para inserir, recuperar e deletar pares chave-valor. A complexidade de tempo no pior caso dessas operações é Tempo Linear O(n), que ocorre quando há muitas colisões de hash, então a estratégia de resolução de colisões precisa ser aplicada várias vezes. A complexidade de espaço ao inserir em um hash map é constante O(1) no caso médio, uma quantidade constante de memória para armazenar o novo par. No entanto, no pior caso, pode ter complexidade de espaço linear O(n) devido a uma operação de redimensionamento do array subjacente. Em geral, remover um elemento tem uma complexidade de espaço constante O(1). Isso transforma a tabela hash em algo semelhante a uma estrutura de dados linear onde n elementos precisam ser escaneados para encontrar a chave alvo. No entanto, isso é relativamente raro se o hash map for implementado corretamente. Os dicionários do Python são implementados como hash maps nos bastidores. Para criar um dicionário Python, você só precisa escrever os pares chave-valor dentro de chaves e separá-los com uma vírgula. Cada chave deve ser separada do seu valor correspondente por dois pontos.

my_dictionary = {
  'A': 1,
  'B': 2, 
  'C': 3
}

Neste código, 'A' é a chave e 1 é o valor:

'A': 1

Alternativamente, você pode usar dict():

my_dictionary = dict(A=1, B=2, C=3)

Você pode obter o valor através da sua chave correspondente:

my_dictionary['A']  # 1

Você também pode atualizar o valor associado a uma chave:

my_dictionary['A'] = 4

E você pode remover um par chave-valor:

del my_dictionary['A']

Você também pode verificar se uma chave está no dicionário (ou não):

'C' in my_dictionary

E você pode chamar esses métodos para obter as chaves, valores e itens do dicionário, respectivamente.

my_dictionary.keys()
my_dictionary.values()
my_dictionary.items()

Ótimo. Agora que você sabe mais sobre mapas e hash maps, vamos falar sobre conjuntos. Conjuntos são coleções não ordenadas de elementos únicos. Vamos dividir este conceito em seus componentes principais: * Conjuntos são desordenados. Os elementos de um conjunto não são armazenados em nenhuma ordem específica, então você não pode acessá-los por meio de índices. * Conjuntos contêm apenas elementos únicos. Se você tentar adicionar o mesmo valor duas vezes, apenas uma cópia do valor será mantida. Eles são análogos a conjuntos em matemática e implementam as mesmas operações de conjunto, como interseção, união e diferença. Uma das principais vantagens dos sets é que eles garantem que os elementos serão únicos (sem duplicatas). É por isso que eles são frequentemente usados para remover duplicatas de listas e outras estruturas de dados. Eles também são dinâmicos. Eles podem se ajustar ao número de elementos que estão atualmente armazenados. Isso os torna bastante poderosos. A complexidade de tempo no caso médio de adicionar, remover, obter o tamanho do conjunto e verificar se um elemento está no conjunto é "Constant Time" O(1), que é muito eficiente. Como os conjuntos são implementados como tabelas hash, a complexidade de tempo no pior caso para adicionar, remover e verificar a associação é "Linear Time" O(n). Isso pode ocorrer quando há múltiplas colisões de hash, transformando a tabela de hash em algo semelhante a uma estrutura de dados linear, onde são necessárias n varreduras para encontrar a chave. Em termos de complexidade de espaço, no caso médio, inserir um elemento teria complexidade constante O(1), com um novo elemento único exigindo uma quantidade constante de memória. No entanto, no pior caso, pode haver uma operação de redimensionamento do array subjacente, que pode levar complexidade de espaço linear O(n). Em geral, remover um elemento teria complexidade de espaço constante O(1). Python possui uma estrutura de dados set embutida que você usa para trabalhar com conjuntos em seus programas. Nos bastidores, os conjuntos em Python são implementados usando uma tabela hash onde apenas as chaves são armazenadas, sem quaisquer valores associados. Conjuntos só podem armazenar objetos de tipos de dados imutáveis porque seus valores de hash sempre permanecem os mesmos. Em contraste, os valores de hash de objetos mutáveis podem mudar quando eles são mutados. É por isso que eles não podem fazer parte de conjuntos. Se o valor do hash de um objeto armazenado no conjunto mudar, o programa não seria mais capaz de encontrá-lo. Para definir um conjunto em Python, você só precisa envolver os elementos com chaves e separá-los com vírgulas:

numbers = {1, 2, 3, 4}

Para criar um conjunto vazio, você pode chamar set():

numbers = set()

Observe que se você usar chaves vazias, isso criará automaticamente um dicionário Python, não um conjunto, então você deve chamar a função set() para criar um conjunto vazio. Você pode adicionar um elemento a um conjunto com o método .add():

numbers.add(5)

Você também pode remover elementos do conjunto com o método .remove():

numbers.remove(5)

Isso lançará um KeyError se o elemento não for encontrado. Mas se você não quiser gerar um erro nesse caso, pode usar o método .discard() em vez disso. O método .pop() retorna um elemento arbitrário do conjunto, enquanto o método .clear() remove todos os elementos do conjunto. Você pode testar se um elemento está em um conjunto com o operador in:

5 in numbers

Python também suporta operações com conjuntos, incluindo união, diferença, diferença simétrica e interseção, que você pode realizar com esses métodos:

set_a = {1, 2, 3, 4}
set_b = {2, 3, 4, 5, 6}

set_a.union(set_b)
set_a.intersection(set_b)
set_a.symmetric_difference(set_b)
set_a.difference(set_b)

Ou com seus operadores equivalentes:

set_a | set_b
set_a & set_b
set_a ^ set_b
set_a - set_b

A complexidade de tempo no caso médio para adicionar, remover e testar a associação é "Constant Time" O(1). A complexidade de tempo no pior caso para essas operações é "Tempo Linear" O(n) por causa do pior cenário de colisão do hash map. Você também pode verificar se um conjunto é um subconjunto ou um superconjunto de outro:

set_a.issubset(set_b)
set_a.issuperset(set_b)

Em geral, você deve usar conjuntos quando precisar armazenar uma coleção de itens únicos e verificar frequentemente a presença de um item. Mapas, hash maps e sets são estruturas de dados poderosas projetadas para organização e recuperação eficiente de dados. Cada um deles tem suas próprias características únicas e casos de uso. Como desenvolvedor, você precisará escolher o melhor para o seu projeto.