c# - 您将如何通过多个键实现快速查找？

Question

我正在寻找使用可选键创建快速查找（字典？）的方法，例如，假设我有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

我应该能够查询出这些键的所有排列。您将为此使用哪种数据结构？您将如何实施？

Answer 1

您仍然可以使用常规字典，其中键可以是如下的自定义类型：

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! ;)
        }
    }
}