寻找类似于HashSet的东西，但具有键值的范围

本文关键字：键值 范围 类似于 HashSet 寻找 | 更新日期: 2023-09-27 18:03:27

我想知道是否有类似HashSet的东西，但由一系列值键。

例如，我们可以添加一个键值为100到4000之间所有整数的项。如果我们使用100到4000之间的任何键，例如287，则该项将被返回。

我希望查找速度非常接近HashSet，即O(1)。可以使用二进制搜索来实现这一点，但是对于需求来说，这太慢了。我希望尽可能使用标准的。net API调用。

这很有趣:https://github.com/mbuchetics/RangeTree

它的时间复杂度为O(log(N))，其中N是间隔的数量，所以它不完全是O(1)，但它可以用来构建一个工作实现。

寻找类似于HashSet的东西，但具有键值的范围

我不相信已经有一个结构了。你可以实现像RangedDictionary:

这样的东西
class RangedDictionary {
   private Dictionary<Range, int> _set = new Dictionary<Range, int>();
   public void Add(Range r, int key) {
      _set.Add(r, key);
   }
   public int Get(int key) {
      //find a range that includes that key and return _set[range]
   }
} 
struct Range {  
   public int Begin;
   public int End;
   //override GetHashCode() and Equals() methods so that you can index a Dictionary by Range
}

编辑:将HashSet改为Dictionary

您可以尝试一下这个解决方案。然而，它假设了一些点:

  • 无范围重叠
  • 当你请求一个号码时，它有效地在一个范围内(没有错误检查)

从你说的来看，这个是O(N)，但我认为你可以毫不费力地把它变成O(log(N))。

这个想法是一个类将处理范围的事情，它将基本上转换任何值给它的范围的下限。这样你的哈希表(这里是一个字典)包含低边界作为键。 
public class Range
{
    //We store all the ranges we have
    private static List<int> ranges = new List<int>();
    public int value { get; set; }
    public static void CreateRange(int RangeStart, int RangeStop)
    {
        ranges.Add(RangeStart);
        ranges.Sort();
    }
    public Range(int value)
    {
        int previous = ranges[0];
        //Here we will find the range and give it the low boundary
        //This is a very simple foreach loop but you can make it better
        foreach (int item in ranges)
        {
            if (item > value)
            {
                break;
            }
            previous = item;
        }
        this.value = previous;
    }
    public override int GetHashCode()
    {
        return value;
    }
}

下面测试一下。

class Program
{
    static void Main(string[] args)
    {
        Dictionary<int, int> myRangedDic = new Dictionary<int,int>();
        Range.CreateRange(10, 20);
        Range.CreateRange(50, 100);
        myRangedDic.Add(new Range(15).value, 1000);
        myRangedDic.Add(new Range(75).value, 5000);
        Console.WriteLine("searching for 16 : {0}", myRangedDic[new Range(16).value].ToString());
        Console.WriteLine("searching for 64 : {0}", myRangedDic[new Range(64).value].ToString());
        Console.ReadLine();
    }
}

我不相信你真的可以低于O(Log(N))，因为你没有办法立即知道一个数字在哪个范围内，你必须总是将它与下界(或上界)进行比较。

如果您有预先确定的范围，那将更容易做到。例如，如果你的范围是每百位，通过计算它对100取模就可以很容易地找到任何数字的正确范围，但这里我们不能做任何假设，所以我们必须检查。

要使用此解决方案向下到Log(N)，只需将foreach替换为一个循环，该循环将查看数组的中间，然后每次迭代将其分成两部分…

相关文章：