c - 以固定大小的位数组作为键查找表

Question

我有一系列固定大小的二进制值数组(来自遗传算法的个体)，我想将它们与浮点值(适应度值)关联起来。这样的查找表将具有相当大的尺寸，受可用内存的限制。由于 key 的性质，是否存在可以保证不发生冲突的哈希函数？我尝试了一些方法，但它们导致了冲突。我可以使用什么其他数据结构来构建这个查找系统？

Answer 1

回答您的问题:没有哈希函数可以保证不发生冲突，除非您创建一个对位数组进行完全编码的哈希函数，这意味着给定哈希值您可以重建位数组。这种类型的函数是压缩函数。如果您的数组有很多冗余信息(例如大多数值都是零)，则压缩它们可能有助于减少查找表的总大小。

关于用 C 语言压缩位数组的问题在这里得到了解答:Compressing a sparse bit array

由于大多数位设置为零，最简单的解决方案是编写一个函数，将位数组转换为整数数组，该数组跟踪设置为“1”的位的位置。然后编写一个函数，如果您再次需要位数组，则执行相反的操作。您只能将编码后的数组保存在 HashMap 中。

减少查找表总大小的另一个选项是删除旧值。由于您使用的是遗传算法，种群应该随着时间的推移而变化，旧值应该变得无用，您可以定期从查找表中删除旧值。