Идея хеш-таблицы заключается в том, что вы хотите эффективно реализовать структуру данных, называемую словарем.Словарь - это хранилище ключей / значений, т. Е. Вы хотите иметь возможность хранить определенные объекты под определенным ключом, а затем снова получать их, используя тот же ключ.
Один из наиболее эффективных способовДоступ к значениям - это сохранение их в массиве.Например, мы могли бы реализовать словарь, который использует целые числа для ключей и строки для значений, например:
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") в словаре.Ммм, но массив может хранить только 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 arЧлены класса верхнего уровня java.lang.Object и все другие классы наследуются от него.
Как видите, на самом деле не имеет значения, возвращают ли два разных объекта одинаковое значение в их hashCode() метод: вышеуказанный подход всегда будет работать!Но все же желательно, чтобы они возвращали разные значения, чтобы снизить вероятность коллизий хешей, вызванных h.Мы видели, что этого нельзя избежать на 100% в целом, но чем меньше мы получаем коллизий, тем эффективнее становится наша хеш-таблица.В худшем случае все ключи отображаются на один и тот же индекс массива: в этом случае все пары хранятся в одном списке, и поиск значения становится операцией с линейными затратами в размере хеш-таблицы.