完整哈希函数,用于一组没有更新的整数

Question

在我工作的其中一个应用程序中,有必要使用这样的函数:

bool IsInList(int iTest)
{
   //Return if iTest appears in a set of numbers.
}

数字列表在应用程序加载时已知(但在同一应用程序的两个实例之间并不总是相同),并且不会在整个程序中更改(或添加).整数本身可能很大并且范围很大因此没有效率vector<bool>.性能是一个问题,因为功能处于热点.我听说过Perfect hashing但是找不到任何好的建议.任何指针都会有所帮助.谢谢.

ps我理想情况下,如果解决方案不是第三方库,因为我不能在这里使用它们.如果可能的话,简单到足以理解和手动实现的东西将是很好的.

Answer 1

对于这个问题，我将使用二分搜索，假设可以保持数字列表排序。

维基百科有示例实现，应该足够简单，可以转换为 C++。