Алгоритм и структура данных для хранения имени и фамилии

Question

Есть ли эффективный способ сохранить имя и фамилию в структуре данных, чтобы мы могли искать, используя имя или фамилию? Я хотел бы рассмотреть бинарное дерево поиска с именем. Было бы эффективно искать имя. Но не будет эффективным при поиске фамилии. мы также можем рассмотреть еще один BST с фамилией. Любые идеи, чтобы реализовать это эффективно?

Что делать, если вопрос

Имена строк [] = {"A B", "C D"};

Требуется иметь возможность динамически расширять этот каталог во время выполнения, без постоянного хранения. Каталог может в итоге вырасти до сотен или тысячи имен и должны быть доступны для поиска по имени или фамилии.

Теперь мы не можем хранить хеш-таблицы. Есть идеи?

Answer 1

Две хеш-таблицы: одна от имени к человеку и одна от фамилии к человеку.

Просто лучше всего.

Answer 2

Почему бы не указать имена и фамилии в три ?

В качестве бонуса, таким образом, вы даже можете получить предложения по частичным именам, пройдя через все листья после текущего узла (возможно, при асинхронном вызове)

Answer 3

если вам нужно искать только по имени или только по фамилии, тогда да, две хеш-карты являются лучшими (и обратите внимание, что вы не дублируете данные, вы разделяете их), но если вы не возражаете, тогда поместите имена и фамилии в одну хэш-карту и не делайте различий между ними.

Answer 4

Также см. Есть ли в Java HashMap с обратным поиском? …, что характерно для Java, но обсуждение структур данных относится к любому языку.

Обратите внимание, что такие структуры, как двунаправленные отсортированные карты, также позволяют выполнять поиск по диапазону (а двойные хеш-таблицы не позволяют).

Answer 5

Ваша идея довольно хорошая, но есть еще один вариант: как насчет реализации хеш-таблиц?

Первая хеш-таблица будет использовать имена в качестве ключа, а соответствующее значение будет либо фамилией, либо указателем на объект Name. Вторая хеш-таблица будет использовать фамилии в качестве ключей, а имена или указатели на Name будут использоваться в качестве значений.

Лично для выбора значений я бы использовал указатель на объект Name, поскольку этот метод был бы более применим в случае, если вы хотите хранить еще больше информации (например, данные о рождении и т. Д.)