Эта статья является первой подписанной статьей сообщества Nuggets, и ее перепечатка без разрешения запрещена.
Хеш-таблица и, наконец, давно назревшая.
В этой статье объясняется концепция структуры данных хеш-таблицы и объясняется разница между ней и обычной хеш-таблицей с Hashmap, и, наконец, простой хеш-таблицей, написанной от руки.
Таким образом, я надеюсь, что благодаря этой статье читатели смогут получить четкое представление о хеш-таблицах, особенно в процессе собеседования по Java, вопросы, связанные с HashMap, почти всегда задаются на каждой встрече. действительно трудно понять HashMap в корне.
В дополнение к интервью, после того как вы освоите хеш-таблицу, вы также можете переписать хеш-функцию в соответствии с потребностями сценария приложения, чтобы обеспечить более равномерное распределение хэша в вашем сценарии приложения.
Обзор этой статьи выглядит следующим образом:
1. Хэш-таблица
хеш-таблица(Хеш-таблица, также называемая хеш-таблицей), доступ к которой осуществляется напрямую в соответствии со значением ключа (значением ключа)структура данных. То есть он обращается к записям, сопоставляя значение ключа с местоположением в таблице, чтобы ускорить поиск. Эта функция отображения называетсяхэш-функция, ведение записеймножествоназываетсяхеш-таблица.
Хэш как очень распространенная структура данных поиска, он может выполнять поиск данных с временной сложностью O (1).
Например, у меня есть коллекция со следующими данными, и я хочу быстро узнать, есть ли данные в этой коллекции, что мне делать?
В общем, обход можно использовать, но если объем данных слишком велик, стоимость каждого обхода будет неприемлемой.
Затем, если они упорядочены, вы можете использовать древовидную структуру данных для бинарного поиска, что очень эффективно, но, к сожалению, наши данные неупорядочены.
Вот кто-то придумал очень хитрый способ его найти, то есть вычислить искомые данные (далее ключ) для получения значения индекса массива, а затем поместить это значение в соответствующий массив.
В дальнейшем мы будем вычислять ключ каждый раз, когда ищем его, чтобы получить значение индекса массива, а затем получать данные, соответствующие массиву, через индекс, и мы можем знать, существует ли он в массиве.
Структура данных такого рода поиска данных называется хеш-таблицей, а метод вычисления ключа — хеш-функцией.
В Java классом типичной структуры данных Hash является HashMap.
Давайте рассмотрим шаги выполнения хеш-таблицы:
-
Выполните вычисление хеш-функции для ключа, чтобы получить значение хеш-функции.
-
Вычислите хеш-значение, чтобы получить индекс массива.
-
Получите соответствующий массив в массиве, подписав массив.
Поскольку шаги поиска в хеш-таблице и хеш-функции постоянны, временная сложность хеш-таблицы составляет O (1).
2. Хеш-функция
Хеш-функция — это алгоритм извлечения признаков данных. Существуют разные хэш-алгоритмы для разных форм данных, поэтому хеш-функции не универсальны. Существует много разных хеш-алгоритмов для разных сценариев. Например, наш общий MD5 — это хэш-алгоритм A для получения дайджест файловой информации.
Другой пример: в Java для часто используемых типов данных JDK реализует множество различных хеш-функций.
Целое:
public static int hashCode(int value) {
return value;
}
Хэш-функция Integer предназначена для прямого получения значения.
Нить:
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
hash = h = isLatin1() ? StringLatin1.hashCode(value)
: StringUTF16.hashCode(value);
}
return h;
}
Для строкового типа используйте алгоритм:s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1].
Двойной:
public static int hashCode(double value) {
long bits = doubleToLongBits(value);
return (int)(bits ^ (bits >>> 32));
}
Типы с плавающей запятой хешируются с помощью побитовых операций.
Читатели могут задаться вопросом, почему для такого количества структур данных реализованы разные методы расчета хэшей, что в основном необходимо для единообразия значений хеш-функции.
Чем равномернее хеш-значение, тем лучше дизайн хеш-функции и меньше хеш-коллизий, о хеш-коллизиях мы поговорим в следующем разделе.
В первом разделе я сказал, что помимо вычисления хэш-значения нам также необходимо вычислить позицию массива.
Есть много способов вычислить расположение массива, здесь я введу относительно простое остаточное число:
я предполагаю中国人Вычислите этот ключ и получите хеш-значение: 19942986, затем я буду использовать это число, чтобы взять остаток от размера массива.Здесь я предполагаю, что размер моего массива равен 11, и я получаю эту формулу:
19942986 % 11 = 8
Тогда мы получаем, что результатом этой хэш-функции является индекс массива 8, и мы можем положить中国人Эта строка помещается в индекс 8 массива.
Поскольку ожидается, что вычисление хеш-значения будет максимально однородным, существуют ли аналогичные требования для индексов массива?
На самом деле существует такой, как описанный выше метод деления и оставления остатка.В методе деления и оставления остатка выбор размера массива сильно повлияет на то, будет ли результат взятия остатка четным, поэтому в метод деления и оставления остатка, мы обычно используем простые числа, поэтому HashTable Инициализированный размер равен 11, потому что 11 является простым числом.
3. Столкновение хэшей
После предыдущего исследования я считаю, что у всех есть четкое понимание соответствующих концепций хеш-таблицы, поэтому в этом разделе будет изучен основной момент хеш-таблицы: коллизия хэшей.
Коллизия хэшей — это когда несколько разных ключей хэшируются в одну и ту же позицию нижнего индекса массива.Случай следующий:
На приведенном выше рисунке耳、朵、不Нижние индексы массива этих трех слов после хеширования равны 0, и, поскольку они представляют собой три разных значения, их нельзя напрямую перезаписать в массиве, поэтому нам нужен способ хранения этих трех значений.
Здесь будут представлены два общих метода:开放地址法и链地址法.
Метод открытых адресов является относительно простым методом разрешения конфликтов, и его принцип очень прост:
во-первых耳После того, как слово заняло индекс 0, второе朵Слово ищет свободный нижний индекс в обратном направлении и устанавливает себя после его нахождения, поэтому朵слово находится в нижнем индексе 1, и不Слово находится в нижнем индексе 2.
В соответствии с различными способами поиска индексов метод открытого адреса можно разделить на следующие типы:
-
Линейный метод обнаружения: после того, как нижний индекс занят, выполните последовательный поиск в обратном направлении с размером шага 1. Этот метод я использую в приведенном выше примере.
-
Вторичный метод обнаружения: после того, как нижний индекс занят, размер шага кратен 2, и поиск выполняется в обратном порядке по очереди.
-
Метод псевдослучайного обнаружения: после того, как нижний индекс занят, случайно генерируется число, а затем это число используется в качестве нижнего индекса для его поиска.Этот метод полностью зависит от воли Бога.
На самом деле принципы одинаковые, все ищут пустой индекс назад на основе текущего индекса, но размер шага разный.
Метод цепных адресов, широко известный как метод застежки-молнии, заключается в поддержании связанного списка в конфликтующих элементах нижнего индекса, и все конфликтующие элементы помещаются в этот связанный список по очереди:
На приведенном выше рисунке я расположил два конфликтующих ключа в связанном списке по порядку. В следующий раз, когда я буду искать его, мне нужно будет только просмотреть элементы массива и пройтись по связанному списку. Этот метод используется в HashMap в Java. разрешать коллизии хешей.
С вышеуказанными двумя способами, вероятно, увеличит конфликт, что приводит к тому, что эффективность эффективности становится низким, поэтому нет идеального решения, не может решить проблему хэш-столкновений, я обычно рекомендую использовать Zip-метод, потому что это относительно простое и легко понять.
4. Дело HashMap
HashMap много упоминался в предыдущей статье, в этом разделе мы разберем некоторые ключевые моменты в HashMap, которые отличаются от описанных выше.
Во-первых, это емкость таблицы HashMap, Емкость таблицы — это количество элементов, которые можно загрузить в эту хеш-таблицу.
Как я уже говорил ранее, лучше всего использовать простые числа в качестве емкости таблицы в хеш-таблице, и я также взял HashTable в качестве примера.
В HashMap его начальная емкость равна 16, что является не только четным числом, но и кратным 2.
Причина, по которой HashMap использует в качестве емкости не простое число, а кратное 2, заключается в том, что он не использует метод деления и остатка при вычислении нижнего индекса массива, а использует битовую операцию для вычисления нижнего индекса массива.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
После вычисления хеш-значения выполняется битовая операция с использованием хеш-значения и длины массива:(tab.length - 1) & hash.
5. Рукописная хеш-таблица
Поняв приведенные выше знания о хэшах, вы можете самостоятельно написать структуру данных, аналогичную hashMap.
Прежде всего, давайте подумаем о необходимых условиях для создания хеш-таблицы:
-
хэш-функция
-
Метод столкновения хешей
Просто помните об этих двух моментах и напишите структуру данных, отвечающую требованиям:
public class DiyHashMap{
private Object[] tables;
private int size;
public DiyHashMap() {
size = 11;
tables = new Object[size];
}
public Object get(String key) {
int index = hash(key) % size;
if (tables[index] == null) {
return null;
} else {
return tables[index];
}
}
public void put(String key, Object obj) {
int index = hash(key) % size;
tables[index] = obj;
}
private int hash(String key) {
int hash = 0;
for (int i = 0; i < key.length(); i++) {
hash = hash + (key.charAt(i) * 31 + i);
}
return hash;
}
}
В моем примере строка используется в качестве ключа таблицы HASH, а функция HASH просто умножается на 31 и добавляется вместе. Возвращаемое значение здесь - это тип int, поэтому максимальное значение хеса составляет 32 бита.,
На этапе отображения хэша я использовал упомянутый выше метод деления и остатка, а размер таблицы был установлен равным простому числу: 11.
В дополнение к ним, есть два пункта, которые могут быть расширены:
-
Таблица может быть расширена, а размер расширения может быть удвоен и +1, чтобы сделать его простым числом, насколько это возможно.
-
Чтобы использовать метод застежки-молнии для разрешения конфликтов, мой текущий подход состоит в том, чтобы перезаписать его напрямую.Используя метод застежки-молнии, массив объектов таблицы можно заменить массивом других абстрактных типов данных, а также можно добавить дополнительную ссылку на двусвязный список. добавлен.
6. Заключение
Ну, вышеизложенное - это все содержание хэш-стола, конечно, хэш также имеет недостатки:
-
Слишком много коллизий хешей может привести к тому, что частичный поиск будет линейным.
-
Поиск диапазона невозможен.
Что касается первого недостатка, то при обычном использовании не будет слишком много конфликтов, а в Java, если конфликтов будет слишком много, она будет автоматически преобразована в красно-черную древовидную структуру данных.
Что касается второго недостатка, то это неизбежный недостаток хэш-таблицы.При требовании поиска по диапазону древовидная структура данных может лучше учитывать поиск по диапазону и экспоненциальную скорость.
Конечно, скорости хеш-таблицы хватает, чтобы скрыть многие недостатки.Она используется во многих приложениях.Например, redis сам по себе является большой хеш-таблицей, а индекс в базе данных часто имеет вариант хеш-индекса, т.к. а также регистрация операционной системы.Быстрый поиск, таких как таблицы, будет использовать структуру данных хеш-таблицы, точно так же, как белое покрытие сто уродство, хэш, до тех пор, как это достаточно быстро. Наконец, если эта статья будет полезна для всех, я надеюсь, что вы, не колеблясь, поставите лайк, соберете и подпишитесь. Ваша поддержка — моя непрекращающаяся мотивация. Увидимся в следующей статье.