Smart Chaining: Templing and Temple Search
Hash tables continue to be at the forefront of applications that require fast data lookup, but their usefulness in practice depends on effective collision resolution. Classical approaches like chaining (linked lists) and open addressing (linear/quadratic/random probing) have inherent challenges, lik...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/11027127/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Hash tables continue to be at the forefront of applications that require fast data lookup, but their usefulness in practice depends on effective collision resolution. Classical approaches like chaining (linked lists) and open addressing (linear/quadratic/random probing) have inherent challenges, like chaining degrades with increasing lists, whereas universal hash functions impose unrealistic computational costs on bulk operations. This work introduced two complementary innovations that can circumvent these flaws. First, Even-Odd Hash Function optimizes prime-number selection for modulo computations so that 95% uniformly distributed load is achieved at zero overhead. Second, chaining is structurally re-architected with linked lists substituted by B-trees of order 5, which gives the Templing and Temple Search framework. By combining combinatorial hashing with hierarchical collision resolution, the scheme avoids linear search delays and resists clustering without increasing the memory footprint. Experimental evidence illustrates the dominance of Templing and Temple Search as it delivers <inline-formula> <tex-math notation="LaTeX">$4.5x$ </tex-math></inline-formula> faster searches and <inline-formula> <tex-math notation="LaTeX">$3.5x$ </tex-math></inline-formula> faster insertions over plain chaining at equal space complexity. Light-weight prime selection and non-contiguous memory structure within the methodology guarantee scalability even under heavy loads. It restates hash table performance, resolving algorithmic advancement against practical exigencies to set the agenda for contemporary data structure design. |
|---|---|
| ISSN: | 2169-3536 |