构建"稀疏"查找阵列,最大限度地减少内存占用

Question

假设我想构建一个数组来执行查找以解析网络协议(如ethertype).由于这样的标识符是2字节长,如果我使用直接索引,我最终会得到一个2 ^ 16个单元格数组:这是一个真正的浪费,因为它很可能是数组稀疏 - 即大量的空白阵列.

为了减少内存使用量,我会使用像CMPH这样的完美散列函数生成器,这样我就可以将我的"n"标识符映射到n大小的数组而不会发生任何冲突.这种方法的缺点是我必须依赖外部的"开放"库.

我想知道 - 在我的情况下 - 是否有更聪明的方法可以在保持海湾内存使用的同时进行恒定的时间查找; 请记住,我感兴趣的是索引16位无符号数,并且设置大小非常有限.

谢谢

Answer 1

由于您知道您正在处理16位值,因此任何查找算法都将是一个恒定时间算法,因为只有O(1)个不同的可能值.因此,表面上可能较慢的算法(例如,线性搜索,对于n个元素在O(n)中运行)在这里实际上可能是有用的.

除非你想要保证快速查找,否则我会建议查看杜鹃散列,它可以保证最坏情况下的O(1)查找时间,并且预计会有O(1)次插入(尽管你必须是你的哈希函数有点聪明).为16位值生成散列函数非常容易; 如果你计算两个16位乘法器并将16位值的高位和低位乘以这些值,然后将它们加在一起,我相信你得到一个好的散列函数mod任何素数.

或者,如果您不必绝对必须进行O(1)查找并且可以获得良好的预期查找时间,则还可以使用具有开放寻址的标准哈希表,例如线性探测哈希表或双哈希哈希表.使用具有这种散列方案的较小阵列可能非常快并且应该非常容易实现.

对于完全不同的方法,如果您要存储稀疏数据并希望快速查找时间,那么可能适合您的选项是使用简单的平衡二叉搜索树.例如,treap数据结构易于实现,并为值提供预期的O(log n)查找.因为你正在处理16位值,所以log n大约是16(我认为对数的基数实际上有点不同),所以查找应该非常快.这确实为每个元素引入了一些开销,但是如果你只有几个元素,它应该很容易实现.对于更少的开销,您可能希望查看splay树,每个元素只需要两个指针.

希望这可以帮助!