Hash tables

Datenstrukturen und Algorithmen 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

Structure

Each position: slot/bucket

Schematic representation of an empty hash table.

Hash functions

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

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

Lookups

Schematic representation of a hash table with some values.

Find "lasagna"
- hash("lasagna") -> 5

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)$

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

Python dictionary

Empty dictionary

my_empty_dictionary = {}

Dictionary with items

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

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

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])

Python dictionary - insert

my_menu['samosas'] = 13

print(my_menu.items())

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

Python dictionary - modify

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

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()

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

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

Python dictionary - nested dictionaries

Nested dictionary

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

Let's practice!

Datenstrukturen und Algorithmen in Python