Hashmaps & Sets
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(1).
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?
# Only unique numbers are printed
#
# Why do you think Sets are in the same tech talk as Hashmaps/Hashtables?
# They only contain unique values
#
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?
#
#
# 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']
# What can you change to make sure there are no duplicate producers?
lover_album["producer"] = set(lover_album["producer"])
#
# 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?
lover_album["genre"].push("stuff")
#
# 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 k,v in lover_album["tracks"].items():
print("Track " + str(k) + ": " + 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()))
search()
# This is a very basic code segment, how can you improve upon this code?
#
# Abstract search parameter:
def search2(search):
if lover_album.get(search.lower()) == None:
print("Invalid Search")
else:
print(lover_album.get(search.lower()))
search2("producer")
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
+----------------------+---------------------------+
| Dictionaries | Lists |
+----------------------+---------------------------+
| Unordered | Ordered |
| Accessed by key | Accessed by index |
| Keys must be unique | Can have duplicates |
| Value can be any | Value can be any |
| object type | object type |
| Can't be sliced | Can be sliced |
| Can't be sorted | Can be sorted |
| Use curly braces {} | Use square brackets [] |
+---------------------+----------------------------+- Expand upon the code given to you, possible improvements in comments
- Build your own album showing features of a python dictionary
channel_orange_album = {
"title": "channel ORANGE",
"artist": "Frank Ocean",
"year": 2012,
"genre": ["Alternative R&B", "Neo-Soul"],
"tracks": {
1: "Start",
2: "Thinkin Bout You",
3: "Fertilizer",
4: "Sierra Leone",
5: "Sweet Life",
6: "Not Just Money",
7: "Super Rich Kids (feat. Earl Sweatshirt)",
8: "Pilot Jones",
9: "Crack Rock",
10: "Pyramids",
11: "Lost",
12: "White (feat. John Mayer)",
13: "Monks",
14: "Bad Religion",
15: "Pink Matter (feat. André 3000)",
16: "Forrest Gump",
17: "End"
}
}
- For Mr. Yeung's class: Justify your favorite Taylor Swift song, answer may effect seed
It is my pleasure to delve into the musical masterpiece that is "Shake It Off" by Taylor Swift. This song stands out among her many hits as a true representation of her unparalleled songwriting abilities and artistic vision.
Firstly, the infectious melody of "Shake It Off" is one that simply cannot be ignored. From the opening notes, listeners are drawn into the upbeat rhythm that sets the tone for the entire song. Swift's use of repetition throughout the chorus creates a singalong-worthy hook that is both memorable and catchy. Furthermore, the instrumental arrangement is perfectly balanced, blending horns, drums, and guitar to create a dynamic sound that complements Swift's vocals beautifully.
Beyond its musical merits, "Shake It Off" is a lyrical masterpiece. Swift's signature storytelling is on full display, as she takes listeners on a journey of self-discovery and resilience. The song's central message, to let go of negativity and embrace positivity, is one that resonates with people of all ages and backgrounds. Swift's ability to articulate this message through her lyrics is a testament to her songwriting prowess and demonstrates her ability to connect with her audience on a personal level.
Additionally, "Shake It Off" marks a significant departure from Swift's earlier works, showcasing her growth and evolution as an artist. The song's pop-infused sound was a departure from her country roots and signaled a shift towards a more mainstream sound. This willingness to take risks and explore new musical territories is a hallmark of Swift's career and has helped to solidify her status as a musical icon.
It is also worth noting that "Shake It Off" has had a lasting impact on popular culture. The song's music video, which features Swift showcasing various dance moves and outfits, has become iconic in its own right. The video has been viewed over 3 billion times on YouTube and has inspired countless parodies and tributes. This cultural impact further cements the song's status as one of Swift's most enduring and beloved works.
In conclusion, "Shake It Off" is a true masterpiece of modern pop music. Its infectious melody, powerful lyrics, and lasting impact on popular culture have cemented its status as one of Taylor Swift's greatest songs. I can confidently say that "Shake It Off" is not only an artistic triumph but also a cultural touchstone that will continue to inspire and resonate with people for years to come.