Ответ 3
Идея хэш-таблицы состоит в том, что вы хотите эффективно реализовать структуру данных, называемую словарем. Словарь - это хранилище ключей/значений, то есть вы хотите иметь возможность хранить определенные объекты под определенным ключом, а затем снова получать их с помощью одного и того же ключа.
Один из наиболее эффективных способов доступа к значениям - хранить их в массиве. Например, мы могли бы реализовать словарь, который использует целые числа для ключей и строк для таких значений:
String[] dictionary = new String[DICT_SIZE];
dictionary[15] = "Hello";
dictionary[121] = "world";
System.out.println(dictionary[15]); // prints "Hello"
К сожалению, этот подход не очень общий вообще: индекс массива должен быть целым значением, но в идеале мы хотели бы иметь возможность использовать произвольные объекты для наших ключей, а не только целые числа.
Теперь, чтобы решить эту задачу, нужно иметь способ сопоставления произвольных объектов с целыми значениями, которые мы могли бы использовать в качестве ключей для нашего массива. В Java это то, что делает hashCode(). Итак, теперь мы можем попытаться реализовать словарь String- > String:
String[] dictionary = new String[DICT_SIZE];
// "a" -> "Hello"
dictionary["a".hashCode()] = "Hello";
// "b" -> "world"
dictionary["b".hashCode()] = "world";
System.out.println(dictionary["b".hashCode()]); // prints world
Но эй, что, если есть какой-то объект, который мы хотели бы использовать в качестве ключа, но его метод hashCode возвращает значение, большее или равное DICT_SIZE? Тогда мы получим исключение ArrayIndexOutOfBoundsException, и это было бы нежелательно. Итак, позвольте просто сделать это как можно большим, не так ли?
public static final int DICT_SIZE = Integer.MAX_VALUE // Ooops!
Но это означало бы, что нам придется выделять гинеормные объемы памяти для нашего массива, даже если мы только намерены хранить несколько элементов. Так что это не может быть лучшим решением, и на самом деле мы можем сделать лучше. Предположим, что у нас была функция h, что для любого заданного DICT_SIZE отображает произвольные целые числа в диапазон [0, DICT_SIZE[. Затем мы могли бы просто применить h к тому, что возвращает метод hashCode() ключевого объекта, и быть уверенным, что мы остаемся в границах базового массива.
public static int h(int value, int DICT_SIZE) {
// returns an integer >= 0 and < DICT_SIZE for every value.
}
Эта функция называется хэш-функцией. Теперь мы можем адаптировать нашу реализацию словаря, чтобы избежать исключения ArrayIndexOutOfBoundsException:
// "a" -> "Hello"
dictionary[h("a".hashCode(), DICT_SIZE)] = "Hello"
// "b" -> "world"
dictionary[h("b".hashCode(), DICT_SIZE)] = "world"
Но это порождает еще одну проблему: что, если h отображает два разных ключевых индекса в одно и то же значение? Например:
int keyA = h("a".hashCode(), DICT_SIZE);
int keyB = h("b".hashCode(), DICT_SIZE);
может давать одинаковые значения для keyA и keyB, и в этом случае мы случайно перезаписали бы значение в нашем массиве:
// "a" -> "Hello"
dictionary[keyA] = "Hello";
// "b" -> "world"
dictionary[keyB] = "world"; // DAMN! This overwrites "Hello"!!
System.out.println(dictionary[keyA]); // prints "world"
Ну, вы можете сказать, тогда нам просто нужно убедиться, что мы реализуем h таким образом, что этого никогда не произойдет. К сожалению, это вообще невозможно. Рассмотрим следующий код:
for (int i = 0; i <= DICT_SIZE; i++) {
dictionary[h(i, DICT_SIZE)] = "dummy";
}
Этот цикл хранит значения DICT_SIZE + 1 (всегда то же самое значение, а именно String "dummy") в словаре. Mhh, но массив может хранить только DICT_SIZE разные записи! Это означает, что при использовании h мы должны перезаписать (по крайней мере) одну запись. Или, другими словами, h отобразит два разных ключа на одно и то же значение! Эти "столкновения" нельзя избежать: если n голубей попытаются войти в n-1 отверстия голубя, по крайней мере два из них должны войти в ту же дыру.
Но мы можем расширить нашу реализацию, чтобы массив мог хранить несколько значений под одним и тем же индексом. Это можно легко сделать, используя списки. Поэтому вместо использования:
String[] dictionary = new String[DICT_SIZE];
пишем:
List<String>[] dictionary = new List<String>[DICT_SIZE];
(Боковое замечание: обратите внимание, что Java не позволяет создавать массивы общих типов, поэтому приведенная выше строка не будет компилироваться, но вы получите идею).
Это изменит доступ к словарю следующим образом:
// "a" -> "Hello"
dictionary[h("a".hashCode(), DICT_SIZE)].add("Hello");
// "b" -> "world"
dictionary[h("b".hashCode(), DICT_SIZE)].add("world");
Если наша хешфункция h возвращает разные значения для всех наших ключей, это приведет к спискам только с одним элементом, а извлечение элементов очень просто:
System.out.println(dictionary[h("a".hashCode(), DICT_SIZE)].get(0)); // "Hello"
Но мы уже знаем, что в общем случае h иногда отображает разные ключи на одно и то же целое число. В этих случаях списки будут содержать более одного значения. Для поиска нам нужно пройти весь список, чтобы найти "правильное" значение, но как мы его узнаем?
Ну, вместо того, чтобы хранить только одно значение, мы всегда можем хранить полную (ключ, значение) пару в списках. Затем поиск будет выполняться в два этапа:
- Применить хэш-функцию для получения правильного списка из массива.
- Итерации через все пары, сохраненные в извлеченном списке: если пара с нужным ключом найдена, верните значение из пары.
Теперь добавление и извлечение стали настолько сложными, что неприлично относиться к отдельным методам для этих операций:
List<Pair<String,String>>[] dictionary = List<Pair<String,String>>[DICT_SIZE];
public void put(String key, String value) {
int hashCode = key.hashCode();
int arrayIndex = h(hashCode, DICT_SIZE);
List<Pair<String,String>> listAtIndex = dictionary[arrayIndex];
if (listAtIndex == null) {
listAtIndex = new LinkedList<Pair<Integer,String>>();
dictionary[arrayIndex] = listAtIndex;
}
for (Pair<String,String> previouslyAdded : listAtIndex) {
if (previouslyAdded.getValue().equals(value)) {
return; // the value is already in the dictionary;
}
}
listAtIndex.add(new Pair<String,String>(key, value));
}
public String get(String key) {
int hashCode = key.hashCode();
int arrayIndex = h(hashCode, DICT_SIZE);
List<Pair<String,String>> listAtIndex = dictionary[arrayIndex];
if (listAtIndex != null) {
for (Pair<String,String> previouslyAdded : listAtIndex) {
if (previouslyAdded.getKey().equals(key)) {
return previouslyAdded.getValue(); // entry found!
}
}
}
// entry not found
return null;
}
Итак, для того, чтобы этот подход работал, нам действительно нужны две операции сравнения: метод hashCode для поиска списка в массиве (это работает быстро, если hashCode() и h являются быстрыми) и equals, который нам нужен при просмотре списка.
Это общая идея хэширования, и вы узнаете метод put и get из java.util.Map.. Конечно, вышеупомянутая реализация является упрощением, но она должна проиллюстрировать суть всего этого.
Естественно, что этот подход не ограничивается строками, он работает для всех видов объектов, поскольку методы hashCode() и equals являются членами класса java.lang.Object верхнего уровня и всех других классов, наследуемых от что один.
Как вы можете видеть, на самом деле не имеет значения, возвращают ли два разных объекта одинаковое значение в свой метод hashCode(): этот подход всегда будет работать! Но все же желательно, чтобы они возвращали разные значения, чтобы снизить шансы на хэш-коллизии, вызванные h. Мы видели, что их нельзя избежать на 100% в целом, но чем меньше мы столкнемся, тем эффективнее становится наша хэш-таблица. В худшем случае все ключи сопоставляются с одним и тем же индексом массива: в этом случае все пары хранятся в одном списке, а поиск значения становится операцией с затратами, линейными по размеру хеш-таблицы.
