Maps and Hashing

Dec. 4, 2020

Vuong Huynh

Maps

The defining characteristic of a map is its key-value structure. Maps are similar to dictionaries in terms of key and value; Word is the key and definitions are the values of that key.

Set is an abstract data type similar to a list. However, all elements of a set are identical.

Thus, the keys in a map are a set.

Python Dictionaries

In Python, the map concept appears as a built-in data type called a dictionary. A dictionary contains key-value pairs. Dictionaries are wonderfully flexible. We can store primitive data types, lists, or even dictionaries inside a dictionary.

Python Dictionaries Quiz

You're going to work on a dictionary that stores cities by country and continent. One is done for you - the city of Mountain View is in the USA, which is in North America.

locations = {'North America': {'USA': ['Mountain View']}

You need to add the cities listed below by modifying the structure. Then, you should print out the values specified by looking them up in the structure.

Cities to add:

Bangalore (India, Asia)

Atlanta (USA, North America)

Cairo (Egypt, Africa)

Shanghai (China, Asia)

locations['North America']['USA'].append('Atlanta')
locations['Asia'] = {'India': ['Bangalore']}
locations['Asia']['China'] = ['Shanghai']
locations['Africa'] = {'Egypt': ['Cairo']}

The variable locations now becomes:

locations =

{'North America': {'USA': ['Mountain View', 'Atlanta']}, 'Asia': {'India': ['Bangalore'], 'China': ['Shanghai']}, 'Africa': {'Egypt': ['Cairo']}}

Now print a list of all cities in the USA in alphabetic order.

for value in sorted(locations['North America']['USA']):
    print(value)

The result is:

Atlanta

Mountain View

Next, print all cities in Asia, in alphabetic order, next to the name of the country

city_country = []

for key, value in sorted(locations['Asia'].items()):
    value_key = value[0] + ' - ' + key
    city_country.append(value_key)

for item in sorted(city_country):
    print(item)

The output:

Bangalore - India

Shanghai - China

Hashing

Hash Functions

The purpose of a hash function is to transform some value into one that can be stored and retrieved easily.