我想知道是否有类似 HashSet 的东西,但以一系列值作为键。
例如,我们可以添加一个以 100 到 4000 之间的所有整数作为键的项目。如果我们使用 100 到 4000 之间的任何键,例如287.
我希望查找速度非常接近 HashSet,即 O(1)。可以使用二进制搜索来实现这一点,但这对于要求来说太慢了。我想尽可能多地使用标准 .NET API 调用。
更新
这很有趣:https://github.com/mbuchetics/RangeTree
它的时间复杂度为 O(log(N)),其中 N 是间隔数,因此它不完全是 O(1),但它可用于构建工作实现。
最佳答案
我认为目前还没有适合它的结构。您可以实现类似 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 to Dictionary
关于c# - 寻找类似 HashSet 的东西,但具有一系列键值?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39077141/