Data Structures- Hashmaps, Sets, Hash Tables, Hashing and Collisions
Observing hashmaps with python dictionaries
What is a Hashtable/Hashmap?
A hashtable is a data structure with a collection of key-value pairs, where each key maps to a value, and the keys must be unique and hashable.
- In Python there is a built in hashtable known as a dictionary.
The primary purpose of a hashtable is to provide efficient lookup, insertion, and deletion operations. When an element is to be inserted into the hashtable, a hash function is used to map the key to a specific index in the underlying array that is used to store the key-value pairs. The value is then stored at that index. When searching for a value, the hash function is used again to find the index where the value is stored.
The key advantage of a hashtable over other data structures like arrays and linked lists is its average-case time complexity for lookup, insertion, and deletion operations.
-
The typical time complexity of a hashtable is O(1).
-
Looking for a value in a dictionary would have a time complexity of O(1), because each key only has 1 value. If you know what the key is you will know what the value is.
What is Hashing and Collision?
Hashing is the process of mapping a given key to a value in a hash table or hashmap, using a hash function. The hash function takes the key as input and produces a hash value or hash code, which is then used to determine the index in the underlying array where the value is stored. The purpose of hashing is to provide a quick and efficient way to access data, by eliminating the need to search through an entire data structure to find a value.
However, it is possible for two different keys to map to the same hash value, resulting in a collision. When a collision occurs, there are different ways to resolve it, depending on the collision resolution strategy used.
- duplicate key = collision
- no need to hash in Python dictionary
Python's dictionary implementation is optimized to handle collisions efficiently, and the performance of the dictionary is generally very good, even in the presence of collisions. However, if the number of collisions is very high, the performance of the dictionary can degrade, so it is important to choose a good hash function that minimizes collisions when designing a Python dictionary.
What is a Set?
my_set = set([1, 2, 3, 2, 1])
print(my_set)
# What do you notice in the output?
# In the output I notice it prints the outputs only once so there is no repeats.
# In the output I notice it prints in ascending order or in order that it was originally in, without repeats
# Why do you think Sets are in the same tech talk as Hashmaps/Hashtables?
# I think sets are in the same tech talk as Hashmaps/Hashtables because dictionaries also cannot have duplicates.
#
lover_album = {
"title": "Lover",
"artist": "Taylor Swift",
"year": 2019,
"genre": ["Pop", "Synth-pop"],
"tracks": {
1: "I Forgot That You Existed",
2: "Cruel Summer",
3: "Lover",
4: "The Man",
5: "The Archer",
6: "I Think He Knows",
7: "Miss Americana & The Heartbreak Prince",
8: "Paper Rings",
9: "Cornelia Street",
10: "Death By A Thousand Cuts",
11: "London Boy",
12: "Soon You'll Get Better (feat. Dixie Chicks)",
13: "False God",
14: "You Need To Calm Down",
15: "Afterglow",
16: "Me! (feat. Brendon Urie of Panic! At The Disco)",
17: "It's Nice To Have A Friend",
18: "Daylight"
}
}
# What data structures do you see?
# list and dictionary
# integers and strings
# Printing the dictionary
print(lover_album)
print(lover_album.get('tracks'))
# or
print(lover_album['tracks'])
print(lover_album.get('tracks')[4])
# or
print(lover_album['tracks'][4])
lover_album["producer"] = ['Taylor Swift', 'Jack Antonoff', 'Joel Little', 'Taylor Swift', 'Louis Bell', 'Frank Dukes']
# set equal to data type
# What can you change to make sure there are no duplicate producers?
# use a set to print the data without duplicates
#
# Printing the dictionary
#print(lover_album)
albumSet = set(lover_album["producer"])
print(albumSet)
lover_album["tracks"].update({19: "All Of The Girls You Loved Before"})
# How would you add an additional genre to the dictionary, like electropop?
# You can add a list within the dictionary
#
# Printing the dictionary
print(lover_album)
Adding electropo genre to the lover album dictionary
lover_album["genre"].append("electropop")
# print(lover_album["genre"])
albumSet = set(lover_album["genre"])
print(albumSet)
for k,v in lover_album.items(): # .items() used to iterate using a for loop for key and value
print(str(k) + ": " + str(v)) # k and v variables for keys and values
# Write your own code to print tracks in readable format
# This can be rewritten in a table so it is a readable format
#
Write your own code to print tracks in readable format DataFrame using Pandas
import pandas as pd
print(pd.DataFrame(lover_album.items(),columns={'Value','key'}))
Write your own code to print tracks in readable format Printing out in JSON
lover_album = {
"title": "Lover",
"artist": "Taylor Swift",
"year": 2019,
"genre": ["Pop", "Synth-pop"],
"tracks": {
1: "I Forgot That You Existed",
2: "Cruel Summer",
3: "Lover",
4: "The Man",
5: "The Archer",
6: "I Think He Knows",
7: "Miss Americana & The Heartbreak Prince",
8: "Paper Rings",
9: "Cornelia Street",
10: "Death By A Thousand Cuts",
11: "London Boy",
12: "Soon You'll Get Better (feat. Dixie Chicks)",
13: "False God",
14: "You Need To Calm Down",
15: "Afterglow",
16: "Me! (feat. Brendon Urie of Panic! At The Disco)",
17: "It's Nice To Have A Friend",
18: "Daylight"
}
}
import json
print(json.dumps(lover_album, indent=4, sort_keys=True))
def search():
search = input("What would you like to know about the album?")
if lover_album.get(search.lower()) == None:
print("Invalid Search")
else:
print(lover_album.get(search.lower()))
search()
# This is a very basic code segment, how can you improve upon this code?
# I can improve this code by implementing garbage checking, or more simply, adding an algorithm that is able to identify if a user's song might be a different album's,
# so using different dictionaries and making it so that the algorithm identifies which kind of album the user's input song is from.
Hacks
-
Answer ALL questions in the code segments
-
Expand upon the code given to you, possible improvements in comments
- For Mr. Yeung's class: Justify your favorite Taylor Swift song, answer may effect seed
Blank Space, You Belong With Me, Wildest Dreams
- All of these songs communicate Taylor's failed relationships and how men literally suck. It shows how she is a hopeless romantic and honestly I think I am too. When I was younger and first heard these songs I never really understood them to the extend I did now. Not saying that I have been in love but I have experienced things that confirm her lyrics to be true, how "boys only want love when it's torture", or how "she doesn't get your humor like I do" and "I know you better than that. Hey, what you doing with a girl like that?" GUYS LITERALLY SUCK MR.YEUNG. TAYLOR SWIFT GETS ME THROUGH STUFF. Like a girl could have it all, be so well-rounded:smart, funny, has passions and goals and be decently pretty, but a guy would throw all of that away to be with a really pretty girl with much less attributes (no offense to her). But all throughout these failed relationships Taylor Swift was able to bounce back and keep growing. She did not lose sight of herself or change herself for these useless men. I hope I can do the same.
- Create a diagram or comparison illustration (Canva).
- What are the pro and cons of using this data structure (dictionary)?
- Dictionary vs List
from IPython.display import Image, display
from pathlib import Path # https://medium.com/@ageitgey/python-3-quick-tip-the-easy-way-to-deal-with-file-paths-on-windows-mac-and-linux-11a072b58d5f
# prepares a series of images
def image_data(path=Path("images/"), images=None): # path of static images is defaulted
if images is None: # default image
images = [
{'source': "Canva", 'label': "Dictionary Pros and Cons ", 'file': "dictionaryprocon.png"}
]
for image in images:
# File to open
image['filename'] = path / image['file'] # file with path
return images
def image_display(images):
for image in images:
display(Image(filename=image['filename']))
# Run this as standalone tester to see sample data printed in Jupyter terminal
if __name__ == "__main__":
# display default images from image_data()
default_images = image_data()
image_display(default_images)
from IPython.display import Image, display
from pathlib import Path # https://medium.com/@ageitgey/python-3-quick-tip-the-easy-way-to-deal-with-file-paths-on-windows-mac-and-linux-11a072b58d5f
# prepares a series of images
def image_data(path=Path("images/"), images=None): # path of static images is defaulted
if images is None: # default image
images = [
{'source': "Canva", 'label': "Dictionary vs List ", 'file': "DictionaryvsList.png"}
]
for image in images:
# File to open
image['filename'] = path / image['file'] # file with path
return images
def image_display(images):
for image in images:
display(Image(filename=image['filename']))
# Run this as standalone tester to see sample data printed in Jupyter terminal
if __name__ == "__main__":
# display default images from image_data()
default_images = image_data()
image_display(default_images)
Build your own album showing features of a python dictionary
SOUR_album = {
"title": "SOUR",
"artist": "Olivia Rodrigo",
"year": 2021,
"genre": ["Pop", "Alternative-indie"],
"tracks": {
1: "brutal",
2: "traitor",
3: "drivers license",
4: "1 step forward, 3 steps back",
5: "deja vu",
6: "good 4 u",
7: "enough for you",
8: "happier",
9: "jealousy, jealousy",
10: "favorite crime",
11: "hope ur ok",
},
"duration": {
1: "2:23",
2: "3:49",
3: "4:02",
4: "2:43",
5: "3:35",
6: "2:58",
7: "3:22",
8: "2:55",
9: "2:53",
10: "2:32",
11: "3:29",
}
}
print(SOUR_album)
print(SOUR_album["genre"])
print(SOUR_album['tracks'][1] + " " + SOUR_album['duration'][1])
import pandas as pd
newalbum = pd.Series(SOUR_album)
print(newalbum)