02_Hash Maps and Sets
Hash Maps and Hash Sets.
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 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 Functions
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.")