Reorganization of collisions in a hash bucket of a hash table to improve system performance
US6052698A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Mar 15, 1999 |
| Grant date | Apr 18, 2000 |
| Priority date | — |
| Expiry date | Mar 15, 2019 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99956
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
An improved hashing system is provided that takes advantage of the caching architecture of many of today's processors to improve performance. Some of today's most advanced processors, like PENTIUM processor, have a two level caching scheme utilizing a primary cache and a secondary cache, where data contained in the primary cache is accessible 50-150 times faster than data in main memory. The improved hashing system ensures that collision occur so that the buckets contain many entries, and at runtime, the entries in the buckets are reordered to increase the number of times that the primary cache of the processor is used and to reduce the number of times that main memory is used, thereby improving the performance of the hashing system.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.