Hash Table Implementation in Python

Intro

Data structure that maps a key to a value in the memeory slot. It uses hash function that converts a key into a hashed code wich is used for the index computing. Received index indicates a memeory slot where we can get a value from.

Features

App includes following features:

  • OOP
  • Hash function

Demo

Main goal of keeping hash table is distributing and retrieving entries (key-value pairs) across an array slots efficiently.

Key-Value inserting with Hash Function:
  1. Each key from a key-value pairs is being converted into a hash code.
    hash = hash_function(key)
       note that hash being calculated based on a key is independent of the array size.
  2. Calculating modulo which gives rest of division:
    modulo operator: %
    index = hash % hash_table_size
       modulo reduces hash to an index = number between 0 and hash_table_size - 1 inclusively.
  3. The outcome of modulo gives a hash_table index where value can be inserted.
  4. In case when the received hash table index is already occupied by another value, then we have a collision. In other words, collsion appears when hash function and further modulo generates the same index for more than one key.
  5. When we have a collision, then we need to proceed with additional computation with e.g. double hashing.
Key-Value insertion example:
source: wikipedia
  • In example we can see key-value pairs: name-phone.
  • Each person's name goes through a hash function which places that person's phone number into a specific slot/bucket of the hash table.
  • Hash function outputs a hash table index where a value for the computed key is being stored.
  • Important to notice is the fact that hash function output, which is a final hash table's index, depends on the key directly. In other words, characters sequence of 'John' gives totally different index than characters sequence of 'Johnny'.
Hash table in Python:
  1. For testing, I set hash table size to 7.
  2. I populate hash table with hash function and modulo from hash table size.
  3. I handle any slot collistion with double hashing.
  4. I keep inserting till all entries distributed among hash table slots.
  5. I print each iteration of entries distributing.
  6. For testing, I try to insert 8th element to has table which results with programmed rejection.
  7. For testing, I try to delete 10th element from table which results with programmed rejection.

Setup

No specific libraries required.

Source Code

You can view the source code: HERE