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

Posted on Wed 31 May 2017 in tech

Introdução

Neste ultimo sábado, eu dei uma breve palestra sobre dicionários no Meetup 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

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.

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

1
2
3
4
5
6
7
8
9
     # 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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
     # 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:
1
2
     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.