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

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