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