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