This repository contains a simple script for generating illustrations of different operations on hash tables that use open addressing as a collision resolution strategy. At the moment it is only possible to generate illustrations that show:

• Insertion of keys into a hash table, where collisions are resolved through linear probing, quadratic probing or double hashing

Illustrations for searching and deleting keys might be added at a later time.

Note: The purpose of the script is to be able to automatically create illustrations of simple constructed examples. In other words, the size of the table is fixed, as it should have a reasonable size to be able to fit into e.g. a LaTeX beamer or A4 document.

• Python 3
• jinja2: A templating language for Python. The library can be installed through pip by running: pip install jinja2
• LaTeX & TikZ: To subsequently be able to compile the illustrations into a .pdf document. For Linux LaTeX distributions, see e.g. Ubuntu LaTeX packages or Arch Linux LaTeX packages.

Note: The script has only been tested on a Linux system (Manjaro).

• First of all clone the repository to some local directory:

git clone https://github.com/NicklasXYZ/TikzHashTableGenerator

• Create and save a Python script inside the TikzHasTableGenerator directory, which contains something along the lines of:

# Contents of the "example.py" file
from HashTableRenderer import HashTableRenderer

######################################
#     Example 1: Linear probing      #
######################################
# Specify the size of the hash table
size = 11

# Define the list of keys to be inserted into the table
values = [67, 20, 17, 33, 16, 2, 15, 18, 26]

# Specify the complete hash function and thus the probing strategy
hash_function = lambda k, i: (((7 * k  + 4) % size) + i) % size 

# Create the hash table and supply the hash function as an argument
hashtable = HashTableRenderer(size = size, hash_function = hash_function)

# Insert all the keys
hashtable.bulk_insert(values)

#--- Render the illustrations and compile them into a main.tex document ---#
# 1. Compile all the illustrations into a beamer presentation
hashtable.render(beamer = True, scale = 0.9)    # document class: beamer

# or 2. compile all the illustrations into an article document
# hashtable.render(beamer = False, scale = 0.9)   # document class: article

• Lastly, run the script, which was just created above. This should create a directory output that contains all the generated TikZ and LaTeX code, which is needed for compiling a .pdf document that contains a sequence of illustrations

As a last note, the files in the output directory can be compiled into a .pdf document by running pdflatex main.tex.