40 Tiny Hash Table
40 : Tiny Hash Table
- Author: Sasha Krassovsky
- Description: Hash table with 8 slots, 4-bit keys, 4-bit values
- GitHub repository
- Open in 3D viewer
- Clock: 0 Hz
How it works
This is a hash table with 8 slots, 4-bit keys, and 4-bit values. Keys are entered on pins KEY3-KEY0, values are entered on pins VAL3-VAL0. When given a command, and told to execute via the GO line, the hash table hashes the key, and begins linearly probing into the hash table. Once a suitable slot is found, the given command is executed on that slot, or STATUS1-STATUS0 returns a suitable error message. The table takes care to buffer the inputs so that they're not changed during probing.
The commands are:
| Command | CMD1 | CMD0 | ||
|---|---|---|---|---|
| CMD_LOOKUP | 0 | 0 | ||
| CMD_INSERT | 0 | 1 | ||
| CMD_DELETE | 1 | 0 |
The status codes are:
| Status | STATUS1 | STATUS0 | Description |
|---|---|---|---|
| STATUS_OK | 0 | 0 | Operation Succeeded |
| STATUS_FULL | 0 | 1 | Insertion failed - hash table full |
| STATUS_NOTFOUND | 1 | 0 | Lookup failed - key not found |
| STATUS_BUSY | 1 | 1 | Hash table is still probing |
How to test
Choose a key and value to insert, such as 0x4 and 0x2, and set the KEY and VAL lines accordingly (so in this case, 0100 and 0010). Next, set the CMD lines to CMD_INSERT, or 01. Lastly, set the GO line to 1. The STATUS lines should then turn to STATUS_BUSY for a few cycles, empirically 15 cycles is enough for all commands, though the timing varies on the load factor. After it finishes, the STATUS line should return to STATUS_OK, and the OVAL lines should contain the key you inserted (0010)! To run another command on the table, you must set GO to 0 for at least one cycle before triggering another command.
IO
| # | Input | Output | Bidirectional |
|---|---|---|---|
| 0 | VAL0 | OVAL0 | CMD0 |
| 1 | VAL1 | OVAL1 | CMD1 |
| 2 | VAL2 | OVAL2 | GO |
| 3 | VAL3 | OVAL3 | |
| 4 | KEY0 | ||
| 5 | KEY1 | ||
| 6 | KEY2 | STATUS0 | |
| 7 | KEY3 | STATUS1 |