02_Hash Maps and Sets

• Hash Cheatsheet
• Hash Functions
• Hash Map
• Hash Set

Hash Cheatsheet

As some might know sets in python can contain only unique elements. “Similar to hash table, a hash set is also a collection of objects. In hash table, data was stored in the form of key-value pairs, whereas in hash sets, the data is stored as objects. A hash set internally uses the hash table data structure to store data items. Just like a set, a hash set also does not allow storage of duplicate elements.”

Hashing is the most common example of a space-time tradeoff. Instead of linearly searching an array every time to determine if an element is present, which takes O(n) time, we can traverse the array once and hash all the elements into a hash table. 

Basic	HashSet	HashMap
Implements	Set interface	Map interface
Duplicates	No	Yes duplicates values are allowed but no duplicate key is allowed
Dummy values	Yes	No
Objects required during an add operation	1	2
Adding and storing mechanism	HashMap object	Hashing technique
Speed	It is comparatively slower than HashMap	It is comparatively faster than HashSet because of hashing technique has been used here.
Null	Have a single null value	Single null key and any number of null values
Insertion Method	Only one value is required for the insertion process. Add() function is used for insertion	Two values are required for the insertion process. Put() function is used for insertion.
Data storage	The data is stored as objects.	The data is stored as key-value pair.
Complexity	O(n)	O(1)

Hash Functions

Hash Map

 

# Creating a hash table to store fruits based on their first letter
hash_table = {}
hash_table['A'] = 'Apple'
hash_table['B'] = 'Banana'
hash_table['O'] = 'Orange'

# Accessing a fruit based on its first letter
print(hash_table['A'])  # Output: 'Apple'
print(hash_table['B'])  # Output: 'Banana'
print(hash_table['O'])  # Output: 'Orange'

Hash Set

Example regular set:

# Regular Set (Without Hashing)
my_set = {3, 7, 1, 9, 5}

# Searching for an element in the set
search_element = 7
if search_element in my_set:
    print("Element found in the set!")
else:
    print("Element not found in the set.")

------------------------------------------------------
Example hashset:

# Hash Set (With Hashing)
my_hash_set = set()

# Adding elements to the hash set
my_hash_set.add(3)
my_hash_set.add(7)
my_hash_set.add(1)
my_hash_set.add(9)
my_hash_set.add(5)

# Searching for an element in the hash set
search_element = 7
if search_element in my_hash_set:
    print("Element found in the hash set!")
else:
    print("Element not found in the hash set.")