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

你可能需要Geohash??跟你的想法很類似，也是二分確定區間給定hash。
http://en.wikipedia.org/wiki/Geohash
http://www.cnblogs.com/LBSer/p/3310455.html

Answer 2

這種hash函數叫做perfect hash.
linux有一個工具專門做這件事：
http://www.gnu.org/software/gperf/

補充：
上面這個思路有問題。

這個問題應該和路由器中的路由表查找問題是一個問題，
大型路由器為了速度，似乎對這種查找的速度做過大量優化，用的比較多的，貌似是trie。
或許可以直接利用已有成果？