Hash Table implementations for STM32 devices

This repository provides two Hash Table implementations for use with STM32 microcontrollers: a Linear Probing Hash Table (LPHT) and a Cache Line Hash Table.

We provide implementations for each Hash Table in two forms: as an STM32CubeIDE project and as standalone C modules that you can use to integrate into your own project.

Examples for both on-board memory storage, and external memory storage (MRAM) are included. We provide basic benchmarks to put/get values from the Hash Tables, which showcase the code necessary for basic setup and operation.

The benchmarks use pre-generated key datasets of varying sizes (between 2 and 256 bytes) for evaluating performance. For each byte size, 5 datasets are available. In order to reduce space, only a single copy of each dataset is included in this repository, and put operations use the values identical to keys (i.e., put(key[0],key[0])). The datasets are named with the pattern keys-xbytes.h and can be found in the MRAM-key-value/Core/Inc/ folder. For each key size, 5 different datasets are available. In order to select a different dataset you have to comment out the array currently enabled, and uncomment a different one. For example:

vim keys-32bytes.h

//In this case, the second dataset is enabled
//char keys[4096][32] = {...}
char keys[4096][32] = {...}  

The number of keys in each dataset is as follows:

• 2 byte-sized keys = 65365 keys in each dataset
• 4 byte-sized keys = 32768 keys in each dataset
• 8 byte-sized keys = 16384 keys in each dataset
• 16 byte-sized keys = 8192 keys in each dataset
• 32 byte-sized keys = 4096 keys in each dataset
• 64 byte-sized keys = 2048 keys in each dataset
• 128 byte-sized keys = 1024 keys in each dataset
• 256 byte-sized keys = 512 keys in each dataset

Compatibility

The STM32CubeIDE project is setup to be used with a NUCLEO-H743ZI board. If you intend to use a different board or microcontroller, use the standalone modules to integrate the Hash Tables into your own project.

LPHT - Linear Probing Hash Table

The linear probing Hash Table divides a zone of memory into consecutive key/value slots. During a put operation, the key is hashed into a slot. If the slot is empty, the key/value pair is inserted into the slot, otherwise an attempt is made for the following slot, and so on until an available spot is found. Slot occupation information is kept in a separate array of bytes, where each bit describes the occupation of a particular slot.

For further details on LPHT usage see LPHT's README.

CLHT - Cache Line Hash Table

The Cache Line Hash Table (CLHT) is organized into buckets, where each bucket contains a set of key/value pairs, a lock, and a pointer to the next bucket. Keys are hashed into buckets, which when full add a new bucket in a linked list configuration. CLHT leverages the CPU's cache lines to improve performance by matching the bucket's size to the CPU's cache line size.

For further detail on CLHT usage see CLHT's README