Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Хеширование и хеш-коды

В предыдущем примере класс стандартной библиотеки (Integer) использовался в качестве ключа для HashMap. Он великолепно работает в качестве ключа, потому что он имеет все необходимые записи, чтобы корректно работать в качестве ключа. Но основные ловушки, случающиеся с HashMap, возникают тогда, когда вы создаете свой собственный класс для использования в качестве ключа. Например, рассмотрим систему прогнозирования погоды, которая ставит в соответствие объекты Groundhog с объектами Prediction. Это кажется достаточно просто: вы создаете два класса и используете Groundhog в качестве ключа, а Prediction в качестве значения:

//: c09:SpringDetector.java// выглядит правдоподобно, но не работает.import java.util.*; class Groundhog { int ghNumber; Groundhog(int n) { ghNumber = n; }} class Prediction { boolean shadow = Math.random() > 0.5; public String toString() { if(shadow) return "Six more weeks of Winter!"; else return "Early Spring!"; }} public class SpringDetector { public static void main(String[] args) { HashMap hm = new HashMap(); for(int i = 0; i < 10; i++) hm.put(new Groundhog(i), new Prediction()); System.out.println("hm = " + hm + "\n"); System.out.println("Looking up prediction for Groundhog #3:"); Groundhog gh = new Groundhog(3); if(hm.containsKey(gh)) System.out.println((Prediction)hm.get(gh)); else System.out.println("Key not found: " + gh); }} ///:~

Каждому Groundhog дан идентификационный номер, так что вы можете искать Prediction в HashMap, говоря: “Дайте мне Prediction, ассоциированный с Groundhog под номером 3”. Класс Prediction содержит boolean, который инициализируется с использованием Math.random(), и toString(), который интерпретирует результат для вас. В main() заполняется HashMap с помощью Groundhog и ассоциированными Prediction. HashMap печатается, так что вы можете видеть, как он заполнен. Затем Groundhog с идентификационным номером 3 используется в качестве ключа для поиска прогноза для Groundhog №3 (который, как вы видите, должен быть в Map).

Это выглядит достаточным, но это не работает. Проблема в том, что Groundhog наследуется от общего корневого класса Object (что происходит в том случае, когда вы не указываете базовый класс, так как все классы наследуются от Object). Этот метод hashCode() класса Object используется для генерации хеш кода для каждого объекта, а по умолчанию он просто использует адрес этого объекта. Таким образом, первый экземпляр Groundhog(3) не производит хеш код, равный хеш коду для второго экземпляра Groundhog(3) который мы пробуем использовать для поиска.

Вы можете подумать, что все, что вам нужно сделать, это написать соответствующую перегрузку для hashCode(). Но это все равно не будет работать, пока вы не сделаете еще одну вещь: перегрузка метода equals(), который тоже является частью Object. Этот метод используется HashMap когда происходит попытка определить, что ваш ключ равен ключу из таблицы. Опять таки, по умолчанию Object.equals() просто сравнивает адреса объектов, так что один Groundhog(3) не равен другому Groundhog(3).

Таким образом, для использования вашего собственного класса в качестве ключа в HashMap, вы должны перегрузить и hashCode(), и equals(), как показано в следующем решении возникшей выше проблемы:

//: c09:SpringDetector2.java// Класс, который используется в качестве ключа в HashMap,// должен перегружать hashCode() и equals().import java.util.*; class Groundhog2 { int ghNumber; Groundhog2(int n) { ghNumber = n; } public int hashCode() { return ghNumber; } public boolean equals(Object o) { return (o instanceof Groundhog2) && (ghNumber == ((Groundhog2)o).ghNumber); }} public class SpringDetector2 { public static void main(String[] args) { HashMap hm = new HashMap(); for(int i = 0; i < 10; i++) hm.put(new Groundhog2(i),new Prediction()); System.out.println("hm = " + hm + "\n"); System.out.println("Looking up prediction for groundhog #3:"); Groundhog2 gh = new Groundhog2(3); if(hm.containsKey(gh)) System.out.println((Prediction)hm.get(gh)); }} ///:~

Обратите внимание, что здесь используется класс Prediction из предыдущего примера, так что SpringDetector.java должен быть откомпилирован первым или вы получите ошибку времени компиляции, когда попробуете откомпилировать SpringDetector2.java.

Groundhog2.hashCode() возвращает номер groundhog в качестве идентификатора. В этом примере программист отвечает за то, что не будет существовать два одинаковых groundhog с одним и тем же идентификационным номером. hashCode() не требует возврата уникального идентификатора (кое-что вы поймете лучше позднее в этой главе), но метод equals() должен быть способен точно определить равны два объекта или нет.

Даже притом, что метод equals() только проверяет, является ли аргумент экземпляром Groundhog2 (использование ключевого слова instanceof будет полностью объяснено в Главе 12), instanceof на самом деле спокойно выполняет вторую необходимую проверку, проверяет, что объект - это не null, так как instanceof производит false, если левый аргумент - это null. Принимая это во внимание, получаем, что необходимо соответствие типов и не null, сравнение основывается на реальных ghNumber. Когда вы запустите программу, вы увидите что получаете на выходе правильный результат.

Когда создаете ваши собственные класса для использования в HashSet, вы должны уделять внимание тем же проблемам, что и при использовании в качестве ключей в HashMap.

Понимание 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 может быть протестирован путем заполнения его значениями и распечатыванием их.




Дата добавления: 2015-09-11; просмотров: 22 | Поможем написать вашу работу | Нарушение авторских прав

Поиск в отсортированном массиве | Введение в контейнеры | Распечатка контейнера | Заполнение контейнеров | Неудобство контейнеров: неизвестный тип | Итераторы | Таксономия контейнера | Функциональность Collection | Функциональность List | Функциональность Set |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.01 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав