我有一个范围元素的数组。每个元素都有一个开始和结束。在数组中，范围不重叠，并对它们进行排序。散列范围
即（代码只是为了说明这一点，不要指望它来编译）：
var arr = { [0,3], [5,10], [15,59] };
给定值（比如9），是有范围的哈希函数，让我快速获取具有包含该值的范围的元素？
当然有一种天真的解决方案，只是循环每个元素，直到找到合适的;更精细的一个，如范围开始的二进制搜索;以及创建一个具有范围的二叉树的专利技术。
但有谁知道使用散列的方法吗？
您可以创建一个索引，以便在arr中索引起始值。
var arr = { [0,3], [5,10], [15,59] };
var dictStart = new Dictionary<int, int>();
dictStart.Add(0, 0);
dictStart.Add(5, 1);
dictStart.Add(15, 2);
现在，让你可以做的dictStart字典对于较高的值来搜索的第一个元素的值的二进制搜索范围。然后采取以前的条目。
很难解释。作为一个例子查找9.做搜索得到元素e = [5,1]。
var range = arr[e[1]]; // = [5, 10]
bool isWithin = val <= range[1] && val >= range[0];
因此，它将减少内存侵入。关键是要快速搜索范围的起始值。
我想它会解决这个问题，但它不是一个散列。
不是我正在寻找的东西，但它给了我一个主意。 标准化范围的结束，然后使用每个标准化开始范围的最后4位来计算桶。散列可以变成int [] []的形式，其中第一个数组是桶，而锯齿形是属于该桶的范围列表。 谢谢 – JorgeLeo 2010-08-19 18:13:29
您可以预先计算最近的neigbour并将其存储在某个地方。在你的例子中，表格有0..59个条目，并且你在每个索引处存储最近范围的索引。
这样，它会非常快。
我喜欢这个解决方案。您的查找值然后成为您的表中的索引，并且该表返回arr []的索引。 2查找，你就完成了。它会迅速获得内存密集，但它很好地解决了这个问题。 – 2010-08-18 20:38:08
请注意，在示例中范围之间有空洞，没有0到59个条目。确实可以用空值来代替这些洞，但是它在范围内击败了它的能力，记忆力消耗天空火箭。我看到的范围在0到2百万之间，中间有很多漏洞，我需要在内存中保留60k或更多的这些集合（因此为什么是范围） 这就是为什么我要找一个哈希解决方案。以我可以回答问题的方式散列范围：这个位置是在一个范围内（哪一个），还是落在一个洞中？ – JorgeLeo 2010-08-18 21:18:37
这不使用散列（即使我怀疑散列是一个很好的解决方案）。 – Frank 2010-08-18 21:18:50
如何使用Dictionary<int, Element>来保存所有范围内的所有数字，即添加四个条目
0, [0,3]
1, [0,3]
2, [0,3]
3, [0,3]
等等的其他范围。它通过使用Dictionary来使用散列，但我怀疑它是最有效的解决方案。
顺便说一句。我必须是一个函数，散列表不计算。 – JorgeLeo 2010-08-18 21:25:53