我正在寻找使用可选键创建快速查找(字典?)的方法,例如,假设我有3个键:“ first_name”,“ last_name”,“ zipcode”
因此,我希望能够执行以下操作(伪代码):
GetValue(first_name) -- would return a list of everyone with that first name
GetValue(first_name, last_name) -- would return a list of everyone with that first name & last name
GetValue(zipcode, first_name) -- would return a list of everyone with that first_name in the specified zipcode
我应该能够查询出这些键的所有排列。您将为此使用哪种数据结构?您将如何实施?
最佳答案
您仍然可以使用常规字典,其中键可以是如下的自定义类型:
public class CompositeKey
{
public CompositeKey(string firstName, string lastName, string zipCode)
{
FirstName = firstName;
LastName = lastName;
ZipCode = zipCode;
}
public string FirstName { get; }
public string LastName { get; }
public string ZipCode { get; }
}
现在,我将覆盖
Equals
上的GetHashCode
和CompositeKey
以提供使组合键唯一的内容,以便Dictionary<TKey, TValue>
能够存储唯一的组合键。最后,我将能够以这种方式查询字典:
var value = dict[new CompositeKey(firstName: "Matías", lastName: "Fidemraizer" )];
OP在一些评论中问了这个问题:
我考虑过这种方法,但是您将如何查询字典
仅用于“ FirstName =” Matias”?
由于您要同时覆盖
Equals
和GetHashCode
,因此可以将所有组合添加为整个字典中的键,并且它们可以在其中共存:Person person = new Person { /* Set members here */ }
// Note that I'll add many keys that have the same value
dict.Add(new CompositeKey(name: "Matías"), person);
dict.Add(new CompositeKey(lastName: "Fidemraizer"), person);
dict.Add(new CompositeKey(firstName: "Matías", lastName: "Fidemraizer"), person);
每个键将导致不同的哈希码,因此它们都可以共存于同一字典中,并且它们将提供强大的工具来按许多条件和条件组合进行查询。
另一种方法
另一种方法可能是使用多个字典,其中它们的键是使用某些约定的整个值的串联,而这些值是整个类的实例:
Dictionary<string, Person> names = new Dictionary<string, Person>();
names.Add("matias", new Person { /* Set members here */ });
Dictionary<string, Person> names = new Dictionary<string, Person>();
names.Add("matias:fidemraizer", new Person { /* Set members here */ });
// And so on, for every criteria you want to search...
稍后,您将实现代理,以根据给定的条件确定要查询的词典。
那Redis呢
实际上,您应该看一下Redis,这是一个键值存储,具有复杂的数据结构,这些值包括散列,集合,排序集合等等。也就是说,您可以集中缓存并使用Redis进行分发,并且缓存可能被许多应用程序占用。
它的使用和安装非常简单(可执行文件不到10MB ...)。
@Paparazzi提出了字典方法的问题
他说:
第二个名字相同的人呢?
如果OP需要考虑这种情况(是的,这不是一个例外情况,那么值得考虑一下!),似乎OP需要将数据存储在字典中,其中键是整个复合键,而值应该是
List<Person>
,HashSet<Person>
甚至LinkedList<Person>
。此外,这意味着一个键(插槽)将能够存储许多人,并且诸如让名字为
"Matías"
的人这样的查询将始终返回IEnumerable<Person>
的实现(列表,哈希,链表... ),在整个返回的集合中都可以找到以下人员:KeyValuePair<CompositeKey, ISet<Person>> result;
if(dictionary.TryGetValue(new CompositeKey(firstName: "Matías"), out result))
{
// I've got either one or many results and I'll decide what to do in
// that case!
}
同样,这种增强的方法还有另一个可能的问题。当您使用诸如
new CompositeKey(firstName: "Matías")
之类的复合键查询时,整个词典存储区中存储的名字可能不止一个具有"Matías"
的人,您将得到一个ISet<Person>
,IList<Person>
或LinkedList<Person>
。获得一个或多个结果的第一个搜索的复杂度
O(1)
(恒定时间),因为整个组合键是基于其哈希码存储的,但是第一个搜索的返回结果不再是字典,并且任何针对它们将是O(N)(获得的项目越多,找到结果所花费的时间就越多)。顺便说一句,如果您要按姓氏查找某人,那是因为您知道您可以获得的结果不止一个,而且除非只有一个全名的人被存储在其中,否则您就不会期望找到一个人词典。
因此,如果结果的计数大于
1
,则似乎需要消除歧义,这可以通过提供比名字更大的组合键来执行另一个O(1)
搜索来完成,或者可以使用某些人工用户(或人工智能...)将需要手动选择结果之一。综上所述:
如果您通过提供一种要素来寻找人,那您将承担获得超过结果的风险。然后,如果它是具有UI或某种人工智能的应用程序,则根本不应该进行搜索,而应直接从结果中选择一项(这是具有
O(1)
复杂性的操作):KeyValuePair<CompositeKey, ISet<Person>> result;
if(dictionary.TryGetValue(new CompositeKey(firstName: "Matías"), out result))
{
if(result.Value.Count > 1)
{
// Here you would show the user what you've found in the UI
// and the whole user would choose one of the results directly,
// which is an operation with O(1) complexity
}
else if(result.Value.Count <= 1)
{
// OK, I got 0 or 1 result, this is easier than I thought! ;)
}
}
如果您通过提供一个组件来寻找人,并且一旦您的应用程序意识到它所提供的不仅仅是一个结果,它就可以自动提供另一个组件,那么您将不会针对该结果执行搜索,而是将提供一个新的复合键为主要字典提供更多组件,幸运的是,您将获得一个结果。
public KeyValuePair<CompositeKey, ISet<Person>> SearchPerson(CompositeKey key)
{
KeyValuePair<CompositeKey, ISet<Person>> result;
if(dictionary.TryGetValue(new CompositeKey(firstName: "Matías"), out result))
{
if(result.Value.Count > 1)
{
// Oops! More than one result..... BUT I already know another
// component that will make the whole key absolutely unique, so
// I'll call this method recursively to specialize the search even
// more. Obviously, I've hardcoded the ZIP code as a sample, but
// in a real-world case, who knows from where I would get this
// ZIP code... Maybe from some geolocalization query based on current
// user's location?
// Wait, it might happen that a person called Matías could live
// in a location near be so this other person would have stored
// the same ZIP code... Well, this goes outside the scope of this
// Q&A. It's just an example of what to do, in an actual application
// there should be many other choices to disambiguate persons
// automatically...
return SearchPerson(new CompositeKey(firstName: key.FirstName, zipCode: "03984"));
}
else if(result.Value.Count <= 1)
{
// OK, I got 0 or 1 result, this is easier than I thought! ;)
}
}
}
关于c# - 您将如何通过多个键实现快速查找?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/38774757/