2008

Self-Adjusting Hash Tables for Embedded Flight Applications

A common practice in computer science to associate a value with a key is to use a class of algorithms called a hash-table. These algorithms enable rapid storage and retrieval of values based upon a key. This approach assumes that many keys will need to be stored immediately. A new set of hash-table algorithms optimally uses system resources to ideally represent keys and values in memory such that the information can be stored and retrieved with a minimal amount of time and space. These hash-tables support the efficient addition of new entries. Also, for large data sets, the look-up time for large data-set searches is independent of the number of items stored, i.e., O(1), provided that the chance of collision is low.

Like arrays, hash-tables provide constant time O(1) look-up on average, regardless of the number of items in the table. However, the rare worst-case look-up time can be as bad as O(n). Compared to other associative array data structures, hash-tables are most useful when large numbers of records are to be stored, especially if the size of the data set can be predicted.

These algorithms may be used as in-memory data structures and may also be adopted for use with persistent data structures. Hash-tables are used in thousands of instances of flight code, and this approach could improve the efficiency of those applications, allowing them to run in smaller memory footprints and to autonomously evolve with time if and when their data demands a more efficient representation.

This work was done by Mark James of Caltech for NASA’s Jet Propulsion Laboratory.

In accordance with Public Law 96-517, the contractor has elected to retain title to this invention. Inquiries concerning rights for its commercial use should be addressed to:

Innovative Technology Assets Management
JPL
Mail Stop 202-233
4800 Oak Grove Drive
Pasadena, CA 91109-8099
E-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.

Refer to NPO-40363, volume and number of this NASA Tech Briefs issue, and the page number.

This Brief includes a Technical Support Package (TSP).

Self-Adjusting Hash Tables for Embedded Flight Applications (reference NPO-40363) is currently available for download from the TSP library.

Please Login at the top of the page to download.