Tabelas hash

Estruturas de Dados e Algoritmos em Python

Miriam Antona

Software engineer

Definição

• Armazena uma coleção de itens

• Pares chave-valor

    lasagna: 14.75
    moussaka: 21.15
    sushi: 16.05
  

• Quase toda linguagem tem tabela hash embutida:

  • hashes, hash maps, dicionários, arrays associativos
  • Python: dicionários

Estrutura

• Cada posição: slot/bucket

Funções hash

Funções hash

• Toda vez que uma função hash é aplicada
  • deve retornar o mesmo valor para a mesma entrada

Buscas

• Buscar "lasagna"
  • hash("lasagna") -> 5

Buscas

• Buscar "lasagna"
  • hash("lasagna") -> 5
  • retorna 14,75
• $O(1)$

Colisões

• Funções hash podem retornar o mesmo resultado para entradas diferentes
• hash("moussaka") -> 1

• inserir: moussaka -> 21,15
• Colisão!
  • precisa ser resolvida
  • várias técnicas

Dicionário em Python

• Dicionário vazio

my_empty_dictionary = {}

• Dicionário com itens

my_menu = {
    'lasagna': 14.75,
    'moussaka': 21.15,
    'sushi': 16.05
}

Dicionário em Python - get

print(my_menu['sushi'])

16.05

print(my_menu['paella'])

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'paella'

print(my_menu.get('paella'))

None

Dicionário em Python - items, keys e values

• Obter itens

print(my_menu.items())

dict_items([('lasanga', 14.75), 
            ('moussaka', 21.15),
            ('sushi', 16.05)])

• Obter chaves

print(my_menu.keys())

dict_keys(['lasanga', 'moussaka', 'sushi'])

• Obter valores

print(my_menu.values())

dict_values([14.75, 21.15, 16.05])

Dicionário em Python - inserir

my_menu['samosas'] = 13

print(my_menu.items())

dict_items([('lasanga', 14.75), ('moussaka', 21.15), ('sushi', 16.05), ('samosas', 13)])

Dicionário em Python - modificar

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

20

Dicionário em Python - remover

• Exclui um dicionário inteiro

del my_menu

• Remove um par chave-valor

del my_menu["sushi"]

• Esvazia um dicionário

my_menu.clear()

Dicionário em Python - iterar

for key, value in my_menu.items():
  print(f"\nkey: {key}")
  print(f"value: {value}")

key: lasagna
value: 14.75

key: moussaka
value: 21.15

key: sushi
value: 16.05

Dicionário em Python - iterar

for dish in my_menu:
  print(dish)

lasagna
moussaka
sushi

for prices in my_menu.values():
  print(prices)

14.75
21.15
16.05

Dicionário em Python - dicionários aninhados

• Dicionário aninhado

my_menu = {
  'sushi' : {
    'price' : 19.25,
    'best_served' : 'cold'
  },
  'paella' : {
    'price' : 15,
    'best_served' : 'hot'
  }
}

Vamos praticar!

Estruturas de Dados e Algoritmos em Python