Data Structures- Hashmaps, Sets, Hash Tables, Hashing and Collisions
Observing hashmaps with python dictionaries
- What is a Hashtable/Hashmap?
- What is Hashing and Collision?
- What is a Set?
- Dictionary Example
- Hacks
- Favorite Taylor Swift Song Wildest Dreams
What is a Hashtable/Hashmap?
A hashtable is a data structure that 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(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?
my_set = set([1, 2, 3, 2, 1])
print(my_set)
# What do you notice in the output?
# I notice that the output is the numbers in order and there are no duplicates
#
# Why do you think Sets are in the same tech talk as Hashmaps/Hashtables?
# They are able to be used with each other so that you can use them as filtering for potential output.
#
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?
# Some data structures I see are, an array and list, and a dictioinary. All these different structures have different uses throughout
#
# Printing the dictionary
print(lover_album)
print(set(lover_album.get('tracks')))
# or
print(set(lover_album['tracks']))
print(lover_album.get('tracks')[4])
# or
print(lover_album['tracks'][4])
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?
#
#
# 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 can use the set function so that the 2nd taylor swift is removed from the code.
#
# 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
for album_title, album_details in lover_album.items():
print("Album: " + album_title)
print("-" * 40)
for key, value in album_details.items():
if key == "tracks":
print(key.title() + ":")
for track in value:
print("- " + track)
else:
print(key.title() + ": " + str(value))
print("\n")
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?
# You can improve upon this code segment by having a better if statements which has the capability to get more information in the search from the user
# Its important that the code also run smoothly with adding new featuresn
Hacks
- Answer ALL questions in the code segments
- Create a diagram or comparison illustration (Canva).
- What are the pro and cons of using this data structure?
- Dictionary vs List
- Expand upon the code given to you, possible improvements in comments
-
Build your own album showing features of a python dictionary
-
For Mr. Yeung's class: Justify your favorite Taylor Swift song, answer may effect seed
import random
# Define the lover_album dictionary with some key-value pairs representing songs
lover_album = {
"blank space": "Nice to meet you, where you been?",
"style": "You got that James Dean daydream look in your eye",
"shake it off": "Cause the players gonna play, play, play, play, play",
"wildest dreams": "Say you'll remember me standing in a nice dress, staring at the sunset"
}
# Define a function to search for a song in the dictionary based on user input
def search():
search_term = input("What would you like to know about the album? ").lower()
if search_term in lover_album:
print(lover_album[search_term])
else:
print("Invalid search term. Please try again.")
# Define a function to add a new song to the dictionary
def add_song():
song_name = input("Enter the name of the song: ").lower()
if song_name in lover_album:
print("This song already exists in the album.")
else:
song_lyrics = input("Enter the lyrics of the song: ")
lover_album[song_name] = song_lyrics
print("Song added to the album.")
# Define a function to randomly select a song from the dictionary
def random_song():
song_name = random.choice(list(lover_album.keys()))
print(song_name + ": " + lover_album[song_name])
# Define a function to display all the songs in the album
def display_all_songs():
print("Here are all the songs in the album:")
for song_name in lover_album:
print("- " + song_name)
# Prompt the user to choose an option
while True:
user_input = input("Enter a number to choose an option: \n1. Search for a song \n2. Add a new song \n3. Get a random song \n4. Display all songs \n5. Exit\n")
if user_input == "1":
search()
elif user_input == "2":
add_song()
elif user_input == "3":
random_song()
elif user_input == "4":
display_all_songs()
elif user_input == "5":
break
else:
print("Invalid input. Please enter a number between 1 and 5.")
Favorite Taylor Swift Song Wildest Dreams
"Wildest Dreams" is a song that tells a story of wanting something or someone you can't have. The song starts with an opening line that sets the tone for the rest of the song: "He said, 'Let's get out of this town, drive out of the city, away from the crowds'". This line suggests a sense of longing to escape the current situation and find something better.
As the song progresses, Taylor Swift's emotive vocals convey a sense of yearning and desire that is both captivating and relatable. The lyrics paint a picture of a love that is intense and all-consuming, yet ultimately unattainable. The chorus of the song goes: "Say you'll remember me, standing in a nice dress, staring at the sunset, babe. Red lips and rosy cheeks, say you'll see me again even if it's just in your wildest dreams".
The chorus captures the essence of the song - the longing for someone who is out of reach. It's a powerful sentiment that many people can relate to, whether it's because of unrequited love or a missed opportunity. The music of the song complements the lyrics perfectly, with a haunting melody that adds to the sense of nostalgia and longing.
What makes "Wildest Dreams" such a beloved song is its universal appeal. It's a song that transcends age, gender, or cultural boundaries. Whether you're a teenager experiencing your first crush or a middle-aged person reminiscing about a lost love, the sentiment expressed in "Wildest Dreams" can resonate with you on a deep level.
In conclusion, "Wildest Dreams" is a song that captures the essence of longing and desire in a way that few others can. It's a timeless classic that continues to touch the hearts of people around the world. The lyrics, vocals, and music all come together to create a masterpiece that can evoke powerful emotions in anyone who listens to it.