Функциональность Map
ArrayList позволяет вам выбирать из последовательности объектов, используя номер, другими словами, он ассоциирует номера с объектами. Но что, если вы хотите выбирать из последовательности объектов, используя какой-то другой критерий? Например, стек: его критерием выбора является “последняя вещь, втолкнутая в стек”. Мощными поворотными моментами этой идеи “выборки из последовательности” поочередно стали карта (map), словарь (dictionary) или ассоциативный массив (associative array). Концептуально они выглядят как ArrayList, но вместо поиска объектов по номерам вы ищете их, используя другой объект. Часто это является ключевым процессом в программе.
Эта концепция показана в Java как интерфейс Map. Метод put(Object key, Object value) добавляет значение (то, что вы хотите) и ассоциирует с ним ключ (то, по чем вы будете искать). get(Object key) производит значение по соответствующему ключу. Вы также можете проверить Map, узнав, содержится ли там ключ или значение с помощью containsKey( ) и containsValue( ).
Стандартная библиотека Java содержит два различных типа Map: HashMap и TreeMap. Оба они имеют один и тот же интерфейс (так как они оба реализуют Map), но они отличаются одним способом: эффективностью. Если вы думаете, что это должно выполнятся с помощью get( ), это выглядит приятно медленным, например, при поиске в ArrayList, содержащем ключи. HashMap - достаточно скоростной контейнер. Вместо медленного поиска ключа, он использует специальное значение, называемое хеш-код. Хэш-код - это способ получения определенной информации об объекте путем опроса и включения “относительно уникального” int для этого объекта. Все Java объекты могут производить хеш-код, а метод hashCode( ) - это метод корневого класса Object. HashMap берет hashCode( ) объекта и использует его для быстрого вылавливания ключа. В результате получаем ощутимое прибавление производительности [50].
| Map (Интерфейс) | Содержит ассоциированные пары ключ-значение, так что вы можете производить поиск значения, используя ключ. | |
| HashMap* | Реализация, основывающая на хеш-таблице. (Используйте это вместо Hashtable.) Обеспечивает постоянную по времени производительность при вставлении и поиске пар. Производительность может регулироваться конструктором, который позволяет вам устанавливать емкость и коэффициент загрузки хеш-таблицы. | |
| TreeMap | Реализация, основывающаяся на красно-черном дереве. Когда вы просматриваете ключи или пары, они будут упорядочены (определяется Comparable или Comparator, будет обсуждаться позднее). Преимущество TreeMap в том, что вы получаете результат отсортированным. TreeMap - это просто Map с методом subMap( ), который позволяет вам возвращать часть дерева. |
Иногда вам также будет необходимо знать детали о работе хеширования, так что мы рассмотрим это немного позже.
Приведенный пример использует метод Collections2.fill( ) и проверяет множества данных, которые только что были определены:
//: c09:Map1.java
// То, что вы можете делать с Maps.
import java.util.*; import com.bruceeckel.util.*;
public class Map1 { static Collections2.StringPairGenerator geo = Collections2.geography; static Collections2.RandStringPairGenerator rsp = Collections2.rsp; // Производим Set ключей:
public static void printKeys(Map m) { System.out.print("Size = " + m.size() +", "); System.out.print("Keys: "); System.out.println(m.keySet()); } // Производим Collection значений:
public static void printValues(Map m) { System.out.print("Values: "); System.out.println(m.values()); } public static void test(Map m) { Collections2.fill(m, geo, 25); // Map имеет поведение 'Set' для ключей:
Collections2.fill(m, geo.reset(), 25); printKeys(m); printValues(m); System.out.println(m); String key = CountryCapitals.pairs[4][0]; String value = CountryCapitals.pairs[4][1]; System.out.println("m.containsKey(\"" + key + "\"): " + m.containsKey(key)); System.out.println("m.get(\"" + key + "\"): "
+ m.get(key)); System.out.println("m.containsValue(\"" + value + "\"): " + m.containsValue(value)); Map m2 = new TreeMap(); Collections2.fill(m2, rsp, 25); m.putAll(m2); printKeys(m); key = m.keySet().iterator().next().toString(); System.out.println("First key in map: "+key); m.remove(key); printKeys(m); m.clear(); System.out.println("m.isEmpty(): " + m.isEmpty()); Collections2.fill(m, geo.reset(), 25); // Операции над Set меняют Map:
m.keySet().removeAll(m.keySet()); System.out.println("m.isEmpty(): " + m.isEmpty()); } public static void main(String[] args) { System.out.println("Testing HashMap"); test(new HashMap()); System.out.println("Testing TreeMap"); test(new TreeMap()); } } ///:~
Методы printKeys( ) и printValues( ) не только полезные утилиты они также производят Collection из видов Map. Метод keySet( ) производит Set поддерживаемых ключей в Map. Схожая трактовка дана values( ), который производит Collection, содержащий все значения из Map. (Обратите внимание, что хотя ключи должны быть уникальными, значения могут дублироваться.) Так как эти Collection содержаться в Map, то любые изменения Collection отразятся и в ассоциированном Map.
Оставшаяся часть программы приводит пример каждой операции с Map и проверяет каждый тип Map.
В качестве использования HashMap, рассмотрим программу для проверки случайности метода Java Math.random( ). В идеале, он должен производить равномерно распределенные случайные числа, но для проверки этого вам необходимо сгенерировать группу случайных чисел и посчитать сколько из них попадет в различные пределы. HashMap лучше всего подходит для этого, так как она ассоциирует объекты с объектами (в этом случае, значение объекта содержит число, произведенное Math.random( ) наряду с количеством вхождений этого числа):
//: c09:Statistics.java
// Простая демонстрация HashMap.
import java.util.*;
class Counter { int i = 1; public String toString() { return Integer.toString(i); } }
class Statistics { public static void main(String[] args) { HashMap hm = new HashMap(); for(int i = 0; i < 10000; i++) { // Производим число от 0 до 20:
Integer r = new Integer((int)(Math.random() * 20)); if(hm.containsKey(r)) ((Counter)hm.get(r)).i++; else
hm.put(r, new Counter()); } System.out.println(hm); } } ///:~
В main( ) при каждой генерации случайного числа оно помещается в класс-оболочку Integer, так чтоб эта ссылка могла использоваться HashMap. (Вы не можете использовать примитивные типы с контейнером, только ссылки на объект.) Метод containsKey( ) проверяет, есть ли ключ уже в контейнере. (То есть, было ли число уже найдено?) Если это так, метод get( ) производит ассоциированное значение для этого ключа, которое, в этом случае, является объектом Counter. Значение i внутри счетчика инкрементируется, указывая, что определенное случайное число было обнаружено еще раз.
Если ключ до сих пор не был найден, метод put( ) поместит новую пару ключ-значение в HashMap. Так как Counter автоматически инициализирует свою переменную i при создании, это указывает на первое появление определенного случайного числа.
Для отображения HashMap, он просто печатается. Метод HashMap toString( ) проходит по всем парам ключ-значение и вызывает toString( ) для каждого из них. Integer.toString( ) является предопределенным и вы можете видеть toString( ) для Counter. При запуска мы получим такой вывод (после добавления нескольких символов конец строки):
{19=526, 18=533, 17=460, 16=513, 15=521, 14=495, 13=512, 12=483, 11=488, 10=487, 9=514, 8=523, 7=497, 6=487, 5=480, 4=489, 3=509, 2=503, 1=475, 0=505}
Вы можете быть удивлены необходимость класса Counter, для которого кажется, что он не имеет даже функциональности класса-оболочки Integer. Почему не использовать int или Integer? Хорошо, мы не можем использовать int потому, что все контейнеры могут хранить только ссылки на Object. После рассмотрения контейнеров классы-оболочки могли бы иметь для вас больше смысла, так как вы не можете поместить любой примитивный тип в контейнер. Однако есть только одна вещь, которую вы можете делать с оболочками в Java - это инициализация его определенным значением и чтение этого значения. То есть, нет способа изменить значение, как только оболочка будет создана. Это немедленно делает оболочку Integer бесполезной для решения нашей проблемы, так что мы вынуждены создавать новый класс, который удовлетворяет нашим требованиям.
