我正在寻找使用可选键创建快速查找(字典?)的方法,例如,假设我有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上的GetHashCodeCompositeKey以提供使组合键唯一的内容,以便Dictionary<TKey, TValue>能够存储唯一的组合键。

最后,我将能够以这种方式查询字典:

var value = dict[new CompositeKey(firstName: "Matías", lastName: "Fidemraizer" )];


OP在一些评论中问了这个问题:


  我考虑过这种方法,但是您将如何查询字典
  仅用于“ FirstName =” Matias”?


由于您要同时覆盖EqualsGetHashCode,因此可以将所有组合添加为整个字典中的键,并且它们可以在其中共存:

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/

10-11 14:10