« Предыдущий • След • Затем »

Интерфейс Карты

A Map объект, который отображает ключи на значения. Карта не может содержать, делают дубликаты ключа: Каждый ключ может отобразиться на самое большее одно значение. Это моделирует математическую функциональную абстракцию. Map интерфейс следует.

public interface Map<K,V> {

    // Basic operations
    V put(K key, V value);
    V get(Object key);
    V remove(Object key);
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    int size();
    boolean isEmpty();

    // Bulk operations
    void putAll(Map<? extends K, ? extends V> m);
    void clear();

    // Collection Views
    public Set<K> keySet();
    public Collection<V> values();
    public Set<Map.Entry<K,V>> entrySet();

    // Interface for entrySet elements
    public interface Entry {
        K getKey();
        V getValue();
        V setValue(V value);
    }
}

Платформа Java содержит три общего назначения Map реализации: HashMap, TreeMap, и LinkedHashMap. Их поведение и производительность точно походят HashSet, TreeSet, и LinkedHashSet, как описано в разделе Интерфейса Набора. Кроме того, Hashtable был retrofitted, чтобы реализовать Map.

Сравнение с Хеш-таблицей

Если Вы использовали Hashtable, Вы уже знакомы с общими основами Map. (Конечно, Map интерфейс, в то время как Hashtable конкретная реализация.) Следующее существенные различия:

Map обеспечивает Collection представления вместо прямой поддержки итерации через Enumeration объекты. Collection представления значительно улучшают выразительность интерфейса, как обсуждено позже в этом разделе.
Map позволяет Вам выполнять итерации по ключам, значениям, или парам ключ/значение; Hashtable не предоставляет третью возможность.
Map обеспечивает безопасный способ удалить записи посреди итерации; Hashtable не сделал.

Наконец, Map исправления незначительный недостаток в Hashtable интерфейс. Hashtable вызывали метод contains, который возвращается true если Hashtable содержит данное значение. Учитывая его имя, Вы ожидали бы, что этот метод возвратится true если Hashtable содержавший данный ключ, потому что ключ является основным механизмом доступа для a Hashtable. Map интерфейс устраняет этот источник беспорядка, переименовывая метод containsValue. Кроме того, это улучшает непротиворечивость интерфейса — containsValue параллели containsKey.

Интерфейс карты Основные Операции

Основные операции Map (put, get, containsKey, containsValue, size, и isEmpty) ведите себя точно как их дубликаты в Hashtable. following program генерирует таблицу частот слов, найденных в ее списке параметров. Таблица частот отображает каждое слово на число раз, это происходит в списке параметров.

import java.util.*;

public class Freq {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<String, Integer>();

        // Initialize frequency table from command line
        for (String a : args) {
            Integer freq = m.get(a);
            m.put(a, (freq == null) ? 1 : freq + 1);
        }

        System.out.println(m.size() + " distinct words:");
        System.out.println(m);
    }
}

Единственной хитрой вещью об этой программе является второй параметр put оператор. Тем параметром является условное выражение, которое имеет эффект установки частоты к тому, если слово никогда не замечалось прежде или еще один чем его текущая стоимость, если слово было уже замечено. Попытайтесь выполнить эту программу с командой:

java Freq if it is to be it is up to me to delegate

Программа приводит к следующему выводу.

8 distinct words:
{to=3, delegate=1, be=1, it=2, up=1, if=1, me=1, is=2}

Предположите, что Вы предпочли бы видеть таблицу частот в алфавитном порядке. Все, что необходимо сделать, изменить тип реализации Map от HashMap к TreeMap. Создание этого четырехсимвольного изменения заставляет программу генерировать следующий вывод из той же самой командной строки.

8 distinct words:
{be=1, delegate=1, if=1, is=2, it=2, me=1, to=3, up=1}

Точно так же Вы могли заставить программу напечатать таблицу частот в порядке, к которому слова сначала появляются на командной строке просто, изменяя тип реализации карты LinkedHashMap. Выполнение так результаты в следующем выводе.

8 distinct words:
{if=1, it=2, is=2, to=3, be=1, up=1, me=1, delegate=1}

Эта гибкость приводит мощный пример питания основанной на интерфейсе платформы.

Как Setи Listинтерфейсы, Map усиливает требования к equals и hashCode методы так, чтобы два Map объекты могут быть сравнены для логического равенства без отношения к их типам реализации. Два Map экземпляры равны, если они представляют те же самые отображения значения ключа.

Условно, все общего назначения Map реализации предоставляют конструкторам, которые берут a Map возразите и инициализируйте новое Map содержать все отображения значения ключа в указанном Map. Этот стандарт Map конструктор преобразования полностью походит на стандарт Collection конструктор: Это позволяет вызывающей стороне создавать a Map из требуемого типа реализации, который первоначально содержит все отображения в другом Map, независимо от другого Map's тип реализации. Например, предположите, что у Вас есть a Map, именованный m. Следующая острота создает новое HashMap первоначально содержа все те же самые отображения значения ключа как m.

Map<K, V> copy = new HashMap<K, V>(m);

Операции Объема Интерфейса карты

clear работа делает точно, что Вы думали бы, что она могла сделать: Это удаляет все отображения из Map. putAll работа Map аналог Collection интерфейс addAll работа. В дополнение к его очевидному использованию дампа того Map в другого у этого есть второе, более тонкое использование. Предположите a Map используется, чтобы представить набор пар значения атрибута; putAll работа, в комбинации с Map конструктор преобразования, обеспечивает аккуратный способ реализовать создание карты атрибута со значениями по умолчанию. Следующее является статическим методом фабрики, который демонстрирует этот метод.

static <K, V> Map<K, V> newAttributeMap(Map<K, V>defaults, Map<K, V> overrides) {
    Map<K, V> result = new HashMap<K, V>(defaults);
    result.putAll(overrides);
    return result;
}

Представления набора

Collection методы представления позволяют a Map просматриваться как a Collection этими тремя способами:

keySet — Set из ключей, содержавшихся в Map.
values — Collection из значений, содержавшихся в Map. Это Collection не a Set, потому что многократные ключи могут отобразиться на то же самое значение.
entrySet — Set из пар ключ/значение, содержавшихся в Map. Map интерфейс обеспечивает маленький вложенный вызванный интерфейс Map.Entry, тип элементов в этом Set.

Collection представления обеспечивают единственные средства выполнить итерации по a Map. Этот пример иллюстрирует стандартную идиому для того, чтобы выполнить итерации по ключам a Map с a for-each создайте:

for (KeyType key : m.keySet())
    System.out.println(key);

и с iterator:

// Filter a map based on some 
// property of its keys.
for (Iterator<Type> it = m.keySet().iterator(); it.hasNext(); )
    if (it.next().isBogus())
        it.remove();

Идиома для того, чтобы выполнить итерации по значениям аналогична. Следующее является идиомой для того, чтобы выполнить итерации по парам ключ/значение.

for (Map.Entry<KeyType, ValType> e : m.entrySet())
    System.out.println(e.getKey() + ": " + e.getValue());

Сначала, много людей волнуются, что эти идиомы могут быть медленными потому что Map должен создать новое Collection экземпляр каждый раз a Collection работу представления вызывают. Останьтесь легкими: нет никакой причины этого a Map не может всегда возвращать тот же самый объект каждый раз, когда его просят относительно данного Collection представление. Это точно что весь Map реализации в java.util сделать.

Со всеми тремя Collection представления, вызывая Iterator's remove работа удаляет связанную запись из поддержки Map, принятие, что поддержка Map поддерживает удаление элемента для начала. Это иллюстрируется предыдущей идиомой фильтрации.

С entrySet представление, также возможно изменить значение, связанное с ключом, вызывая a Map.Entry's setValue метод во время итерации (снова, принимая Map поддерживает модификацию значения для начала). Отметьте, что они - единственные безопасные способы изменить a Map во время итерации; поведение является неуказанным если базовое Map изменяется любым другим способом, в то время как итерация происходит.

Collection представления поддерживают удаление элемента во всех его многих формах — remove, removeAll, retainAll, и clear операции, так же как Iterator.remove работа. (Все снова и снова это предполагает что поддержка Map поддерживает удаление элемента.)

Collection представления не поддерживают дополнение элемента при любых обстоятельствах. Это не имело бы никакого смысла для keySet и values представления, и это является ненужным для entrySet представление, потому что поддержка Map's put и putAll методы обеспечивают ту же самую функциональность.

Необычное Использование Представлений Набора: Алгебра Карты

Когда применено к Collection представления, объемные операции (containsAll, removeAll, и retainAll) удивительно мощные инструменты. Для стартеров предположите, что Вы хотите знать ли один Map подкарта другого — то есть, ли первое Map содержит все отображения значения ключа во втором. Следующая идиома добивается цели.

if (m1.entrySet().containsAll(m2.entrySet())) {
    ...
}

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

if (m1.keySet().equals(m2.keySet())) {
    ...
}

Предположите, что у Вас есть a Map это представляет набор пар значения атрибута, и два Sets представление необходимых атрибутов и допустимых атрибутов. (Допустимые атрибуты включают необходимые атрибуты.) Следующий отрывок определяет, соответствует ли карта атрибута этим ограничениям и печатает подробное сообщение об ошибке, если это не делает.

static <K, V> boolean validate(Map<K, V> attrMap, Set<K> requiredAttrs, Set<K>permittedAttrs) {
    boolean valid = true;
    Set<K> attrs = attrMap.keySet();

    if (! attrs.containsAll(requiredAttrs)) {
        Set<K> missing = new HashSet<K>(requiredAttrs);
        missing.removeAll(attrs);
        System.out.println("Missing attributes: " + missing);
        valid = false;
    }
    if (! permittedAttrs.containsAll(attrs)) {
        Set<K> illegal = new HashSet<K>(attrs);
        illegal.removeAll(permittedAttrs);
        System.out.println("Illegal attributes: " + illegal);
        valid = false;
    }
    return valid;
}

Предположите, что Вы хотите знать все ключи, характерные для два Map объекты.

Set<KeyType>commonKeys = new HashSet<KeyType>(m1.keySet());
commonKeys.retainAll(m2.keySet());

Подобная идиома получает Вас общие ценности.

Все идиомы, представленные к настоящему времени, были неразрушающими; то есть, они не изменяют поддержку Map. Вот некоторые, которые делают. Предположите, что Вы хотите удалить все пары ключ/значение что один Map имеет вместе с другим.

m1.entrySet().removeAll(m2.entrySet());

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

m1.keySet().removeAll(m2.keySet());

Что происходит, когда Вы начинаете смешивать ключи и значения в той же самой объемной работе? Предположите, что у Вас есть a Map, managers, это отображает каждого сотрудника в компании менеджеру сотрудника. Мы будем сознательно неопределенны о типах ключа и объектов значения. Это не имеет значения, пока они - то же самое. Теперь предположите, что Вы хотите знать, кто все "отдельные спонсоры" (или неменеджеры). Следующий отрывок говорит Вам точно, что Вы хотите знать.

Set<Employee> individualContributors = new HashSet<Employee>(managers.keySet());
individualContributors.removeAll(managers.values());

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

Employee simon = ... ;
managers.values().removeAll(Collections.singleton(simon));

Отметьте, что эта идиома использует Collections.singleton, статический метод фабрики, который возвращает неизменное Set с единственным, указанным элементом.

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

Map<Employee, Employee> m = new HashMap<Employee, Employee>(managers);
m.values().removeAll(managers.keySet());
Set<Employee> slackers = m.keySet();

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

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

Мультикарты

Мультикарта походит на a Map но это может отобразить каждый ключ на многократные значения. Платформа Наборов Java не включает интерфейс для мультикарт, потому что они не используются все это обычно. Это - довольно простой вопрос, чтобы использовать a Map чьи значения List экземпляры как мультикарта. Этот метод демонстрируется в следующем примере кода, который читает список слов, содержащий одно слово на строку (весь нижний регистр), и распечатывает все группы анаграммы, которые соответствуют критерию размера. Группа анаграммы является набором слов, все из которых содержат точно те же самые буквы, но в различном порядке. Программа берет два параметра на командной строке: (1) имя файла словаря и (2) минимальный размер группы анаграммы, чтобы распечатать. Группы анаграммы, содержащие меньше слов чем указанный минимум, не печатаются.

Есть стандартный прием для того, чтобы найти группы анаграммы: Для каждого слова в словаре расположите в алфавитном порядке буквы в слове (то есть, переупорядочьте буквы слова в алфавитный порядок), и поместите запись в мультикарту, отображая расположенное в алфавитном порядке слово на исходное слово. Например, слово плохие причины запись, отображающаяся abd в плохо, чтобы быть помещенным в мультикарту. Отражение момента покажет, что все слова, к которым любые данные контурные карты формируют группу анаграммы. Это - простой вопрос, чтобы выполнить итерации по ключам в мультикарте, распечатывая каждую группу анаграммы, которая встречает ограничение размера.

The following program прямая реализация этого метода.

import java.util.*;
import java.io.*;

public class Anagrams {
    public static void main(String[] args) {
        int minGroupSize = Integer.parseInt(args[1]);

        // Read words from file and put into a simulated multimap
        Map<String, List<String>> m = new HashMap<String, List<String>>();

        try {
            Scanner s = new Scanner(new File(args[0]));
            while (s.hasNext()) {
                String word = s.next();
                String alpha = alphabetize(word);
                List<String> l = m.get(alpha);
                if (l == null)
                    m.put(alpha, l=new ArrayList<String>());
                l.add(word);
            }
        } catch (IOException e) {
            System.err.println(e);
            System.exit(1);
        }

        // Print all permutation groups above size threshold
        for (List<String> l : m.values())
            if (l.size() >= minGroupSize)
                System.out.println(l.size() + ": " + l);
    }

    private static String alphabetize(String s) {
        char[] a = s.toCharArray();
        Arrays.sort(a);
        return new String(a);
    }
}

Выполнение этой программы на файле словаря с 173,000 словами с минимальным групповым размером анаграммы восемь производит следующий вывод.

9: [estrin, inerts, insert, inters, niters, nitres, sinter,
     triens, trines]
8: [lapse, leaps, pales, peals, pleas, salep, sepal, spale]
8: [aspers, parses, passer, prases, repass, spares, sparse,
     spears]
10: [least, setal, slate, stale, steal, stela, taels, tales,
      teals, tesla]
8: [enters, nester, renest, rentes, resent, tenser, ternes,
     treens]
8: [arles, earls, lares, laser, lears, rales, reals, seral]
8: [earings, erasing, gainers, reagins, regains, reginas,
     searing, seringa]
8: [peris, piers, pries, prise, ripes, speir, spier, spire]
12: [apers, apres, asper, pares, parse, pears, prase, presa,
      rapes, reaps, spare, spear]
11: [alerts, alters, artels, estral, laster, ratels, salter,
      slater, staler, stelar, talers]
9: [capers, crapes, escarp, pacers, parsec, recaps, scrape,
     secpar, spacer]
9: [palest, palets, pastel, petals, plates, pleats, septal,
     staple, tepals]
9: [anestri, antsier, nastier, ratines, retains, retinas,
     retsina, stainer, stearin]
8: [ates, east, eats, etas, sate, seat, seta, teas]
8: [carets, cartes, caster, caters, crates, reacts, recast,
     traces]

Многие из этих слов кажутся немного поддельным, но это не отказ программы; они находятся в файле словаря. Вот dictionary file мы использовали. Это было получено из Общедоступного Домена, ВКЛЮЧАЮТ ссылочному списку слов сравнительного теста.

«Предыдущий • След • Затем»