c++ - 针对区间范围设计一个高效hash函数，使得一个区间里的数对应一个hash值

Question

假如有一群范围对格式为：<范围表示，该范围对应的结果值>，设计一个最快查找算法，使得给定一个值，输出该值所对应的范围对的结果值。
注意：范围对之间不会存在交集，也不是严格相邻，即两个区间可能不是相邻的。

例如：
<<1, 2>, 65>
<<3, 37>, 75>
<<45, 157>, 12>
<<160, 200>, 23>
<<210, 255>, 121>
……
如果给定一个数78，则输出12，因为78属于范围对<45, 159>

要求：不要用数组存储下标求值，因为范围对可能非常大。

针对这个问题，我目前的解法是利用二分查找，针对范围对的高效查找算法设计（不准用数组）

但还是不够快，我现在有个新的思路，就是：
能不能设计利用这些范围对设计一个hash函数，使得一个区间对应一个hash值，举个例子：
上面的第一对范围<1, 2>里的所有数即1和2都对应hash值1，<3, 37>里的所有值3~37都对应hash值2，以此类推……

这样类似的hash函数能设计出来吗？

Answer 1

You may need Geohash?? It’s very similar to your idea, which is to give a hash in a binary determined interval.
http://en.wikipedia.org/wiki/Geohash
http://www.cnblogs.com/LBSer/p/3310455.html

Answer 2

This hash function is called perfect hash.
Linux has a tool specifically for this purpose:
http://www.gnu.org/software/gperf/

Supplement:
There is a problem with the above idea.

This problem should be the same as the routing table lookup problem in the router,
For the sake of speed, large routers seem to have done a lot of optimization for the speed of this kind of search, and the one they use more often seems to be trie.
Maybe we can directly use existing results?