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:
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.
Don't have an account?
Overview
The document titled "Self-Adjusting Hash Tables for Embedded Flight Applications" (NPO-40363) from NASA's Jet Propulsion Laboratory discusses innovative algorithms designed to optimize the use of hash tables in embedded systems, particularly for aerospace applications. Hash tables are data structures that associate keys with values, allowing for efficient data retrieval. They are widely used in various software applications, including databases and network systems.
The primary advantage of hash tables is their ability to provide average constant-time O(1) lookup, which is independent of the number of items stored. However, traditional hash tables assume that many keys will need to be stored upfront, which can be inefficient for applications that incrementally build their data sets. In such cases, linear searching may be more memory-efficient until the data set grows beyond a certain threshold.
The document introduces a set of self-adjusting algorithms that dynamically change the internal representation of hash tables based on resource requirements. These algorithms aim to maximize resource efficiency by optimizing the representation of keys and values in memory, thereby minimizing both time and space usage. This adaptability allows applications to initially operate within smaller memory footprints and evolve autonomously as data demands change.
The algorithms have been successfully implemented in various applications, including Ryan Mackey's MER battery prognostic technology and Leslie Paal's Common Automation Engine used in NASA's Deep Space Network. The potential applications for these self-adjusting hash tables extend beyond aerospace, with implications for industries such as nuclear power, life support systems, and automotive technology.
The document emphasizes the importance of these algorithms in supporting NASA's ambitious manned flight program and other critical applications where efficient data management is essential. By leveraging self-adjusting hash tables, software can better handle the complexities of data storage and retrieval, ultimately enhancing performance and reliability in mission-critical environments.
In summary, the document presents a significant advancement in hash table technology, showcasing how self-adjusting algorithms can lead to more efficient data management in embedded systems, particularly in the context of aerospace applications. This innovation not only improves resource utilization but also supports the evolving needs of modern software systems.
