Разработать структуру данных для телефонного справочника

Question

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

Мы можем использовать 2 хэш-карты следующим образом

Map<String,int>
Map<int,String>

Но для этого требуется вдвое больше памяти. Кто-нибудь может предложить другое решение?

Answer 1

Двунаправленная карта (или «двунаправленная карта») карта, которая сохраняет уникальность его ценности, а также его ключи. Это ограничение включает бимапс поддерживать "обратный взгляд", который другой бимап, содержащий тот же записи, как этот BIMAP, но с перевернутые ключи и значения.

http://guava -libraries.googlecode.com / SVN / багажник / Javadoc / COM / Google / общие / собирать / BiMap.html

BiMap<String, Integer> biMap = HashBiMap.create();

biMap.put("Mike", 123);
biMap.put("John", 456);
biMap.put("Steven", 789);

BiMap<Integer, String> invertedBiMap = biMap.inverse();

Редактировать: Мультикарты

Multimap<String, String> multimap = HashMultimap.create();
multimap.put("John", "111111111");
multimap.put("John", "222222222");
multimap.put("Mike", "333333333");

System.out.println(multimap.get("John")); //[222222222, 111111111]

for(Map.Entry<String, String> entry : multimap.entries()){
    if(entry.getValue().equals("222222222")){
        System.out.println(entry.getKey()); //John
    }
}
//or

Multimap<String, String> inverted = HashMultimap.create();
Multimaps.invertFrom(multimap, inverted);
System.out.println(inverted.get("222222222")); //[John]

Answer 2

Один человек может иметь более одного номера, а один номер может принадлежать более чем одному человеку (членам семьи). И, как сказал Ник, номер телефона в общем случае может иметь нечисловые символы. Учитывая все вышесказанное, вместо Map<String,int> вы можете использовать Map<String,List<String>> или иметь только указатели на строки (в терминах C ++), чтобы избежать избыточности: Map<String*,List<String*>>.

Answer 3

Использование двоичного дерева поиска для реализации телефонного справочника - лучший способ сделать это.Подумайте о практической реализации телефонного списка контактов мобильного телефона.Сортируется по алфавиту.Если использовать шаблон карты, мы не получим отсортированный список.Вы не можете сортировать элементы карты, и это не эффективно.

Единственный способ сделать это - способ двоичного дерева.Так как при добавлении новой записи она вставляется упорядоченным способом.Таким образом, сортировка не требуется.Уже заказано.Помните, что left_tree

Answer 4

другая возможность - хранить строки в три , а знак '$' указывает конец каждой строки. используйте двусвязные указатели для каждого шага и удерживайте указатель с двойной связью от каждого «$» (конец имени) до его номера (в массиве или списке).

сейчас, когда вы хотите получить телефон от имени:

find the '$' indicating the end of the word for this string.
it is connected to a number in a list - that is your number.

когда вы хотите получить имя с телефона:

find the number, it is connected to a '$' sign.
follow the up-links all the way to the root, this will get you the name (reversed). 
reverse it and you are done.

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