Понимание hashCode( )
Приведенный выше пример - это только первый шаг на пути правильного решения проблемы. Он показывает, что если вы не перегрузите hashCode( ) и equals( ) для вашего ключа, хешируемые структуры данных (HashSet или HashMap) не будут способны иметь дело с вашими ключами. Однако для получения хорошего решения проблемы вам необходимо понимать, что происходит внутри хешируемой структуры данных.
Во-первых, рассмотрим мотивацию хеширования: вы хотите искать объект, используя другой объект. Но вы также можете выполнить это с помощью TreeSet или TreeMap. Также возможно реализовать свой собственный Map. Для этого должен прилагаться метод Map.entrySet( ), для производства множества объектов Map.Entry. MPair будет определен как новый тип Map.Entry. Для правильной работы при помещении в TreeSet должен быть реализован метод equals( ) и должен быть Comparable:
//: c09:MPair.java
// Map реализованный с помощью ArrayLists.
import java.util.*;
public class MPair implements Map.Entry, Comparable { Object key, value; MPair(Object k, Object v) { key = k; value = v; } public Object getKey() { return key; } public Object getValue() { return value; } public Object setValue(Object v){ Object result = value; value = v; return result; } public boolean equals(Object o) { return key.equals(((MPair)o).key); } public int compareTo(Object rv) { return ((Comparable)key).compareTo( ((MPair)rv).key); } } ///:~
Обратите внимание, что сравнение интересует только для ключей, так что допустимы дублирующие значения.
Приведенный пример реализует Map, используя пары из ArrayList:
//: c09:SlowMap.java
// A Map implemented with ArrayLists.
import java.util.*; import com.bruceeckel.util.*;
public class SlowMap extends AbstractMap { private ArrayList keys = new ArrayList(), values = new ArrayList(); public Object put(Object key, Object value) { Object result = get(key); if(!keys.contains(key)) { keys.add(key); values.add(value); } else
values.set(keys.indexOf(key), value); return result; } public Object get(Object key) { if(!keys.contains(key)) return null; return values.get(keys.indexOf(key)); } public Set entrySet() { Set entries = new HashSet(); Iterator ki = keys.iterator(), vi = values.iterator(); while(ki.hasNext()) entries.add(new MPair(ki.next(), vi.next())); return entries; } public static void main(String[] args) { SlowMap m = new SlowMap(); Collections2.fill(m, Collections2.geography, 25); System.out.println(m); } } ///:~
Метод put( ) просто помещает ключ и значение в соответствующий ArrayList. В main( ) загружается SlowMap, а затем печатается так же медленно, как и работает.
Это показывает, что не так сложно произвести новый тип Map. Но как подсказывает имя, SlowMap не является быстрым, так что вы, вероятно, не будите использовать его, если вы имеете альтернативные варианты. Проблема заключается в поиске ключа: здесь нет упорядочивания, поэтому используется простой линейный поиск, являющийся самым медленным способом поиска.
Главное преимущество хеширования - скорость: хеширование позволяет искать исключительно быстро. Так как узкое место в скорости поиска ключа, одно из решений проблемы может быть в хранении ключей в отсортированном порядке и использование Collections.binarySearch( ) для выполнения поиска (упражнения в конце этой главы проведут вас по этому процессу).
Хеширование идет дальше, говоря, что все, что вы хотите делать - это хранить ключи где угодно так, чтобы они могли быть быстро найдены. Как вы увидите в этой главе, самая быстрая структура, в которой хранится группа элементов - это массив, который будет использован для представления информации о ключах (обратите особое внимание, что я сказал “ключевой информации”, а не самих ключей). Также вы увидите в этой главе, что однажды выделенный массив не может изменить размер, так что мы имеем проблему: мы хотим быть способны хранить любое число значений в Map, но если число ключей фиксировано размером массива, как мы это можем сделать?
Ответ заключается в том, что массив не хранит ключи. Из объекта ключа получается число, которое будет индексироваться в массиве. Это число является хеш кодом, производимым методом hashCode( ) (на научном компьютерном языке - это хеш-функция), определенном в Object и, предположительно, перегруженная вашим классом. Для решения проблемы фиксированного размера массива: один и тот же индекс может производиться разными ключами. То есть, здесь могут быть коллизии. Поэтому, не имеет значения, насколько велик массив, потому что каждый объект ключа будет пребывать где-то в этом массиве.
Таким образом, процесс поиска значения начинается с подсчета хеш кода и использовании его в качестве индекса в массиве. Если вы можете гарантировать, что не будет коллизий (которые возможны из-за фиксированного числа значений), то вы имеете точную функцию хеширования, но это особый случай. Во всех остальных случаях коллизии обрабатываются внешней привязкой: массив не прямо указывает на значение, а вместо этого указывает на список значений. Эти значения ищутся линейным способом, с помощью метода equals( ). Конечно эта сторона замедляет поиск, но если у вас хорошая функция хеширования, то в большинстве случаев будет лишь несколько значений в каждой ячейке. Так что вместо поиска во всем списке вы быстро перепрыгиваете на ячейку, в которой лишь несколько включений для нахождения значения. Это намного быстрее, поэтому HashMap такой быстрый.
Зная основы хеширования, можно реализовать простой хешированный класс Map:
//: c09:SimpleHashMap.java
// Демонстрация хешированного Map.
import java.util.*; import com.bruceeckel.util.*;
public class SimpleHashMap extends AbstractMap { // Выбираем главное число размера хеш-таблицы
// для получения равномерного распределения:
private final static int SZ = 997; private LinkedList[] bucket= new LinkedList[SZ]; public Object put(Object key, Object value) { Object result = null; int index = key.hashCode() % SZ; if(index < 0) index = -index; if(bucket[index] == null) bucket[index] = new LinkedList(); LinkedList pairs = bucket[index]; MPair pair = new MPair(key, value); ListIterator it = pairs.listIterator(); boolean found = false; while(it.hasNext()) { Object iPair = it.next(); if(iPair.equals(pair)) { result = ((MPair)iPair).getValue(); it.set(pair); // Замена старого новым
found = true; break; } } if(!found) bucket[index].add(pair); return result; } public Object get(Object key) { int index = key.hashCode() % SZ; if(index < 0) index = -index; if(bucket[index] == null) return null; LinkedList pairs = bucket[index]; MPair match = new MPair(key, null); ListIterator it = pairs.listIterator(); while(it.hasNext()) { Object iPair = it.next(); if(iPair.equals(match)) return ((MPair)iPair).getValue(); } return null; } public Set entrySet() { Set entries = new HashSet(); for(int i = 0; i < bucket.length; i++) { if(bucket[i] == null) continue; Iterator it = bucket[i].iterator(); while(it.hasNext()) entries.add(it.next()); } return entries; } public static void main(String[] args) { SimpleHashMap m = new SimpleHashMap(); Collections2.fill(m, Collections2.geography, 25); System.out.println(m); } } ///:~
Так как “ячейки” в хеш- таблице часто называются ковшом, массив, который на самом деле представляет таблицу, называется bucket. Для обеспечения лучшего распределения, число ковшей обычно является простым числом. Обратите внимание, что это массив типа LinkedList, который автоматически обеспечивает механизм для коллизий: каждый новый элемент он просто добавляет в конец списка.
Возвращаемое значение для put( ) - это null, если ключ уже есть в списке и старое значение уже ассоциировано с этим ключом. Возвращаемое значение равно result, которое инициализируется значением null, но если ключ обнаружен в списке, но этот ключ присваивается result.
Для put( ) и get( ) первое, что выполняется - это вызов hashCode( ) для ключа, а результат ограничивается положительными значениями. Затем он ограничивается размерами массива bucket с помощью оператора остатка от деления. Если это место - null, это означает, что нет элементов предназначенных для этого места, поэтому создается новый LinkedList для хранения полученного объекта. Однако нормальный процесс поиска проверяет есть ли дубликаты, и если они есть, старое значение помещается в result, а новое значение замещает старое. Флаг found хранит информацию о том, была ли найдена старая пара ключ-значение и, если нет, новая пара добавляется в конец списка.
В get( ) вы увидите очень похожий код, что и в put( ), но упрощенный. Рассчитывается индекс для массива bucket, и если существует LinkedList, происходит поиск до совпадения.
entrySet( ) должен находить и обходить все списки, добавляя их в результирующий Set. Как только этот метод был создан, Map может быть протестирован путем заполнения его значениями и распечатыванием их.
