Hashtables for Embedded and Real-Time Systems

Data abstractions such as hash tables are included in most runtime libraries because of their widespread use and straightforward implementation. While operating systems and programming languages continue to improve their real-time features, much of what is offered by a runtime library is not yet suitable for real-time or embedded-systems. In this paper, we present an algorithm for managing hash tables that is suitable for such systems. The algorithm has been implemented and deployed in place of Java's Hashtable class. We present evidence of the algorithm's performance, experimental results documenting our algorithm's suitability for real-time, and lessons learned from migrating this data structure to real-time and embedded platforms.