鬆散詞典，需要諮詢

我需要創建一個口令，其中鍵是字符串，值是對象。但我不希望密鑰與用戶提供的字符串完全匹配。相反，我想要鍵包含字符串的一部分。讓我通過示例來解釋鬆散詞典，需要諮詢

如果在密鑰「Johnson」下的字典中有條目，我希望能夠在給定輸入字符串「John」，「Jo」的情況下找到值。另外我希望能夠提取幾個匹配輸入字符串的值。例如，如果有條目「John A」和「John B」，我希望具有像FindFirst這樣的功能，它會將迭代器返回到第一個匹配值。

理想我寧願使用現有System.Collections.Generic.Dictionary 可能派生新類並覆蓋一些方法

來源

2009-12-07 Captain Comic

它聽起來像你真的想要一個trie – 2009-12-07 11:16:24

我懷疑SortedList<TKey, TValue>將是在這裏你最好的選擇，這是一種基於二叉搜索樹的字典。其Keys財產返回一個IList<TKey> O（1）訪問時間。

你會獲取Keys財產和執行二進制搜索，找到與你的搜索鍵啓動鍵。然後從該示例鍵上下查找實際匹配的鍵的範圍。這會給O（log n）性能，而不是通過查看所有鍵的O（n）性能。

我不會從這個雖然獲得 - 我會寫這有一個SortedList<,>內部一個類型。

來源

2009-12-07 10:31:21

你絕對正確的是，SortedList（而不是SortedDictionary）將通過在Keys集合上允許O（1）操作來幫助查找範圍。更有效率的方法可能是僅僅對List 進行排序並對其進行二分搜索，以避免必須通過鍵查找值。 – SoftMemes 2009-12-07 10:55:27

儘管當然Values集合可以通過索引來訪問（索引與鍵的索引相同），所以它不是一個真正的問題。沒關係。 – SoftMemes 2009-12-07 10:56:51

雖然我懷疑一本字典是否適合這樣的事情，你可以使用：

dictionary[dictionary.Keys.First(d=>d.StartsWith("Jo"))]

你失去了最字典的價值在這裏，因爲它的價值的快速檢索優化，通過使用該密鑰。在這種情況下，你必須迭代列表中的每個鍵。

我得+1喬恩您指出SortedList<TKey,TValue>

來源

2009-12-07 10:27:41

可以通過提供的IEqualityComparer實現與使用自定義詞典相等比較。然而，Dictionary是一個散列映射，需要從每個鍵映射到同一個整數散列，這使得它在你的情況下不太有用。您可以使用SortedDictionary（也是IDictionary），提供自定義IComparer並獲得O（log（n））查找時間（而不是字典理想情況下可以提供的O（1））。

來源

2009-12-07 10:35:12 SoftMemes

注意自我：這不能解決多個匹配的問題，SortedDictionary將只返回第一個「相等」鍵。 – SoftMemes 2009-12-07 10:47:54

你可以使用一個正常字典並提供你自己的比較器，看看generic dictionary，特別是關於providing your own comparer的部分。

的主要問題是，你基本上是要比較對所有鍵，直到你找到一個匹配，由於您使用的自定義規則，所以請確保您的自定義比較迅速地退出。如果不能匹配（例如開始用不同的字母）。

來源

2009-12-07 10:37:14

你打算GetHashCode在這種情況下返回什麼？ – SoftMemes 2009-12-07 10:48:48

我想你應該考慮將來自基礎記錄的訪問相應的鍵搜索。

那你，例如，有單純的鍵的B樹+結構，其中您找到第一個匹配的記錄，那麼按照B樹+枚舉，直到你有不匹配。

與數據庫中的非聚簇索引類似。首先你找到鑰匙，然後找到記錄。

「Johnson」中的示例「Jo」和「John」是「StartsWith（）」的示例，其中關鍵排序將有利於您。如果你也希望僅僅尋找一個子字符串而不是僅僅是初始段，那麼你需要查看其他存儲和查找密鑰的算法。

如果你不積極，你們都需要並且能夠利用優化搜索，那麼你應該對所有的鍵進行內存中的掃描，然後專注於優化匹配的謂詞。例如，使用預編譯搜索的Regex選項。

來源

2009-12-07 11:04:49 Tormod

btree與內存中的搜索有什麼關係？ – SoftMemes 2009-12-07 11:47:45

鬆散詞典，需要諮詢

回答

相關問題