File Indexing and Disk-Based Hash Tables

This repository was developed as part of an academic File Organization and Data Structers subject. The primary goal of the project is to apply concepts of binary file management and implement Disk-Based Hash Tables to optimize record retrieval within a large dataset (a postal code/CEP database), bypassing the need for slow, brute-force sequential reads.

The project demonstrates how to build efficient binary index files and explores two classic strategies for handling hash function collisions.

---

Project Structure and Approaches

The system features two distinct implementations to solve the same problem: retrieving a specific record from disk in near-constant time $O(1)$.

1. Chaining Approach (Linked List on Disk)

In this strategy, the index file features a large hash space, and collisions are resolved by creating pointers that point to the end of the file, chaining elements that generate the same hash.

• CriaIndice.py: Reads the original cep.dat database and generates the cep-hash.dat index using the SHA-1 algorithm (hash size: 900,001). In case of a collision, it chains records using file pointers.
• ProcuraIndice.py: Performs the optimized search by hashing the input CEP, navigating the file pointers within the index, and directly fetching the record from the data file.
• NumeroColisoes.py: A statistical tool that simulates data distribution, displaying total collisions, the maximum linked list size, and the average number of disk accesses required per search.

2. Bucket Approach (Fixed-Size Blocks)

In this strategy, the hash table is much smaller, but each position (bucket) is a fixed byte-structured block capable of storing multiple keys and record positions simultaneously.

• Hash2.py: Initializes the hashcep.dat index file with 977 positions (the chosen magic number). It reads the data and inserts keys and positions into buckets designed to hold up to 1,000 entries each using Python's struct format (i1000l1000l).
• ProcuraHash.py: Calculates the hash, extracts the entire bucket from disk into memory in a single read operation, scans the bucket array, and retrieves the complete information.

Sequential Search (Baseline)

• lerArquivoCEP.py: Performs a brute-force search by linearly reading the data file from start to finish. It serves as a performance baseline to highlight the massive speed difference between a linear $O(N)$ search and a hashed $O(1)$ index search.

---

How to Run

1. Environment Setup

Ensure that the directory structure expected by the scripts exists hash-2024/hash/data/cep.dat - original binary database file (cep.dat)

2. Generating the Indexes

To run the Chaining approach:

python "CriaIndice.py"

To run the Bucket approach:

python "Hash2.py"

3. Searching a record

By Chaining index search

python ProcuraIndice.py XXXXXXXX

By Bucketg structure search

python ProcuraHash.py