Authors:

Partth Suraj Kulkarni

Date Created:

Not specified

Course Title:

Professor:

Not specified

About Paper:

Hash tables are widely used for fast data retrieval, but their performance can suffer when many keys hash to the same bucket. In such cases, traditional chaining methods use linked lists, which have poor cache performance and linear lookup time. This research explores a more efficient approach by replacing linked lists in hash buckets with AVL trees, which maintain balance and offer logarithmic lookup time. We implemented this hybrid structure in C++, where each bucket stores keys in an AVL tree instead of a list. The project also involved optimizing memory layout for cache efficiency and comparing the performance against the standard unordered_map from the C++ Standard Library. We tested the implementation under a variety of key distributions, including cases designed to trigger many collisions. Initial results show that the AVL-based buckets maintain consistent logarithmic access time, even under heavy collision scenarios. Compared to linked-list chaining, our structure shows better worst-case performance and reduced variance in lookup times. This project demonstrates a practical improvement to hash table design for modern systems. In the future, we plan to extend the design to support concurrent operations and to explore when the structure should dynamically switch between lists and trees based on usage. Keywords: Optimization; Vector Computing; Data Structures; Performance Analysis; Computer Architecture

Source:

Purdue University / 2025

Topics:

No topics listed

Co-authors:

Partth Suraj Kulkarni