Слияние HashMaps из n списков

Question

Я постараюсь описать мою проблему как можно лучше, но, пожалуйста, спросите, есть ли вещи, которые не имеют смысла.

• У меня есть конечное число списков
• Каждый список содержит конечное количество контактов
• Каждый контакт представлен в виде HashMap
• Каждый список связан с провайдером
• Один и тот же контакт может присутствовать в нескольких провайдерах (и, следовательно, в нескольких списках).
• Мне нужен «основной» список, который содержит все уникальные записи в других списках

Я ищу эффективный способ объединения этих списков в основной список без дубликатов. Например, если один и тот же контакт появляется в нескольких списках (несколько HashMaps, соответствующих одному и тому же физическому лицу), я хочу объединить все HashMaps в один и поместить объединенный HashMap в основной список. Простая «перестановка» здесь не годится, поскольку мне нужно повторно набрать содержимое для эффективного доступа к ним (например, один провайдер дает мне список адресов электронной почты, помеченных как «электронные письма», а провайдер 2 дает мне ту же информацию, что и 'адресов электронной').

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

Проблема, из-за которой я почесал голову, заключается в эффективном сканировании списков ... нет ли другого способа, кроме линейного прохождения каждого списка во вложенном цикле, захвата следующего HashMap, проверки, существует ли он уже в списке mater? и слияние / создание нового ...?

Answer 1

Первое наблюдение - использование HashMap для представления запахов ваших контактов «отрицание объекта» .

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

Классу нужны геттеры для всех полей ключа контакта, и ему нужно реализовать equals, hashcode и Comparable на основе полей ключа. Методы получения (и, возможно, установки) также необходимы для неключевых полей.

При этом процесс слияния становится (псевдокод):

// If you haven't already done so
convert the master list of HashMaps to a list of Contact objects and sort it.
create an empty "new master" list

for each list of contact HashMaps:
    convert the list of HashMaps to a merge list of Contact objects
    sort the merge list
    iterate the sorted master and merge lists in parallel:
        if a master Contact matches a merge Contact:
            merge the two Contacts and add to the new master list
            advance both iterators
        if a master Contact has no corresponding merge Contact:
            copy the master Contact to the new master list
            advance the master iterator.
        if a merge Contact has no corresponding master Contact:
            add the merge Contact to the new master list.
            advance the merge iterator

Рабочие характеристики различных фаз должны быть:

• Преобразование N HashMaps в объекты Contact - O(N).
• Создание списка из N контактов - O(N)
• Сортировка списка N контактов - O(NlogN)
• Объединение 2 отсортированных списков - O(M + N).

Общая производительность должна быть лучше, чем O(NlogN), где N - общее количество основных и объединенных объектов Customer.

Answer 2

Для своего внутреннего основного списка, можете ли вы использовать класс, для которого вы можете определить значимый equals (), для инкапсуляции HashMap вместо простого хранения прямых HashMaps? Если бы вы это сделали, вы могли бы переключиться на использование реализации Collection, которая имеет постоянный поиск (например, HashSet) для Master List. Это исключит вложенную итерацию, и вам просто нужно будет проверить каждый контакт у провайдера один раз. Методом проб и ошибок можно определить, достаточно ли велико число контактов для улучшения.

Answer 3

Если ваши списки отсортированы, учтите следующее:

Создайте «объединяющий» итератор, который потребляет 2 итератора из ваших списков.
Если 2 головы одинаковы, бросьте одну. В противном случае представьте меньшее из двух.
Если одна голова от исчерпанного (пустого) итератора, просто представьте другую.

Теперь у вас есть итератор, который создает уникальную отсортированную последовательность из 2 итераторов.

Вы можете собрать их столько, сколько нужно, чтобы получить уникальный итератор для всех ваших списков.

Answer 4

Создайте Map<String,Contact>, используя класс, подобный приведенному ниже.Хотя я все еще не уверен, что вы подразумеваете под провайдером.Возможно, вы могли бы предоставить более подробную информацию об этом.

class Contact {

    enum ContactMethod {
        email,
        phone,
        address
    }

    String name;
    Map<ContactMethod,Set<String>> contactInfo;

    Contact(String name) {
        this.name = name;
        this.contactInfo = new HashMap<ContactMethod,Set<String>>();
    }

    void consume(Map<ContactMethod,String> info) {
        for(ContactMethod method : info.keySet()) {
            Set<String> modes = contactInfo.get(method);
            if(modes == null) {
                modes = new HashSet<String>();
                contactInfo.put(method,modes);
            }
            modes.add(info.get(method));
        }
    }
}