我有一個範圍元素的數組。每個元素都有一個開始和結束。在數組中，範圍不重疊，並對它們進行排序。散列範圍
即（代碼只是爲了說明這一點，不要指望它來編譯）：
var arr = { [0,3], [5,10], [15,59] };
給定值（比如9），是有範圍的哈希函數，讓我快速獲取具有包含該值的範圍的元素？
當然有一種天真的解決方案，只是循環每個元素，直到找到合適的;更精細的一個，如範圍開始的二進制搜索;以及創建一個具有範圍的二叉樹的專利技術。
但有誰知道使用散列的方法嗎？
您可以創建一個索引，以便在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);
現在，讓你可以做的dictStart字典對於較高的值來搜索的第一個元素的值的二進制搜索範圍。然後採取以前的條目。
很難解釋。作爲一個例子查找9.做搜索得到元素e = [5,1]。
var range = arr[e[1]]; // = [5, 10]
bool isWithin = val <= range[1] && val >= range[0];
因此，它將減少內存侵入。關鍵是要快速搜索範圍的起始值。
我想它會解決這個問題，但它不是一個散列。
不是我正在尋找的東西，但它給了我一個主意。 標準化範圍的結束，然後使用每個標準化開始範圍的最後4位來計算桶。散列可以變成int [] []的形式，其中第一個數組是桶，而鋸齒形是屬於該桶的範圍列表。 謝謝 – JorgeLeo 2010-08-19 18:13:29
您可以預先計算最近的neigbour並將其存儲在某個地方。在你的例子中，表格有0..59個條目，並且你在每個索引處存儲最近範圍的索引。
這樣，它會非常快。
我喜歡這個解決方案。您的查找值然後成爲您的表中的索引，並且該表返回arr []的索引。 2查找，你就完成了。它會迅速獲得內存密集，但它很好地解決了這個問題。 – 2010-08-18 20:38:08
請注意，在示例中範圍之間有空洞，沒有0到59個條目。確實可以用空值來代替這些洞，但是它在範圍內擊敗了它的能力，記憶力消耗天空火箭。我看到的範圍在0到2百萬之間，中間有很多漏洞，我需要在內存中保留60k或更多的這些集合（因此爲什麼是範圍） 這就是爲什麼我要找一個哈希解決方案。以我可以回答問題的方式散列範圍：這個位置是在一個範圍內（哪一個），還是落在一個洞中？ – JorgeLeo 2010-08-18 21:18:37
這不使用散列（即使我懷疑散列是一個很好的解決方案）。 – Frank 2010-08-18 21:18:50
如何使用Dictionary<int, Element>來保存所有範圍內的所有數字，即添加四個條目
0, [0,3]
1, [0,3]
2, [0,3]
3, [0,3]
等等的其他範圍。它通過使用Dictionary來使用散列，但我懷疑它是最有效的解決方案。
順便說一句。我必須是一個函數，散列表不計算。 – JorgeLeo 2010-08-18 21:25:53