Hotrace is a high-performance Key-Value Store implementation in C, developed as a "Rush" project (a timed 48-hour challenge).

The goal is to build a data structure capable of storing pairs of key: value and then retrieving the values associated with specific keys as fast as possible, handling millions of entries efficiently.

• Custom Hash Table: Optimized for speed and low collision rates.
• Double Hashing: Collision resolution strategy using two hash functions (h1 and h2) to probe the table.
  • h(k, i) = (h1(k) + i * h2(k)) % size
• Dynamic Expansion: The table automatically resizes when the load factor exceeds a threshold.
• Input Parsing: Efficient reading from standard input (stdin) using get_next_line.

Use the provided Makefile to compile the project:

make

The program reads from Standard Input. The input format is:

1. Key-Value Pairs: Lines containing key and value separated by a newline.
2. Empty Line: Separator.
3. Search Keys: Keys to search for.

./hotrace < input_file

key1
value1
key2
value2

key1
key2

value1
value2

The project focuses on minimizing CPU cycles and memory access latency. The choice of Double Hashing ensures a uniform distribution of keys and reduces clustering compared to linear probing.