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

Introdução

Quem, onde, como?

Francisco Borges Fernandes Júnior

O quê?

(ou uma breve intro a hashtables)

Por tras dos panos

Dicionários

Estruturas de dados

Estruturas de dados

Hash tables

Hash tables

Hash tables: Funções hash

Funções hash: exemplo

Inteiros: quick and dirty


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

Funções hash: exemplo

Strings : polyhash


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)

Hash tables: Colisões

Colisões

Python e hashtables

Objetos em Python

Dicionários e hashtables

id() e hash()

id() e hash()

dict()

Curiosidades: