предисловие

Эта статья включена в альбом:dwz.win/HjK, нажмите, чтобы получить дополнительные знания о структурах данных и алгоритмах.

Здравствуйте, меня зовут Тонг.

В предыдущем разделе мы вместе узнали, как построить высокопроизводительную очередь на Java, что требует большого количества базовых знаний.Не знаю, сколько вы можете получить? !

В этом разделе я хочу вслед за вами заново узнать все о хэшах — хешах, хеш-функциях, хеш-таблицах.

Какая любовь и ненависть у этих троих?

Почему класс Object должен иметь метод hashCode()? Какое это имеет отношение к методу equals()?

Как написать высокопроизводительную хеш-таблицу?

Можно ли заменить красно-черное дерево в HashMap на Java другими структурами данных?

Что такое хэш?

Хэш относится к вводу любой длины по определенному алгоритму ввывод фиксированной длиныПроцесс, этот вывод называется хэш-значением или хэш-кодом, этот алгоритм называется хэш-алгоритмом или хеш-функцией, этот процесс обычно называется хэшем или вычислением хэша, хеш в переводе на китайский язык имеет хеш, хэш, хэш и т. д.

Поскольку это выход фиксированной длины, это означает, что ввод бесконечен, а вывод ограничен.Неизбежно, что разные входы могут получить один и тот же вывод.Поэтому алгоритм хеширования, как правило, необратим.

Итак, каковы применения алгоритма Hash?

Назначение хеш-алгоритма

Алгоритм хеширования является обобщенным алгоритмом или своего рода идеей. У него нет фиксированной формулы. Пока алгоритм, определенный выше, удовлетворяется, его можно назвать алгоритмом хеширования.

Вообще говоря, он имеет следующие области применения:

Зашифруйте пароль, например, используйте MD5 + соль для шифрования пароля;
Быстрые запросы, например, использование хеш-таблиц, которые позволяют быстро запрашивать элементы через хэш-таблицы;
Цифровые подписи, такие как межсистемные вызовы плюс подписи, могут предотвратить подделку данных;
Проверка файлов, например, при загрузке игр Tencent обычно используется значение MD5.После загрузки установочного пакета значение MD5 вычисляется и сравнивается с официальным значением MD5, чтобы вы могли узнать, поврежден файл или нет. в процессе загрузки, вмешательстве и т. д.;

Что ж, говоря об алгоритме хеширования или хеш-функции, в Java родительский класс Object всех объектов имеет хеш-функцию, метод hashCode() Почему класс Object должен определять такой метод?

Строго говоря, хеш-алгоритм и хэш-функция все же немного отличаются, и я думаю, что вы можете различить их в зависимости от контекста.

Давайте посмотрим, что говорят комментарии в исходном коде JDK:

Обратите внимание на красную рамку.Грубый перевод: вернуть значение хэша для этого объекта, которое существует для лучшей поддержки хеш-таблиц, таких как HashMap. Проще говоря, этот метод используется для хеш-таблиц, таких как HashMap.

// 默认返回的是对象的内部地址
public native int hashCode();

На этом этапе мы должны упомянуть еще один метод класса Object — equals().

// 默认是直接比较两个对象的地址是否相等
public boolean equals(Object obj) {
    return (this == obj);
}

В чем запутанность между hashCode() и equals?

Вообще говоря, hashCode() можно рассматривать как слабое сравнение, возвращаясь к сути Hash и сопоставляя различные входные данные с выходными данными фиксированной длины, тогда могут возникнуть следующие ситуации:

Вход тот же, выход должен быть таким же;
Вход может быть другим, выход может быть таким же или другим;
Выход тот же, вход может быть, а может и не быть;
Выход другой, вход должен быть другим;

И equals() — это метод, строго сравнивающий, равны ли два объекта, поэтому, если два объекта equals() истинны, то их hashCode() должен быть равен, что, если они не равны?

Если equals() возвращает true, но hashCode() не равен, то представьте, что эти два объекта используются в качестве ключей HashMap, они, скорее всего, будут расположены в разных слотах HashMap, и HashMap будет вставлен в это время. Два одинаковых объекта не допускаются, поэтому, если вы переопределяете метод equals(), вы должны переопределять метод hashCode().

Например, все мы знаем, что в классе String его метод equals() сравнивает на равенство содержимое двух строк, а не адреса двух строк.Вот его метод equals():

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = value.length;
        if (n == anotherString.value.length) {
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = 0;
            while (n-- != 0) {
                if (v1[i] != v2[i])
                    return false;
                i++;
            }
            return true;
        }
    }
    return false;
}

Итак, для следующих двух строковых объектов используйте equals(), чтобы сравнить их как равные, но их адреса памяти не совпадают:

String a = new String("123");
String b = new String("123");
System.out.println(a.equals(b)); // true
System.out.println(a == b); // false

В настоящее время, если метод hashCode() не переписан, то a и b будут возвращать разные хеш-коды, что создаст огромные помехи для нас при использовании String в качестве ключа HashMap.Поэтому метод hashCode(), переписанный String :

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

Этот алгоритм также очень прост и выражается формулой: s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1].

Что ж, поскольку хеш-таблица упоминается здесь много раз, давайте посмотрим, как шаг за шагом развивается хеш-таблица.

История развития хеш-таблицы

множество

Прежде чем говорить о хеш-таблицах, давайте взглянем на создателя структур данных — массивы.

Массив относительно прост, поэтому больше говорить не буду, всем все понятно, смотрите рисунок ниже.

Индекс массива обычно начинается с 0, а элементы хранятся последовательно, и то же самое верно для поиска указанного элемента.

Например, чтобы найти элемент 4, потребуется 3 поиска для поиска с самого начала.

ранняя хеш-таблица

Недостатки массива рассмотрены выше: чтобы найти элемент, можно искать элементы только с начала или с конца до тех пор, пока он не совпадет, а его время равновесия сложное O(n).

Итак, есть ли способ быстро найти элементы с помощью массива?

Умные братья-программисты придумали способ вычислить значение элемента с помощью хэш-функции и использовать это значение для определения положения элемента в массиве, чтобы можно было сократить временную сложность до O(1).

Например, если есть 5 элементов 3, 5, 4 и 1, позиции вычисляются с помощью хеш-функции перед помещением их в массив, и они размещаются точно, а не располагаются последовательно, как в простом массиве ( на основе индекса вместо значения элемента), чтобы найти местоположение).

Если длина примененного здесь массива равна 8, мы можем создать такую хеш-функцию, как hash(x) = x % 8, тогда конечным элементом станет следующее изображение:

В это время мы ищем элемент 4 и сначала вычисляем его хэш-значение как hash(4) = 4 % 8 = 4, поэтому вы можете напрямую вернуть элемент в позиции 4.

Развитая хеш-таблица

Все выглядит идеально, но когда приходит элемент 13, его нужно вставить в хеш-таблицу, и его хеш-значение вычисляется как хеш(13) = 13 % 8 = 5, Нани, его расчетная позиция также равна 5 , но Нет .5 был занят первым, что мне делать?

Этохэш-коллизия.

Почему возникают коллизии хэшей?

Поскольку массив, к которому мы обращаемся, имеет конечную длину, сопоставление бесконечного числа с конечным массивом рано или поздно приведет к конфликту, то есть несколько элементов сопоставляются с одной и той же позицией.

Что ж, теперь, когда есть коллизия хэшей, нам нужно ее решить, мы должны!

Как?

Линейный метод обнаружения

Поскольку у позиции 5 уже есть владелец, то я допускаю элемент 13, передвигаюсь на одну позицию назад и перехожу к позиции 6. Это метод линейного обнаружения. найдена свободная позиция. .

Однако есть новый элемент 12, и его хеш-значение равно хэш(12) = 12 % 8 = 4, что? Таким образом, вам нужно 3 раза вернуться на 7-ю позицию, чтобы иметь свободную позицию, что приводит к низкой эффективности вставки элементов, и поиск такой же.4-я позиция, расположенная первой, это не то, что я ищу , а затем двигайтесь назад, пока не найдете позицию номер 7.

вторичный метод обнаружения

Использование линейного метода обнаружения имеет большой недостаток.Конфликтующие элементы имеют свойство накапливаться.Например,поставьте 12-й в 7-ю позицию,и тогда 14-й будет такой же конфликтный,и тогда массив заканчивается,а дальше начинаются с 7-й позиции В позиции 0 вы обнаружите, что конфликтующие элементы сгруппированы, что не способствует поиску, а также не способствует вставке новых элементов.

В это время другой умный брат-программист придумал новую идею - второй метод обнаружения, когда возникает конфликт, я не прихожу находить пустые позиции по одной, а использую исходное значение хеша плюс i Квадратичная степень of , i из 1, 2, 3... таким образом, пока не будет найдена пустая позиция.

Взяв в качестве примера приведенный выше пример, вставив элемент 12, процесс выглядит следующим образом. Эта статья взята из исходного кода принцессы Тонг, читающей:

Это дает возможность быстро найти пустые места для размещения новых элементов, и не будет скопления конфликтующих элементов.

Но гусь, есть новый элемент 20, куда ты его денешь?

Я обнаружил, что я не мог поставить его в любом месте.

Исследования показали, что при использовании хеш-таблиц с квадратичным зондированием, когда размещено более половины элементов, возникают ситуации, когда новые элементы не могут найти свое место.

Поэтому вводится новое понятие - расширение.

Что такое расширение?

Когда размещенный элемент достигает x% от общей емкости, его необходимо расширить, этот x% также называетсякоэффициент расширения.

Очевидно, что чем больше коэффициент расширения, тем лучше, что указывает на то, что использование пространства хеш-таблицы выше.

Так что, к сожалению, квадратичный метод обнаружения не может удовлетворить нашу цель, коэффициент расширения слишком мал, всего 0,5, и половина места потрачена впустую.

В это время программистам пора использовать свои умные возможности.После мозгового штурма в 996 году они придумали новый метод реализации хеш-таблицы — метод связанного списка.

метод связанного списка

Разве это не просто разрешение конфликтов? Если есть конфликт, я не буду помещать его в массив.Я использую связанный список, чтобы соединить элементы в позиции нижнего индекса одного и того же массива, чтобы я мог полностью использовать пространство, ахахаха~~

Хе-хе-хе, идеально △△.

Действительно идеально, я хакер, я продолжаю помещать в него *%8=4 элемента, и тогда вы обнаружите, что почти все элементы попадают в один и тот же связанный список, ха, конечный результат - вы Хеш-таблица вырождается в связанную list, а эффективность запроса и вставки элементов стала O(n).

На данный момент, конечно, есть способ, что делает коэффициент расширения?

Например, если коэффициент расширения установлен равным 1, когда количество элементов достигает 8, расширение удваивается, половина элементов по-прежнему находится на 4-й позиции, а половина элементов — на 12-й позиции, что может облегчить давление на хеш-таблицу.

Тем не менее, гусь все еще не идеален, и он просто изменился с одного связанного списка на два связанных списка.Эта статья взята из исходного кода Princess Tong.

На этот раз умные братья-программисты начали мозговой штурм по взрослению 9127 и, наконец, придумали новую структуру — метод дерева связанных списков.

дерево связанных списков

Хотя приведенное выше расширение может решить некоторые проблемы, когда количество элементов относительно невелико, общая эффективность поиска и вставки не будет слишком низкой, поскольку количество элементов невелико.

Тем не менее, хакеры все еще атакуют, и количество элементов продолжает увеличиваться.Когда количество элементов увеличивается до определенной степени, эффективность поиска и вставки всегда будет особенно низкой.

Итак, другой способ мышления, поскольку эффективность связанного списка низкая, я его обновлю.Как насчет обновления до красно-черного дерева, когда связанный список длинный?

Ну, я вижу это, просто делай, что говоришь.

Что ж, неплохо, моя мама больше не боится, что меня атакуют хакеры.Эффективность запроса красно-черного дерева составляет O(log n), что намного выше, чем O(n) связанного списка.

Итак, это конец?

Если вы слишком много думаете, вам все равно придется перемещать половину элементов каждый раз, когда вы расширяетесь.Разве одно дерево разделено на два дерева?Это действительно хорошо?

Братья-программисты слишком сложны.После мозгового штурма 12127 на этот раз я, наконец, придумал новую вещь - согласованный хэш.

Согласованный хэш

Consistent Hash больше используется в распределенных системах. Например, кластер Redis развертывает четыре узла. Мы определяем все значения хэша как 0~2^32 и размещаем четверть элементов на каждом узле.

Это просто пример, принцип реального кластера Redis такой, а конкретное значение не такое.

На этом этапе предположим, что вам нужно добавить в Redis узел, например node5, и поместить его между узлами node3 и node4, чтобы вам нужно было только переместить элементы между node3 и node4 с node4 на node5, а остальные элементы остались неизменными.

Таким образом, скорость расширения увеличивается, а затронутые элементы относительно малы, и большинство запросов практически не осознаются.

Что ж, это все, что касается истории эволюции хеш-таблицы, у вас есть это?

постскриптум

В этом разделе мы заново изучили знания о хэше, хеш-функции и хеш-таблице вместе.В Java окончательная форма HashMap представлена в виде массива + связанный список + красно-черное дерево.

Говорят, что это красно-черное дерево можно заменить и другими структурами данных, например таблицей пропуска.

В следующем разделе поговоримпропустить столЭта структура данных, и используйте ее, чтобы переписать HashMap, чтобы получить последнюю рекламу, приходите и следуйте за мной!

Подпишитесь на «Tong Ge Read Source Code» владельца официальной учетной записи, чтобы разблокировать больше исходного кода, основ и знаний об архитектуре.