Hash table expansion and contraction for use with internal searching
US6067547A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | Aug 12, 1997 |
| Grant date | May 23, 2000 |
| Priority date | — |
| Expiry date | Aug 12, 2017 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99943
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Hash tables are used to index an internal database--one that resides in primary memory. The hash tables are segmented into a sequence of segments that increase geometrically in size. To expand a table, an additional segment is allocated which is twice as large as the previously allocated segment. This most recently allocated segment is referred to as an expansion segment, while the previously existing segments are referred to as base segments. As records are added, entries from the base segments are gradually split, and some of the records referenced by these entries are assigned to new entries in the expansion segment. This distributes address recalculations over time, while also using memory quite efficiently.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.