中图分类号：TP872文献标识码：ADOI:10.19339/j.issn.1674-2583.2026.08.005
中文引用格式：任文龙，姚力，陈路.嵌入式定量定速哈希表的实现方法［J］.集成电路应用，2026，43（8）：22-27.
英文引用格式：Ren Wenlong,Yao Li,Chen Lu. Implementation method of embedded quantitative constant-speed hash table［J］.Application of IC，2026，43（8）：22-27.

Implementation method of embedded quantitative constant-speed hash table

Abstract： Most small RAM embedded operating systems which follow the principle of simplicity and efficiency usually don’t support built-in hash data structures, and this limits the design and application of the hash table structure in the embedded software. It’s also a challenge for embedded hash table application because of the memory management efficiency of different embedded operating systems and that of the hash table operation. This paper designs a quantitative constant-speed hash implementation method for the embedded system. It constructs a constant O(1) dynamic memory mechanism using the global static memory segment. Based on this, the algorithm adds a dual linked list for storing the key and improves the structure of chain hash which has the same complexity with the traditional chaining hash algorithm when executing the CRUD operation. The algorithm is tested and the results show that it has excellent real-time performance and high practical value.

Key words : embedded system; hash table; chaining; static memory segment; dual linked list