Hash tables

Data Structures and Algorithms in 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
Data Structures and Algorithms in Python

Structure

  • Each position: slot/bucket

Schematic representation of an empty hash table.

Data Structures and Algorithms in Python

Hash functions

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

Data Structures and Algorithms in 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
Data Structures and Algorithms in Python

Lookups

Schematic representation of a hash table with some values.

  • Find "lasagna"
    • hash("lasagna") -> 5
Data Structures and Algorithms in 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)$
Data Structures and Algorithms in 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
Data Structures and Algorithms in Python

Python dictionary

  • Empty dictionary
my_empty_dictionary = {}
  • Dictionary with items
my_menu = {
    'lasagna': 14.75,
    'moussaka': 21.15,
    'sushi': 16.05
}
Data Structures and Algorithms in 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
Data Structures and Algorithms in 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])
Data Structures and Algorithms in 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)])
Data Structures and Algorithms in Python

Python dictionary - modify

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

20
Data Structures and Algorithms in 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()
Data Structures and Algorithms in 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
Data Structures and Algorithms in 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
Data Structures and Algorithms in Python

Python dictionary - nested dictionaries

  • Nested dictionary
my_menu = {
  'sushi' : {
    'price' : 19.25,
    'best_served' : 'cold'
  },
  'paella' : {
    'price' : 15,
    'best_served' : 'hot'
  }
}
Data Structures and Algorithms in Python

Let's practice!

Data Structures and Algorithms in Python

Preparing Video For Download...