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

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

Что, если речь идет о

имена String [] = { "A B", "C D"};

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

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

источник

2011-12-21 klaks

проблема кажется несколько расплывчатым, вы хотите, учитывая одну строку , найдите либо последнее, либо первое имя, которое соответствует, вы хотите искать по фамилии и фамилии отдельно, или вы хотите найти комбинацию из первого и последнего имени? Для первых двух случаев я бы пошел с отдельными BST, вы могли бы пойти с BST, вложенными в BST, для последнего случая – pasha

Вы можете представить себе сценарий адресной книги. нам присваивается список имен, таких как emp.setName ("A", "J"), emp.setName ("B", "C"), ... Мне нужно получить данные emp либо при поиске по имени или фамилия – klaks

Это тоже работает в вышеуказанном сценарии? – klaks

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

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

источник

2011-12-21 21:04:01

Да, это решение прост, но вы считаете его эффективным. Мне нужны два хэшмапа для тех же данных? – klaks

Ну, это быстро: средний O (1) для любого поиска.Вставка и удаление - среднее значение O (1), а также пробел O (n). Вы не сохраняете одни и те же данные дважды, вы храните таблицы поиска. Я не думаю, что вы получите асимптотически лучше этого. Я не знаю, сколько контактов у вас будет, но я не вижу, чтобы это было узким местом памяти. –

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

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

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

источник

2011-12-21 21:05:40

Также см. Does Java have a HashMap with reverse lookup? ..., который является специфическим для Java, но обсуждение структур данных относится к любому языку.

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

источник

2011-12-27 15:04:08

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

источник

2011-12-27 15:13:18

Почему бы не поместить имя и имя себе в ? Trie?

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

источник

2014-06-12 12:57:28

Trie так же быстро, как хэш, и вы не получаете столкновение с хешем. – Raz

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

ответ

Смежные вопросы