Hashmaps, Sets, Hash Tables, Hashing and Collisions Notes
Observing hashmaps with python dictionaries
What is a Hashtable/Hashmap?
A hashtable is a data structure that has 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), or constant.
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.
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?
(Questions are answered in the code comments.)
my_set = set([1, 2, 3, 2, 1])
print(my_set)
# What do you notice in the output?
# the output only contains the first instance of each of the unique numbers
# the output also has brackets around it like a dictionary
# according to a test, it also automatically orders it by increasing value
# Why do you think Sets are in the same tech talk as Hashmaps/Hashtables?
# dictionaries also cannot have duplicate keys, like these sets
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?
# i see strings, integers, lists, and a nested dictionary inside the dictionary
# Printing the dictionary
print(lover_album)
These are two different methods to retrieve the data behind a certain key.
print(lover_album.get('tracks'))
# or
print(lover_album['tracks'])
These are, similarly, alternatives to each other.
print(lover_album.get('tracks')[4])
# or
print(lover_album['tracks'][4])
I made it a set to prevent the duplicate Taylor Swift from showing up.
lover_album["producer"] = set(['Taylor Swift', 'Jack Antonoff', 'Joel Little', 'Taylor Swift', 'Louis Bell', 'Frank Dukes'])
# What can you change to make sure there are no duplicate producers?
# you could turn the list of producers into a set
# Printing the dictionary
print(lover_album)
lover_album["tracks"].update({19: "All Of The Girls You Loved Before"})
# How would add an additional genre to the dictionary, like electropop?
# you would .update the ["genre"] key by appending "electropop"
# Printing the dictionary
print(lover_album)
"""
for k,v in lover_album.items(): # iterate using a for loop for key and value
print(str(k) + ": " + str(v))
"""
# Write your own code to print tracks in readable format
# you can see that below; I also reformatted the other data
for k, v in lover_album.items():
if type(v) == list or type(v) == set:
print(str(k).capitalize() + ": ", end="")
print(", ".join(v))
elif type(v) == dict:
print(str(k).capitalize() + ":")
for num, track in v.items():
print("\t" + str(num) + ": " + track)
else:
print(str(k).capitalize() + ": " + str(v))
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()))
# This is a very basic code segment, how can you improve upon this code?
# I think it could be improved upon by reformatting the output to be more readable
# It would also be good to tell the user what their options are
# I did all of this below
def search(): #here is search but better
info = []
for k, v in lover_album.items():
info.append(k)
search = input("What would you like to know about the album? (Options: " + ", ".join(info) + ")")
if lover_album.get(search.lower()) == None:
print("Invalid Search")
else:
data = lover_album.get(search.lower())
if type(data) == list or type(data) == set:
print(search.capitalize() + ": ", end="")
print(", ".join(data))
elif type(data) == dict:
print(search.capitalize() + ":")
for num, track in data.items():
print("\t" + str(num) + ": " + track)
else:
print(search.capitalize() + ": " + str(data))
search()
Hacks
Hacks Completed Throughout the Lesson
- Answer ALL questions in the code segments
I made sure to do that.
- Expand upon the code given to you, possible improvements in comments
For each of the code segments with possible improvements, I went through and improved them.
One way I did this was using the .capitalize() function to make the keys into grammatically-correct headings. I also improved the displays more comprehensively by reformatting the data displayed depending on the type of data using the type() function.
For example:
Data sets with type
listor typesetcould be handled the same way:to prevent the code formatting brackets from showing up, I used", ".join(list)in the print statement to get rid of it. Data sets with typedictionarycould be iterated through to display the key, a colon, and the value using thefor k,v in dict.items()format. I decided to tab intent each of these instances to set it apart from the "Tracks" header in this specific case.All singular data sets were just displayed in a single print statement, with the key of the key, a colon, and the value.
Canva Diagrams
.png)
Personal Album Dictionary
My friend has been trying to get me to listen to music by a certain artist (Rav) for a while now, and I just recently listened through one of his more popular albums "Beneath the Toxic Jungle". I noticed that it contained a lot of features that weren't mentioned in the song titles, so I decided that, in the track list, I would list all of the artists involved along with the title of the song. This shows the ability to nest dictionaries.
I then made a system to sift through the data and display it in an appealing way.
Since in previous examples, the get function was used, I decided to pull information from the keys in the other format to show understanding.
from datetime import datetime, date
# Creating a dictionary with information about the album "BENEATH THE TOXIC JUNGLE"
btj_album = {
"title": "BENEATH THE TOXIC JUNGLE", #dictionaries can store strings,...
"artist": "Rav",
"date": datetime(2015, 12, 19), #date objects,...
"genres": ["Abstract Hip Hop", "Jazz Rap", "Lo-Fi Hip Hop, Experimental Hip Hop"], #lists,...
"tracklist": { #and even more dictionaries
1: {"title": "1,000 Years In The Sea", "mixer": ["Kill Bill"], "producers":["Ljones"]},
2: {"title": "Solanine", "producers":["dream Entact."]},
3: {"title": "Save Face As...", "features":["Kill Bill"], "mixer":["Kill Bill"], "producers":["Yuni Wa"]},
4: {"title": "Devil Fruit Smoothies", "features":["JINZO THE TRAP LORD"], "mixer":["Kill Bill"], "producers":["MAITRO", "Plaid"]},
5: {"title": "Addlerall", "features":["Scuare"], "mixer":["Scuare"], "producers":["Birocratic"]},
6: {"title": "A Better Place", "features":["Ashido Brown", "Rekcahdam"], "mixer":["Rekcahdam"], "producers":["Edo Lee"]},
7: {"title": "Lavender", "features":["Kill Bill"], "producers":["Datfootdive", "Moar"]},
8: {"title": "Get Mine II", "features":["Scuare", "suddlenuance"], "mixer":["Kill Bill"], "producers":["Tantu"]},
9: {"title": "1,000 Years In The Mountains", "producers":["Pacific Yew"]},
"Bonus Track": {"title": "Tachyon", "producers":["Raistlin"]}
}, #contributors are all in list form to allow for proper iteration through each one
}
feat_list = [] #creating initial lists of features, mixers, producers, and all contributors
mix_list = []
prod_list = []
cont_list = []
for num, track in btj_album["tracklist"].items():
for k, v in track.items():
if k == "features":
for p in v:
feat_list.append(p)
elif k == "mixer":
for p in v:
mix_list.append(p)
elif k == "producers":
for p in v:
prod_list.append(p)
if k != 'title':
for p in v:
cont_list.append(p)
btj_album["features"] = set(feat_list) #a set of filtered info, no duplicates
btj_album["mixers"] = set(mix_list) #same formatting below
btj_album["producers"] = set(prod_list)
btj_album["contributors"] = set(cont_list) #list of all outside contributors
# process to print album information
def print_album(album):
print(f"\"{album['title']}\" by {album['artist']}") #title and artist display
print(f"\tRelease Date: {album['date'].strftime('%m-%d-%Y')}") #release date format
print(f"\tGenres: " + ", ".join(album['genres'])) #genre listing, formatted
print(f"\tTracklist:") #header for tracklist
for part, track in album['tracklist'].items():
print(f"\t\t{str(part)}: {track['title']}") #leading with title, primary
for key, info in track.items():
if key != "title": #filtered to avoid double printing title
print(f"\t\t\t\t{key.capitalize()}: " + ", ".join(info)) #info and details
print(f"Contributors: " + ", ".join(btj_album['contributors'])) #contributor list, no repeats
print_album(btj_album)
I added code comments throughout to describe what's going on.
Yes, that friend was AJ. I'm like 90% sure he's also gonna do an album by Rav.
My Favorite Taylor Swift Song
I don't need ChatGPT to help me argue in favor of "Teardrops On My Guitar". To be completely honest, I've never been a fan of the more recent Taylor Swift music, though that's mostly due to the genre. It's nothing personal. I also wouldn't say I'm a fan of country by any means, but, especially in my more recent personal life, country music has adopted a sort of nostalgic value.
This song has quite literally followed me through my life. Being released on her 2006 self-titled debut album "Taylor Swift," it (along with her first single "Tim McGraw") earned her some of her first share of popularity. It was cowritten by Liz Rose, who received a Songwriter of the Year award from Society of European Stage Authors and Composers the following year for her work on these two singles. In an interview about the song, Rose talked about how Swift was good at expressing the emotions she wished to portray in the song to her. Rose made it very clear that she was not stepping in or creating a corporate, filtered expression of Swift's idea, as she wanted Swift to "be the vehicle." It was produced by Nathan Chapman, known for his work on many other early Taylor Swift songs as well as other artists like Lady Antebellum and, more recently, Revival.
If you know this song well enough, you know I'm failing to address a big elephant in the room. The elephant's name is "Drew."
For my whole life, my family has, mockingly or not, sung this song around me, played it in the car, etc. "Drew looks at me" was a lyric that wrapped itself around my brain fairly often. My dad bought her debut album on iTunes just so that they could play it in my mom's old van, which couldn't play music from my dad's phone unless it was saved through iTunes. When I picked up guitar, my parent said it was the first song I should learn. My girlfriend, an avid Taylor Swift and country fan, referenced it not long after I met her. If it's not clear, I have a lot of personal associations with this song.
And speaking of playing it on guitar, it's a very easy song to learn if you strip it of all of the complicated bits. The fact that it comes with so many potential variations to learn, though, like the somewhat melancholy Dsus4 chord in the second verse and the various pinky-finger add-ons that you can choose to play.
There's lots of other stuff I could talk about with this song, like how the actual "Drew" is actually named "Andrew," like me. Or how the "Drew" from the song is now in jail for child abuse, while, fun fact, I'm not. But I think I'll leave it at that. I'm not trying to convince you to change your mind on your favorite. But now, if you ever hear that song again, you might think of me. And I think that's funny.