在小型MCU上优化稀疏阵列中的元素查找

问：

我正在开发一个应用程序，该应用程序涉及管理分布在大小为 M 的数组中的 N 个 Element 实例，其中 N << M（N 比 M 小得多）。这些元素可以通过它们的索引进行访问，它们在数组中的分布在构建时是已知的，但没有遵循特定的模式。

主要目标：我寻求一种算法，该算法允许通过索引对元素进行有效（时间）检索，同时还要注意空间限制。理想情况下，我希望避免分配 O（M） 空间，这虽然会导致 O（1） 时间复杂度，但对于我的应用程序来说是不可行的。

上下文：此任务是为工作频率为 50 MHz 且没有浮点单元 （FPU） 的 16 位微控制器单元 （MCU） 开发 CanOpen 从站堆栈的一部分。传统的哈希表似乎是一个显而易见的解决方案，但由于 MCU 的局限性，它并不适合。

当前方法：我正在考虑使用简化的 Murmur 哈希函数的开放式寻址哈希表。下面是初步函数：

const int A = 16;
const int B = 0x45d9f3b;
const int C = B;

unsigned int hash(unsigned int x) {
    x = ((x >> A) ^ x) * B;
    x = ((x >> A) ^ x) * C;
    x = (x >> A) ^ x;
    return x;
}

我计划尝试使用不同的 A、B 和 C 值，以最大程度地减少访问时间并减少冲突。最终，使用自动化脚本运行构建时间以找到最佳的 A、B、C 常量。

问题：考虑到限制，这种方法是否可行，或者是否有更有效的算法或方法更适合这种情况？我对其他建议持开放态度，包括使用二叉搜索的可能性。

其他信息

此设置是运行实时应用程序的小型MCU上的CANopen从站堆栈的一部分。虽然 CanOpen 使用 16 位对象字典，但我的应用程序只需要 100-200 个对象。关键是尽量减少每个对象的访问时间。

我的处理能力有限，MCU 上没有 FPU。空间效率与时间效率同样重要。