Hash Table Demo

Introduction

This project is an exercise in using the data types (data structures) found in Python to demonstrate hash table performance and efficiency.

It was inspired by Faster than Rust and C++: the PERFECT hash table (YouTube)

Watch the complete video. It is useful and instructive.

Project #1

Create a program to test if a string is a day-of-the-week ('Monday','Tuesday','Wednesday','Thursday', 'Friday','Saturday','Sunday').

Use a linear search and a hash table. Collect and display the performance statistics of both methods.

Ask the user to enter the number of randomly selected days-of-the-week to use for testing. Perhaps 100, 400, ...?

Use the two character hash. See Hashing Days-of-the-Week example .

Code the hashing yourself. Do not download or use any Python modules, etc.

Program Pseudo Code

initialize hashing data structure(s), etc.
ask the user to enter a test count
create a random list of days to test
loop
   test using the linear search and collect statistics
loop
   test using the hash table and collect statistics
display statistics   

Linear Search Pseudo Code

def linear_search(day,list-of-days):
    for d in list-of-days:
        if day == d:
            return True
    return False

Note: The day will always match. We are just measuring
      how long it takes.

Project #2

Using Python's perfect-hash package to create a hash function(s) for Python's reserved words.

There are two major steps...

  1. Use the perfect hash tool to generate the hash function code
  2. Use the generated hash function code in a Python program
    1. get a list of Python's reserved words
    2. generate the hash code for Python's reserved words
    3. create a Python program to test the hashing function

For more information about Python's perfect-hash package click HERE .