搜索前一個最近的日期/字符串在（散列）地圖

我遇到了一個問題，我可能需要重新設計我的數據結構。搜索前一個最近的日期/字符串在（散列）地圖

現在我有很多按時間順序排列的信息，並將它保存在Hashmap中，其中的密鑰是date，它也是new Info()的成員。

hashMap.put(date.toString(), new Info(date, ...))

日期與間隔5分鐘

2012-02-15 22:45:00.0
2012-02-15 22:50:00.0
2012-02-15 22:55:00.0
2012-02-15 23:00:00.0
...
2012-02-25 12:10:00.0
2012-02-25 12:15:00.0

到目前爲止，它很容易被拿到鑰匙和速度獲取信息是恆定的時間
hashMap.get(date.toString())

到目前爲止，當我碰到的HashMap是有日期良好。但現在信息的時間順序可能存在差距。在下面的例子中，缺少2012-02-15 22:50:00.0，所以當搜索那個日期時，我會得到NPE。
在這種情況下，我必須找到以前的最近的時間。

2012-02-15 22:45:00.0
2012-02-15 22:55:00.0
2012-02-15 23:00:00.0 ...

if (hashMap.get(date.toString()) != null) { 
    // found it 
} else { 
    return previousTime(date.toString()) 
}

我可以做一個LinkedHashMap的和previousTime可能只是iterate over the collection，直到我找到最近的一個日期。但最糟糕的情況是O（n）的複雜性。這種類型的任務能有更好的數據結構嗎？還是隻使用LinkedHashMap？ SortedMap like here？但最初put將是昂貴的，它會佔用更多的內存。

來源

2012-03-04 Skyzer

這聽起來像我NavigableMap如TreeMap正是你在找什麼。儘管您不應該使用日期的String格式作爲您的密鑰...使用Date本身。

來源

2012-03-04 15:38:32 ColinD

謝謝。我用這個和'lowerKey（）'的作品，很容易找到以前的日期 – Skyzer 2012-03-04 16:43:01

但是最糟糕的情況是O（n）的複雜性

多大將這個n爲？即使它是一百萬，我也不認爲這是一個問題。不止這可能是一個問題，但在你擔心速度之前，我想你會首先耗盡內存。從找到問題日期的位置開始，每5分鐘進行一次反向迭代。

來源

2012-03-04 15:42:26 LeleDumbo

n將高達100k。''''''''''''''''''''''''''但是從查詢日期未找到的地方開始，每5分鐘進行一次反向迭代。「但是我怎樣才能在hashmap中找到問題日期未找到的地方？鍵/值被散列，並且它們不是按照精確順序 – Skyzer 2012-03-04 15:50:27

是的，但是您知道它們在5分鐘範圍內。只是在'get'返回null時循環。 – LeleDumbo 2012-03-05 02:09:51

搜索前一個最近的日期/字符串在（散列）地圖

回答

相關問題