Reorganization of collisions in a hash bucket of a hash table to improve system performance

摘要

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 the 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 collisions 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.