We present a new method for storing data in a hash table. This data structure is able to handle even the worst non-uniform dataset in a highly dynamic environment and provide a competitive worst case response time and space utilization. Other methods attempt to optimize the best or average case in space usage, page file accesses necessary to retrieve a record, or overhead in maintaining the data structure. However, in doing this these methods often sacrifice the ability to handle non-uniform datasets, response time, or optimal memory utilization in dynamic environments. In fact, some hashing algorithms provide no constant bound on response time or space usage in worst cases.
By providing a guarantee on the number of page file accesses necessary to reach any record within the table without abusing the overhead space usage, our method surpasses other classical hashing tables in response time, average load factor, and non-redundant bucket usage. Also, our lack of restriction on the hash function for the table expands the capabilities of our method. We do this by limiting the expansion of the table to only the segments of the table that require additional space by routing these segments with increasing moduli of primes. Also, our method handles excessive deletions by dynamically merging the least utilized parts of the table as necessary, maintaining a competitive load factor without sacrificing response time. Our method is designed to expect and handle the worst case in any scenario.