假设我想构建一个数组来执行查找以解析网络协议（如以太类型）。由于这样的标识符是2字节长的，如果我使用直接索引，我最终会得到一个2^16个单元格的数组：这是一种真正的浪费，因为数组很可能是稀疏的，即数组中有很多间隙。
为了最大限度地减少内存使用，我会使用一个完美的哈希函数生成器，比如CMPH，这样我就可以将我的"n"个标识符映射到一个n大小的数组，而不会发生任何冲突。这种方法的缺点是，我不得不依赖一个外部的"开放"库。
我想知道，在我的情况下，是否有更聪明的方法可以在保持内存使用率的同时进行持续的时间查找；请记住，我对索引16位无符号数字感兴趣，并且集合大小非常有限。
感谢
由于您知道处理的是16位值，任何查找算法都将是一个恒定时间算法，因为只有O（1）个不同的可能值。因此，表面上可能较慢的算法（例如，对n个元素在O（n）中运行的线性搜索）在这里实际上可能有用。
除非有一个完美的哈希函数，如果你想保证快速查找，我建议研究布谷鸟哈希，它保证了最坏情况下的O（1）查找时间，并具有预期的O（2）时间插入（尽管你必须对哈希函数稍微聪明一点）。为16位值生成散列函数真的很容易；如果你计算两个16位乘法器，将16位值的高位和低位乘以这些值，然后将它们相加，我相信你会得到一个很好的散列函数来模任何素数。
或者，如果你不一定要进行O（1）查找，并且可以进行良好的预期查找时间，你也可以使用具有开放寻址的标准哈希表，例如线性探测哈希表或双哈希哈希表。将较小的数组与这种哈希方案一起使用可能非常快，并且实现起来应该非常简单。
对于一种完全不同的方法，如果您存储稀疏数据并希望快速查找，那么一个可能对您很有效的选项是使用简单的平衡二进制搜索树。例如，treap数据结构易于实现，并为值提供预期的O（logn）查找。由于您处理的是16位值，这里的logn大约是16（我认为对数的底实际上有点不同），所以查找应该很快。这确实会给每个元素带来一些开销，但如果您只有几个元素，那么实现起来应该很简单。为了获得更少的开销，您可能需要研究splay树，它每个元素只需要两个指针。
希望这能有所帮助！