Hash tables

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Definition

  • Stores a collection of items

  • Key-value pairs

      lasagna: 14.75
  moussaka: 21.15
  sushi: 16.05

  • Almost every programming language has a built-in hash table:

    • hashes, hash maps, dictionaries, associative arrays
    • Python: dictionaries
Structures de données et algorithmes en Python

Structure

  • Each position: slot/bucket

Schematic representation of an empty hash table.

Structures de données et algorithmes en Python

Hash functions

Schematic representation of an empty hash table. The price of the lasagna has been inserted on the fifth position.

Structures de données et algorithmes en Python

Hash functions

Schematic representation of a hash table with the words "Hash function" in the middle of an arrow that maps the word "Lasagna" with the value on the fifth position.

  • Every time a hash function is applied
    • must return the same value for the same input
Structures de données et algorithmes en Python

Lookups

Schematic representation of a hash table with some values.

  • Find "lasagna"
    • hash("lasagna") -> 5
Structures de données et algorithmes en Python

Lookups

Schematic representation of a hash table with some values. The value on the fifth position is colored green.

  • Find "lasagna"
    • hash("lasagna") -> 5
    • return 14,75
  • $O(1)$
Structures de données et algorithmes en Python

Collisions

  • Hash functions can return same output for different inputs
  • hash("moussaka") -> 1

Schematic representation of a hash table with some values. The value on the first position is colored yellow.

  • insert: moussaka -> 21,15
  • Collision!
    • must be resolved
    • several techniques
Structures de données et algorithmes en Python

Python dictionary

  • Empty dictionary
my_empty_dictionary = {}
  • Dictionary with items
my_menu = {
    'lasagna': 14.75,
    'moussaka': 21.15,
    'sushi': 16.05
}
Structures de données et algorithmes en Python

Python dictionary - 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
Structures de données et algorithmes en Python

Python dictionary - items, keys & values

  • Get items
print(my_menu.items())

dict_items([('lasanga', 14.75), 
            ('moussaka', 21.15),
            ('sushi', 16.05)])
  • Get keys
print(my_menu.keys())

dict_keys(['lasanga', 'moussaka', 'sushi'])
  • Get values
print(my_menu.values())

dict_values([14.75, 21.15, 16.05])
Structures de données et algorithmes en Python

Python dictionary - insert

my_menu['samosas'] = 13

print(my_menu.items())

dict_items([('lasanga', 14.75), ('moussaka', 21.15), ('sushi', 16.05), ('samosas', 13)])
Structures de données et algorithmes en Python

Python dictionary - modify

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

20
Structures de données et algorithmes en Python

Python dictionary - remove

  • Deletes a dictionary completely
del my_menu
  • Removes a key-value pair
del my_menu["sushi"]
  • Empties a dictionary
my_menu.clear()
Structures de données et algorithmes en Python

Python dictionary - iterate

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
Structures de données et algorithmes en Python

Python dictionary - iterate

for dish in my_menu:
  print(dish)

lasagna
moussaka
sushi

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

14.75
21.15
16.05
Structures de données et algorithmes en Python

Python dictionary - nested dictionaries

  • Nested dictionary
my_menu = {
  'sushi' : {
    'price' : 19.25,
    'best_served' : 'cold'
  },
  'paella' : {
    'price' : 15,
    'best_served' : 'hot'
  }
}
Structures de données et algorithmes en Python

Let's practice!

Structures de données et algorithmes en Python

Preparing Video For Download...