Структура данных поиска по нескольким ключам

#data-structures #dictionary #key #lookup

#структуры данных #словарь #Клавиша #поиск

Вопрос:

Мне нужен эффективный способ поиска пользователя по любому 1 из 3 разных ключей. Например, по идентификатору, имени пользователя или псевдониму.

Базовой концепцией будет структура данных, в которой вы можете использовать любой из 3-х различных типов ключей для поиска значения:

myDataStructure.lookupByName(name) -> User
myDataStructure.lookupById(id) -> User
myDataStructure.lookupByAlias(alias) -> User

Единственным непосредственным способом, который я могу придумать для этого, было бы иметь 3 отдельных словаря и использовать тот, который соответствует типу предоставленного ключа.

Есть ли более эффективный способ?

1. Три словаря — самый эффективный способ. Вы могли бы представить себе три отсортированных массива, отсортированных по трем различным типам ключей, с общими указателями на соответствующие значения.

Ответ №1:

Если вы знаете, что наборы ключей (имена, идентификаторы и псевдонимы) различны, вы могли бы поместить их все в одну таблицу. В противном случае вам понадобились бы три отдельные таблицы, которые вы отметили.

1. Я могу быть уверен, что каждый набор ключей будет отличаться, однако я не хочу, чтобы от меня требовали предоставлять все 3 для поиска пользователя.

2. Если таблица заполнена заранее, вам не обязательно указывать все три. Для поиска пользователя можно использовать любое из следующих действий. MyDataStructure. lookupByNameOrIdOrAlias(имя) -> USER, MyDataStructure. lookupByNameOrIdOrAlias(идентификатор) -> ПОЛЬЗОВАТЕЛЬ, MyDataStructure. lookupByNameOrIdOrAlias(псевдоним) -> ПОЛЬЗОВАТЕЛЬ

3. Если вы поместите все три в один словарь, не будете ли вы придерживаться линейного (то есть медленного) поиска? Используя три словаря, поиск будет O (log n) или O (1).

Ответ №2:

Это также может вам помочь. вы можете расширить его на несколько ключей http://www.codeproject.com/KB/recipes/multikey-dictionary.aspx