HASH EM TUDO: como e onde estão dicionários em Python

Introdução

Neste ultimo sábado, eu dei uma breve palestra sobre dicionários no
Meetup <https://www.meetup.com/pt-BR/Grupy-SP/events/240054524/>_
mensal do Grupy-SP. Galera muito boa e deu pra trocar umas idéias
interessantes sobre Python e programação em geral. Resolvi falar sobre dicionários,
um assunto que é do dia-a-dia de muito programadores mas que no geral os detalhes de como
funciona acabam ficando para trás.

Dicionarios são um dos tipos built-in mais flexiveis de Python.
Elas acabam por exercer funções de records, structs, search tables ou
qualquer outro tipo de agregação em que nomes de item são mais significativos
que suas posições na estrutura de dados.

A grande vantagem de dicionarios é o poder de associar um objecto a outro,
não necessitando de estruturas intermediarias para criar esses mapeamentos.
Isso é possivel graças ao modelo de dados do Python, que tem como principio
de design tratar (quase) tudo como objeto.

Devido a esse fundamento de design, dicionarios estão em toda parte e por isso,
daqui pra frente, iremos verificar como eles funcionam, quais seus fundamentos e
como isso influencia nosso uso cotidiano de Python.

Hashtables e suas características
~~~~~~~~~~

Uma hash table (ou hash map) é um tipo de dado abstrato que implementa um array associativo,
que mapeia chaves a valores. Esse tipo de associação é util para busca em tempo constante
( O(1) ), negociando velocidade de processamento por espaço.

Hash tables são arrays associadas com funções que aceitam um argumento, que o mapeia para o dado a ser recuperado

.. image:: ../images/posts/hashs_20170530/hashtable01.png
:width: 500px
:align: center
:alt: Hash table example

valor hash mapeia a chave a um valor no array

Comparando com arrays, por exemplo, a differença fundamental é que é diferente
buscar por um indice e buscar por um valor. Em arrays, no geral, buscar o valor
quando se tem o indice é feito em tempo O(1), mas o que acontece quando não se tem tal informação
e precisa-se de um valor? Deve-se recorrer a algoritmos de busca para achar o valor.
Em hashtables você tem uma função associativa de CHAVE com VALOR,
onde se acha o valor em tempo O(1), enquanto as buscas acima possuem tempo linear e logaritmico,
respectivamente.

Ja que hashtables possuem esse comportamento, deve-se garantir que as funções
hash sempre associarão uma unica chave a unico valor, garantindo assim o acesso ao valor correto.
Caso a função hash acabe mapeando chaves diferentes para o mesmo indice, ocorre o fenomeno de colisão,
propriedade inerente, mas indesejada, de hashtables. Para resolver colisões, as hashtables
precisar possuir maneiras de resolver tal conflito.

.. image:: ../images/posts/hashs_20170530/hashtable02.png
:width: 500px
:align: center
:alt: Colision image

Caju, numa função hash hipotetica que utiliza as 3 primeiras letras da palavra, mapeia para o mesmo slot de Cajá

Desta forma, algoritmos de hash tables consistem de duas partes diferentes:

  • a computação de uma função hash
  • a resoluçao de colisões

Funções Hash
^^^^^^^^^^^^^

Uma funçao hash projeta um valor de um dado conjunto com vários (ou até infinito numero) de membros
para um valor com de um conjunto com menos membros. Funções hash não são invertiveis.

Funções hash podem ser utilizadas para determinar se dois objetos são iguais, com baixa possibilidade
de erro. O uso de checksums por exemplo, para checagem de redundancia ciclica, é um bom exemplo
de uso de hash functions.

No entanto, a escolha da função hash depende da natureza do dado da chave. Desta
forma, tipos de dados diferentes possuem funções hash diferentes. Abaixo, alguns
exemplos de hash functions para inteiros e strings

.. code-block:: python
:linenos:

    # Hash para inteiros

    def quick_and_dirty(integer, a, b, p, m):
    """
    a e b são numeros randomicos
    m é a quantidade de slots da hash table
    p é um primo maior que m
    """
        return ((a*integer + b)%p)%m

.. code-block:: python
:linenos:

    # Hash para strings

    def polyhash_prime(word, a, p, m):
    """
        m é o tamanho do hash
        a é um numero não randomico, preferencialmente primo
        p é um primo maior que m
    """
        hash = 0
        for c in word:
            hash = (hash * a + ord(c)) % p

        return abs(hash % m)

Observe que em ambas as funções existe a inclusão de algum elemento randômico.

Colisões
^^^^^^^^^^^^^

Nos casos em que ocorrem colisões, ou seja, multiplas chaves mapeiam pra um mesmo valor de hash,
elementos diferentes mapeiam para o mesmo ‘espaço’ da hash table. Fica claro que,
quando a função hash é usada para localizar um match em potencial, será necessario comparar a
chave daquele elemento com a chave de busca. No entanto, pode haver mais de um elemento
onde deveria estar um unico valor. Nestas circunstâncias, aplica-se os algoritmos de colisão.

  • Separate chain Utiliza uma estrutura secundária no espaço alocado para aquela chave. Desta forma, ao inserir
    um elemento e ocorrer colição, a estrutura secundária (ou um array ou lista encadeada) cuida
    de gerenciar a alocação e/ou localização do elemento.
  • Open Addressing Quando se utiliza separate chain, ocorre o problema de crescimento sem limites. Um exemplo é
    a utilização em sistemas embarcados, onde memoria é um recurso escasso. Desta forma, novas
    estruturas apresentam um problema secundario. Open Adressing não insere esse problema, tentando
    resolver a situação por vias dos recursos disponiveis. Basicamente, procura-se um novo espaço
    na estrutura original por meio de outras técnicas.

Separate chain não é ideal em circunstâncias em que memória é um elemento escasso.
Em desenvolvimento para sistemas embarcados, por exemplo, pede a utilização
de Open Addressing, ja que tenta-se resolver a colição com os recursos
anteriormente definidos no hash table. Abaixo, seguem dois exemplos de
algoritmos de Open Addressing.

Linear Probing

O mais simples dos algoritmos de colisão. No caso do slot estar ocupado, ele vai procurando
espaços vizinhos ao slot ‘original’ e insere o novo valor na vizinhança.

Rehashing

Em rehashing, apenas se aplica novamente a mesma função ou uma função secundária de hash para
localizar o slot. Se ocorrer colisões secundarias, aplica-se a função até achar um espaço
disponivel.

Python usa Open Addressing para resolver o problema de colisão de seus dicionários.

Dicionários e o Python Data Model

Objetos em Python são a abstração para DADOS. Até mesmo código é representado por objetos
fazendo-os do elemento fundamental de construção da linguagem e implica nos tipos
de operações que esses objetos suportam ou em que circunstâncias podem ser utilizados.

Python é construido ao redor de dicionarios:

  • Globais
  • Locais
  • Dicionarios de modules
  • Dicionarios de classe
  • Dicionarios de instancia

Por esse modelo de dados de Python, a construção de objetos como dicionarios favorecem o acesso rápido a esses elementos
e principalmente a unicidade de cada um deles. Uma instância de uma classe deve ser unica,
mesmo quando se possui várias referencias a ela. Basicamente o hash do objeto garante isso.
Um contra-exemplo, no entanto, são variaveis locais, que a nivel de implementacao não são
dicionários, mas ao requerer acesso a elas, a interface de acesso são dicionarios.

Identidade e identificador de objectos

A função id() é a identidade real do objeto, pois a nivel de implementação, esse identificador
é o endereço de memória do objeto. Um efeito direto disso é: se dois objetos não tem seus
tempos de vida sobrepostos, eles podem possuir o mesmo id (é raro, mas é possivel). O id() é
utilizado pelo operador is para verificar se duas variáveis apontam para o mesmo objeto.

Ja a função hash() retorna o valor hash do objeto, se o possuir. Em Python, os hashes são
inteiros e são usados no lookup dos dicionarios. hash() é a interface de chamada do metodo
__hash__() implementado no objeto, que deve retornar um valor que lhe é unico. Isso é
utilizado ao comparar objetos. Por exemplo, se dois objetos possuem o mesmo valor hash(),
sua comparação via __eq__() é verdadeira. Desta forma, hashability torna o objeto usavel
como chave de dicionario.

No design de Objetos em Python, eles podem ser mutaveis e imutaveis.
Os tipos imutaveis como strings, inteiros e tuplas podem ser utilizados
como chaves em dicionários, já objetos mutáveis como outros dicionarios e listas não.
Por padrão, estes objetos imutaveis de Python são “hashables”. O mesmo acontece
com instâncias de classes, pois eles se utilizam do output de id() como chave:
todos são diferentes ao se compararem.

dict()

A segunda estrutura mais popular de Python (depois de listas). Dicionarios estão em toda parte
e praticamente tudo em Python pode ser associado a um tipo de dict (mutavel ou read-only). Exemplo,
sao as keyword arguments das funções são implementadas como dicts, então toda chamada de função
cria e destroi pelo menos 1 dict.

Algumas curiosidades a nivel de implementação se seguem:

  • No CPython, a hash table do dict possui numero de slots em potência de 2
  • Cada slote tem 3 items: o ponteiro para a chave, o ponteiro pro valor e uma cópia do hash da chave
    (para acesso rápido, ao inves de pegar a chave e recomputar o hash).
  • A tabela é redimensionada quando é preenchida em 2/3 da capacidade. O fator de redimencionamento é escolhido baseada no numero de chaves:
    se for menos de 50000, o fator é 4, caso contrário, 2.
  • A maioria dos dicts tendem a ser pequenos, então para otimizar uso de memoria, uma tabela de 8 espaços é alocada pra um dicionario,
    cabendo em linhas de cache de 64bytes. Se o numero de chaves cresce para acima de 5, uma tabela maior é alocada

Pelo o que discorremos até aqui, dicionarios são conjuntos de objetos indexados por praticamente qualquer
valor arbitrario, desde que eles sejam hashables (os proprios dicionarios e listas nao podem ser pois são mutaveis).
O tipo é implementado como hash tables, dando um melhor desempenho na hora de procurar
valores. Como ja discutido, a busca é feita em tempo O(1) para uma chave, mesmo que as chaves não mantenham
um arranjo ordenado. Também discorremos sobre hashes e identificadores de objetos e como isso estabelece certas
regras para o uso de chaves em dicionários. Basicamente, os objetos chave não podem ser mutaveis pois
ao mudarem a função hash irá retornar um resultado hash diferente.

Um exemplo:

* Aplicar hash a listas por seus ids: Não da certo pois teria-se que manter a **referencia** a essa lista,
  e nao especificamente seu valor para ser utilizada como chave. Uma nova lista com os mesmos valores terão um
  id diferente:

.. code-block:: cpp
:linenos:

    mydict = {[1, 2]: '12'}
    print(mydict[[1, 2]])

KeyError exception é levantada, pois o id de [1, 2] é diferente do id de mydict

Conclusão

Pretendo discorrer mais sobre dicionários no futuro. Existem várias maneiras e
circunstâncias de utilização dessa estrutura de dados, como por exemplo
como usar o defaultdict ou o OrderedDict, formas mais pythonicas de
iterar chaves e/ou valores, valores default de chaves, dentre outras.

Referências

Segue uma lista de links que utilizei para escrever sobre o assunto:
<https://docs.python.org/3/reference/datamodel.html>_
<https://docs.python.org/3.6/faq/design.html>_
<https://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented>_
<https://stackoverflow.com/questions/39980323/dictionaries-are-ordered-in-python-3-6>_

`<http://algs4.cs.princeton.edu/34hash/>`_
`<https://dbader.org/blog/python-dictionaries-maps-and-hashtables>`_
`<https://codereview.stackexchange.com/questions/118110/python-hash-table-implementation>`_
`<http://planspace.org/20150111-a_great_python_book_explains_hash_tables/>`_

`<https://codeyarns.com/2012/04/12/implementation-of-dictionary-in-python/>`_
`<https://hg.python.org/cpython/file/tip/Objects/dictnotes.txt>`_

Add a comment

Your email address will not be published. Required fields are marked *