尋找類似HashSet的東西，但是鍵值的範圍有多大？

我想知道是否有像HashSet這樣的東西，但鍵值的範圍。例如，我們可以在100到4000之間添加一個鍵入所有整數的項目。如果我們使用100到4000之間的任何鍵，例如， 287.尋找類似HashSet的東西，但是鍵值的範圍有多大？

我希望查找速度非常接近HashSet，即O（1）。可以使用二分搜索來實現這一點，但這對於需求來說太慢了。我想盡可能使用標準的.NET API調用。

更新

這很有趣：https://github.com/mbuchetics/RangeTree

它爲O的時間複雜度（日誌（N）），其中N是區間數，所以它不完全O（1），但它可以用來構建一個工作實現。

來源

2016-08-22 Contango

爲什麼不直接使用HashSet與匹配所需邏輯的比較器？ –

但是HashSet沒有密鑰。 – Paparazzi

是否有任何關於範圍的知識，或者它們可以是任何東西？ – Chris

我不相信已經有一個結構。你可以實現像一個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的到字典

來源

2016-08-22 10:46:11 suwik

我無法在msdn文檔中找到對「HashSet 」的任何引用。我是否錯過了某些東西，或者是來自第三方圖書館的東西，還是您真的想在這裏使用字典？ – Chris

感謝您的回答。但是，這似乎要求您知道您想要檢索項目的範圍 - 但我們不知道該點的範圍！ – Contango

另外值得注意的是，「找到一個範圍，包括該鍵和返回_set [範圍]」的過程不會是O（1），因爲OP正在請求我認爲... – Chris

這裏是你可以嘗試的解決方案。但是它假定一些要點：

沒有範圍重疊
當你請求一個數字，它是一個有效的範圍內（沒有錯誤檢查）

從你說的話，這個人是O（N），但你可以用我很小的努力使它成爲O（log（N））。

想法是，一個類將處理範圍事物，它將基本上將給定的任何值轉換爲其範圍的下邊界。這樣你的Hashtable（這裏是一個字典）包含低邊界作爲鍵。

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，那麼它在每兩個迭代分裂...

來源

2016-08-22 13:29:14

尋找類似HashSet的東西，但是鍵值的範圍有多大？

回答

相關問題