Hash Table
Created : February 02, 2021
Written in Python.
- Used to map a given value with a particular key for faster access of elements.
-
Data is stored in an array format, where each data value has its own unique index value.
- Address or the index value is generated from a hash function.
- That makes accessing the data faster as the index value behaves as a key for the data value.
- Hash table stores key-value pairs, but the key is generated through a hashing function.
- Accessing data becomes very fast with the index of data.
Linear Probing
If the hashing creates an already used index of the array,
→ Search the next empty location in the array.
Basic Operations
- Search
- Insert
- Delete
Big-O Complexity for Hash Table
-
Time complexity
- Insertion/Deletion: O(1)
- Search: O(1)
- Space complexity: O(n)
Implementation
- Dictionary data types represent the implementation of hash tables in Python.
- Keys of the dictionary are hashable.
→ generated by hashing function which generates unique result for each unique value.
- The order of data elements in a dictionary is not fixed.
# Declare a dict
dict = {
'Name': 'Happy',
'Age': 3,
'Breed': 'Golden Retriever'
}
# Access values with its key
>>> dict['Name']
Happy
>>> dict['Age']
3
# Update dict
dict['Age'] = 5
dict['Color'] = 'Golden'
>>> dict['Age']
5
>>> dict['Color']
Golden
# Delete dict elements
del dict['Color'] # Delete entry with key 'Color'
dict.clear() # Delete all entries in dict
del dict # Delete entire dict