我正在开发一个用 C 编写的项目，该项目将部署在资源非常有限的老式系统上。目标系统具有 16 MHz 处理器，而我的应用程序内存限制为 1 MB，因此我所做的一切都需要尽可能提高 CPU 和内存效率。
此外，我需要将堆内存分配保持在最低限度，因为它们相对较慢并且可能导致内存碎片。
在这个应用程序中，我需要几个静态关联数组。每个数组都有相同的键和值类型：键是一对两个字节整数（可以表示为单个四字节整数），值是一个两字节整数。所有这些数组中的数据都是在编译时确定的，并且在运行时永远不会改变。因此无需添加或删除键，或更改任何值。
考虑到这些规范，我该如何实现这样的数组？
一个想法是提前对数据进行排序并使用二分搜索来查找值，但我更喜欢找到在恒定时间内运行的东西。
接下来我使用最小完美哈希函数研究了哈希表。这是有道理的，因为数据是静态的，它可以有效地存储在连续的内存中，并且可以进行编译时计算来确定哈希函数。但是，我从未使用或实现过这样的哈希表，并且由于以下原因我不确定它是否适合：
但是，由于我对这些还不熟悉，所以我可能会偏离基础或误解它们的工作原理。
具有最小完美哈希函数的哈希表是否适合我的用例？或者我应该考虑其他方法吗？
众所周知，c 有助于有效地使用内存，但到了一定程度，就必须在 CPU 成本和内存空间之间进行权衡。如果您无法获得令您满意的完美哈希函数，您可以使用我经常使用的哈希表方法，其工作原理如下。
假设你有n个项目，每个项目占用s个字节。创建一个 2ns 字节的数组（您可以更小，例如 1.5，但随后会出现更多冲突，导致查找速度变慢）并用一些空值填充它。对于哈希函数，如果我知道要放入其中多少个元素，我通常只使用某个素数 p > n 的模（例如 p=nextprime(n)）来获取数组的索引以开始搜索/插入从。要在数组中查找某些内容或插入新对象的位置，只需从散列函数给出的位置开始使用线性搜索，并进行环绕，直到找到对象或空值。如果您使用 2ns 大小的数组，大多数时候它会立即找到对象，或者当对象很小时，将在同一缓存行中搜索它。
有很多选择，但只有您知道您想要优先考虑 CPU 工作与空间的程度。