数据结构，C#：~O(1) 使用范围键查找？

我有一个数据集。该数据集将提供一个查找表。给定一个数字，我应该能够查找该数字的相应值。

不过，数据集（假设是 CSV）有一些注意事项。代替：

1,ABC
2,XYZ
3,LMN

这些数字是范围（- 是“通过”，而不是负数）：

1-3,ABC     // 1, 2, and 3 = ABC
4-8,XYZ     // 4, 5, 6, 7, 8 = XYZ
11-11,LMN   // 11 = LMN

所有数字都是有符号整数。范围不与其他范围重叠。存在一些差距；数据集中未定义某些范围（例如上面最后一个片段中的 9 和 10）。 `

如何在 C# 中对该数据集进行建模，以便在保持较低内存占用的同时获得性能最佳的查找？

我想到的唯一选择是内存过度消耗。假设我的数据集是：

1-2,ABC
4-6,XYZ

然后我创建一个Dictionary<int,string>()其键/值是：

1/ABC
2/ABC
4/XYZ
5/XYZ
6/XYZ

现在我有了哈希性能查找，但哈希表中浪费了大量空间。

有任何想法吗？也许只是使用 PLINQ 并希望获得良好的性能？ ;)

如果您的字典要真正存储广泛的键值，则将所有可能范围扩展为显式键的方法将迅速消耗比您可能可用的更多的内存。

最好的选择是使用支持某种二分搜索（或其他 O(log N) 查找技术）变体的数据结构。这是一个链接到 .NET 的通用 RangeDictionary http://www.blackwasp.co.uk/RangeCollection.aspx内部使用 OrderedList，并且具有 O(log N) 性能。

实现恒定时间 O(1) 查找需要将所有范围扩展为显式键。这需要大量内存，并且当您需要拆分或插入新范围时实际上会降低性能。这可能不是你想要的。