为嵌入式应用程序选择C中的唯一标识符

Question

我目前正在尝试实现一种算法来选择唯一的(16位)标识符.挑战是以不使用太多内存的快速方式执行此操作.当前使用的标识符列表是通过一系列SPI事务扫描外部闪存设备来确定的,因此是一个相对较慢的过程.此外,该算法将在小型微控制器上运行,因此我不能真正将所有条目读入RAM并在那里处理它们.

到目前为止我的想法是:

1. 选择一个数字,然后扫描列表,看看它是否被使用.冲洗并重复.遭受相当缓慢(特别是如果有很多文件).
2. 如上所述,但是使用具有适当种子的伪随机数生成器来选择数字.这具有以下优点:不太可能存在如此大量的迭代.
3. 扫描列表并使用找到的所有条目填充数组.对它进行排序然后变得微不足道.这可能会占用大量内存.
4. 使用一个巨大的(好的,可笑的,巨大的)位掩码.不太实际.
5. 接受该工具的生命周期,使其在将65534个文件写入Flash之前很久就被丢弃或"格式化",因此只需将目前使用的最高值存储在Flash或备份内存中并继续增加.老实说,这可能对这个特定的应用程序非常有效.

目前,我正准备使用第二个或第五个,但我有兴趣知道是否有人有任何其他想法.我想认为有一种类似于CRC的算法,可以用来依次处理每个数字,并给出一个尚未使用的数字的公平概念,但我不知道这可能是怎样的工作.

Answer 1

我认为你有一些选择,但还有一个需要考虑的是Bloom Filter.这有可能出现误报(即你可以排除已经使用的ID,即使它还没有),但它可以让你选择你可以专用于这些数据的确切空间量.