散列范围 [英] Hashing a range

问题描述

我有一个范围元素数组。每个元素都有一个起点和终点。在数组中，范围不重叠，而是对其进行了排序。

I have an array of range elements. Every element is has a start and an end. Within the array, the ranges are not overlapping, and they are sorted.

即（代码只是为了说明，不要期望它可以编译）：

i.e. (code just to illustrate, do not expect it to compile):

var arr = { [0,3], [5,10], [15,59] };

给定一个值（例如9），是否存在范围的哈希函数，使我能够

Given a value (say 9), is there a hash function of the ranges that will allow me to quickly get the element that has the range that contains the value?

当然有天真的解决方案，只是循环遍历每个元素，直到找到正确的元素为止。比较复杂的一种，例如以范围开头的二进制搜索；

Of course there is the naive solution, just cycle though each element until you find the right one; the more elaborate one, like binary search by the start of the range; and the patented one of creating a binary tree with the ranges.

但是有人知道使用哈希的方法吗？

But does anybody knows of a way to use a hash?

推荐答案

您可以为起始值创建索引以在arr中建立索引。

You could create an index for the start values to index in 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);

现在要获取范围，您可以对dict的值进行二进制搜索。高于要搜索的值的元素。然后输入上一个条目。

Now to get the range you can do a binary search on the values of the dictStart dict for the first element that is higher that the value to search for. Then take the previous entry.

很难解释。例如，查找9.搜索元素e = [5，1]的内容。

Difficult to explain. As an example look up 9. Do the search what got element e=[5, 1].

var range = arr[e[1]];   // = [5, 10]
bool isWithin = val <= range[1] && val >= range[0];

这样一来，它将减少对内存的入侵。关键是要快速搜索范围的起始值。

So that way it will be less memory invasive. The key is to have a fast search fro the start values of the ranges.

我想它可以解决问题，但不是哈希。

I guess it will solve the problem but it is not a hash.

这篇关于散列范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！