倒排索引執行的不同數據結構

Question

我想創建一個程序，它掃描文本文件的文件夾，分離每個單詞，並將它們添加到ArrayList。用戶可以搜索單個單詞，並且該程序將輸出該單詞存在於哪個文檔中。我最初的目標是使用HashMap，但我想知道是否還有其他更好或同等優秀的數據結構。

• 什麼是使用哈希映射對於這個特殊程序的好處？
• 可以使用哪些其他數據結構來解決這個問題？

Answer 1

對於這個任務，我會推薦一個HashMap<word, Set<text-file>，濫用Java通用語法。其中word作爲key和一組相關文本文件的值如下

爲什麼一個HashMap？

HashMap或Map提供查找和添加時間O(1)。

爲什麼設置裏面的地圖？

相同的單詞可以存在於多個文本文件中。 此外，如果文檔中的同一個詞已被記錄，設置數據結構不會存儲重複值和.contains和.add方法是O(1)

使用HashMap，當你嘗試做每個鍵的查找會花費你O(1) （假設你的哈希表工作正常），而其他實施可能會花費你至少O(log n)

如果你打算做這個任務的同時ConcurrentHashMap將成爲你的朋友

Answer 2

的HashMap是一種更好的解決方案，如果它來了以查找性能。

您還可以使用Google Guava Multimap其中多個值與單個密鑰相關。就像<Key, List<Value>>的地圖一樣。但是，使用Multimap的代碼看起來更清晰。您也可以使用SetMultimap。 SetMultimap不能包含重複的鍵值對。添加已經在multimap中的鍵值對將不起作用。