Это первая часть того, почему технологии72оригинальная статья

В чем проблема с хеш-конфликтом

Прежде чем официально начать эту статью, несколько слов, чтобы прояснить этот вопрос:Что такое конфликт хэшей, о котором мы часто говорим?

Сразу к предыдущей картинке:

Как вы думаете, что пришло вам на ум, когда вы увидели эту картину?

Вы когда-нибудь задумывались о структуре массива плюс связанный список HashMap?

Кстати, я здесь, чтобы использовать HashMap в качестве точки входа, чтобы рассказать вам о конфликтах Hash.

Затем смотрим на следующую картинку:

Допустим сейчас у нас есть ключ значение которого [почему технология].После алгоритма Hash расчетное значение равно 1, то смысл в том, что это значение должно быть размещено в том месте, где индекс массива равен 1.

Но как показано на рисунке, на месте, где стоит индекс 1, уже висело значение eat. Эта яма уже занята.

Тогда в этот момент,Мы называем это явление хэш-конфликтом.

Как HashMap разрешает конфликты хэшей?

Метод адресной цепочки, также известный как метод застежки-молнии.

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

Как используется связанный список? Посмотрите на картинку:

Эта проблема решается нами.

По сути, коллизия хэшей — это то же самое:Разные объекты получают один и тот же HashCode после прохождения одного и того же алгоритма Hash.

Поэтому, когда я писал это, я внезапно подумал о вопросе для интервью:

Могу я спросить, какая версия HashMap на изображении выше основана на JDK?

Почему вы подумали об этом вопросе интервью?

Потому что я колебался около 0,3 секунды, когда рисовал картинку.Когда я повесил ее на связанный список, должен ли я использовать метод вставки головы или метод вставки хвоста?

Как мы все знаем, HashMap в JDK 7 принимает метод вставки начала, то есть [почему технология] Прежде чем [съесть], HashMap в JDK 8 использует метод вставки хвоста.

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

Интервью, туда-сюда, не потёртое.

Построить строку, похожую на HashCode

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

Эта фраза звучит на первый взгляд: Ну, логично, так оно и есть, проблем нет.

Например, в нашем часто используемом HashMap ключ в большинстве случаев имеет тип String. Для возникновения конфликта Hash требуется как минимум два класса String с одинаковым HashCode.

Тогда я прошу вас:Как я могу быстро получить две строки с одним и тем же хэш-кодом?

Как ты, немного запутался?

Достаточно одного вопроса, чтобы перейти от многозначительного к легкому замешательству.

Приходите, позвольте мне показать вам волну анализа.

Позвольте мне сначала спросить вас: будут ли две разные строки длины 1, такие как следующий код, иметь одинаковый хэш-код?

String a = "a";
String b = "b";

Конечно нет, верно.

Если вы не знаете, я предлагаю вам перейти к коду ASCII, чтобы найти ответ.

Давайте посмотрим, будет ли строка длины 2 иметь тот же хэш-код?

Чтобы ответить на этот вопрос, мы должны сначала взглянуть на метод вычисления hashCode String, Здесь я беру JDK 8 в качестве примера:

Предположим, что эти две строки длины 2 равны xy и ab соответственно.

Обратите внимание, что xy и ab здесь являются заполнителями, а не строками.

Подобно неизвестным x и y в квадратном уравнении в учебниках для начальной школы, нам нужно ввести их в метод hashCode выше для вычисления.

Алгоритм hashCode, наиболее важным является цикл for.

Внутри цикла for есть три вещи, о которых мы не знаем: h, value.length и val[i]. Давайте отладим и посмотрим:

h изначально равно 0.

Базовая структура типа String — это массив символов, вы должны это знать.

Итак, value.length — это длина строки. val[] - это массив символов.

Поместите xy в цикл for, этот цикл for будет повторяться 2 раза.

Первый цикл: h=0, val[0]=x, поэтому h=31*0+x, то есть h=x.

Второй цикл: h=x, val[1]=y, поэтому h=31*x+y.

Итак, после расчета хэш-код xy равен 31 * x + y.

Точно так же хэш-код ab равен 31*a+b.

Поскольку мы хотим построить строки, подобные hashCode, мы получаем уравнение:

31x+y=31a+b

Тогда возникает вопрос: что такое x, y, a, b?

Вы можете понять это?

Вы можете считать молоток! Вы либо не хотите решать перестановки и комбинации на доске, либо просто не можете их решить.

Но я могу решить ее и показать вам, как решить эту проблему.

Начинается урок математики. Заметьте, я собираюсь деформироваться.

31x+y=31a+b можно преобразовать в:

31x-31а=б-у.

То есть 31(x-a)=b-y.

В этот момент все гораздо яснее, очевидно, что приведенное выше уравнение имеет особое решение:

х-а=1, Ь-у=31.

Потому что из вышесказанного получаем:Для любых двух строк xy и ab, если они удовлетворяют условиям xa=1, то есть значение кода ASCII первого символа отличается на 1, и в то же время удовлетворяют условиям by=31, то есть значению кода ASCII второго характер отличается на -31. Тогда хэш-код этих двух символов должен быть равен.

Уже так ясно было сказано, такое сочетание встречается против кодовой таблицы ASCII, не много ли?

Аа и ВВ, верно?

Ab и BC, не так ли?

Ac и BD, какие-нибудь?

В ПОРЯДКЕ. Теперь мы можем сгенерировать две строки с одним и тем же HashCode.

Мы немного углубляем сложность. Что делать, если я хочу создать более двух строк с одним и тем же HashCode?

Давайте сначала проанализируем его.

HashCode Aa и BB одинаковы. Если мы поместим их парами, разве это не будет то же самое?

Например: АаВВ, ВВАа.

как до меня"Шок! В ConcurrentHashMap тоже есть бесконечный цикл? 》Примеры, встречающиеся в этой статье, AaAa, BBBB:

Видите ли, произошло что-то волшебное.

Теперь у нас есть 4 строки с одинаковым хэш-кодом.

С этими 4 строками мы собираемся комбинировать с Aa, BB, например, AaBBAa, BBAaBB...

4*2=8 комбинаций, мы снова можем получить 8 строк с тем же hashCode.

Подождите, кажется, я нашел какую-то закономерность.

Если мы используем Aa и BB в качестве начальных данных, мы можем получить любое количество строк с одним и тем же хэш-кодом после нескольких перестановок и комбинаций. Длина строки увеличивается по мере увеличения числа.

Я до сих пор не знаю текста четко, просто покажу вам код напрямую, как показано ниже:

public class CreateHashCodeSomeUtil {

    /**
     * 种子数据：两个长度为 2 的 hashCode 一样的字符串
     */
    private static String[] SEED = new String[]{"Aa", "BB"};
    
    /**
     * 生成 2 的 n 次方个 HashCode 一样的字符串的集合
     */
    public static List<String> hashCodeSomeList(int n) {
        List<String> initList = new ArrayList<String>(Arrays.asList(SEED));
        for (int i = 1; i < n; i++) {
            initList = createByList(initList);
        }
        return initList;
    }

    public static List<String> createByList(List<String> list) {
        List<String> result = new ArrayList<String>();
        for (int i = 0; i < SEED.length; ++i) {
            for (String str : list) {
                result.add(SEED[i] + str);
            }
        }
        return result;
    }
}

С помощью приведенного выше кода мы можем сгенерировать любое количество строк с одним и тем же хэш-кодом.

нравится:

Итак, перестаньте задавать такие вопросы, как:

С этими строками с одинаковым hashCode мы помещаем эти строки в HashMap, код выглядит следующим образом:

public class HashMapTest {
    public static void main(String[] args) {
        Map<String, String> hashMap = new HashMap<String, String>();
        hashMap.put("Aa", "Aa");
        hashMap.put("BB", "BB");
        hashMap.put("AaAa", "AaAa");
        hashMap.put("AaBB", "AaBB");
        hashMap.put("BBAa", "BBAa");
        hashMap.put("BBBB", "BBBB");
        hashMap.put("AaAaAa", "AaAaAa");
        hashMap.put("AaAaBB", "AaAaBB");
        hashMap.put("AaBBAa", "AaBBAa");
        hashMap.put("AaBBBB", "AaBBBB");
        hashMap.put("BBAaAa", "BBAaAa");
        hashMap.put("BBAaBB", "BBAaBB");
        hashMap.put("BBBBAa", "BBBBAa");
        hashMap.put("BBBBBB", "BBBBBB");
    }
}

Наконец, длина этого HashMap будет увеличена вдвое. После расширения длина массива равна 64:

Но заняты в нем только три позиции, это места с нижними индексами 0, 31, 32:

Рисунок выглядит следующим образом:

Понимаете, шипы не волнуют, массив длиной 64, хранящий 14 данных, занимает всего 3 позиции.

Этот коэффициент использования пространства слишком низок.

Итак, это даже взлом HashMap.Поздравляем, вы освоили технику взлома: хеш-конфликт Dos.

Если вы хотите узнать больше. Прочтите эту статью Брата Стоуна:«Я не ожидал, что хэш-конфликт будет так разыгрываться. Ваша служба завербована? 》.

Глядя на картинку выше, я не знаю, с тобой что-то не так?

Если нет, то позвольте мне дать вам еще одну подсказку:Под позицией индекса массива 32 подвешен связанный список длиной 8.

Разве это не так, вдруг понял. В JDK 8, каков порог для связанного списка с деревом?

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

правильно?

Прямо молотком! Некоторые ученики несерьезны в классе, и они собьются с пути, если не будут осторожны.

это неправильно.Порог для преобразования связанного списка в красно-черное дерево — это когда количество узлов больше 8, а не когда оно равно 8.

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

Если вы мне не верите, позвольте мне показать вам, что это за узел сейчас:

Не врал тебе? На приведенном выше рисунке хорошо видно, что 8-й узел по-прежнему является обычным узлом.

А если это узел дерева, то он должен выглядеть так:

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

Так как же может выйти еще один конфликт?

В самом простом случае напишите:

Не будет ли еще одного конфликта? Я такой гений, я не могу не аплодировать себе.

Что ж, давайте посмотрим на текущий статус узла:

Как он стал TreeNode, я тебе солгал?

Кроме того, я хотел бы сказать еще одну вещь о яме вопроса интервью HashMap.

Интервьюер спросил:Каковы условия преобразования связанного списка HashMap JDK 8 в красно-черное дерево?

Большинство друзей, выучивших восьмичастное эссе в интервью, точно смогут ответить:Когда длина связанного списка больше 8.

Этот ответ правильный?

правильно, но только наполовину.

Другое условие заключается в том, что красно-черное дерево будет преобразовано только тогда, когда длина массива больше 64.

В исходниках четко написано, что длина массива меньше 64, поэтому его можно расширить напрямую, а не преобразовывать в красно-черное дерево:

Похоже, что многие игнорируют условие "длина массива больше 64".

Чтобы запомнить восьминогий текст, мне еще предстоит запомнить его весь.

Например, следующий тестовый пример:

Все они попадают в позицию с индексом 0 массива.

При попадании девятого элемента BBBBAa он попадет в метод treeifyBin, но не вызовет операцию древовидности, будет выполнена только операция расширения.

Поскольку текущая длина — это длина по умолчанию, равная 16. Не соответствует условиям преобразования красно-черного дерева.

Итак, на снимке экрана ниже мы видим, что там, где метка ①, длина массива стала 32, а длина связанного списка стала 9, но узел по-прежнему является обычным узлом:

Как насчет этого, это интересно, я думаю, что так интереснее изучать HashMap.

Класс сущности как ключ

В приведенном выше примере мы используем тип String в качестве ключа в HashMap.

Эта сцена покрывает 95% нашей сцены разработки.

Но иногда класс сущности может быть помещен в HashMap в качестве ключа.

Внимание, снова вопрос интервью:Можно ли использовать классы сущностей в качестве объектов в HashMap?

Это должно быть возможно. Но есть ямы, будьте осторожны, чтобы не наступить.

Позвольте мне привести вам пример из новости, которую я видел некоторое время назад:

Предположим, я хочу собрать информацию о семьях учеников и сохранить их в HashMap.

Тогда мой ключ — это объект студента, а значение — объект информации о семье студента.

Они следующие:

public class HomeInfo {

    private String homeAddr;
    private String carName;
     //省略改造方法和toString方法
}

public class Student {

    private String name;
    private Integer age;
     //省略改造方法和toString方法

}

Тогда наш тестовый случай выглядит следующим образом:

public class HashMapTest {

    private static Map<Student, HomeInfo> hashMap = new HashMap<Student, HomeInfo>();

    static {
        Student student = new Student("why", 7);
        HomeInfo homeInfo = new HomeInfo("大南街", "自行车");
        hashMap.put(student, homeInfo);
    }

    public static void main(String[] args) {
        updateInfo("why", 7, "滨江路", "摩托");
        for (Map.Entry<Student, HomeInfo> entry : hashMap.entrySet()) {
            System.out.println(entry.getKey()+"-"+entry.getValue());
        }
    }

    private static void updateInfo(String name, Integer age, String homeAddr, String carName) {
        Student student = new Student(name, age);
        HomeInfo homeInfo = hashMap.get(student);
        if (homeInfo == null) {
            hashMap.put(student, new HomeInfo(homeAddr, carName));
        }
    }
}

В исходном состоянии в HashMap уже есть 7-летний ребенок по имени почему, он живет на улице Да Нан, а транспортное средство дома — велосипед.

Затем, однажды, он сказал учителю, что переехал на Биньцзян-роуд и заменил велосипед дома на мотоцикл.

Таким образом, учитель изменил информацию о семье ребенка на странице.

Наконец, вызывается метод updateInfo.

Эй, угадай что?

Я покажу вам вывод:

После обновления двое 7-летних детей назвали, почему они появились в их классе: один живет на улице Данан, а другой на улице Бинцзян.

Обновление добавлено, вы говорите волшебное или нет?

Феномен вышел, так что в зависимости от явления, чтобы найти код проблемы не дело рук?

Очевидно, проблема кроется в этом месте:

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

Итак, давайте посмотрим, почему здесь пусто.

Следуйте исходному коду hashMap.get(), чтобы посмотреть:

Место, помеченное ①, является ключом вычисления, который является хэш-кодом объекта ученика. И наш объект студента не переопределяет hashCode, поэтому вызывается метод hashCode по умолчанию.

Студент здесь новый:

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

Следовательно, если метка равна ③, соответствующая позиция индекса массива вкладок, полученного после вычисления хэша, равна нулю. Не войдет в суждение if, здесь он возвращает null.

Тогда решение готово появиться:Просто переопределите метод hashCode объекта.

это?

Подожди, когда вернешься, не убегай с половиной. Я еще не закончил говорить.

Затем посмотрите исходный код:

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

Здесь мы не переопределили метод equals, поэтому он возвращает false.

Итак, если наши методы hashCode и equals не переопределены, появится следующая диаграмма:

Если мы перепишем hashCode, не переписывая метод equals, то появится следующая диаграмма:

Одним словом:В HashMap, если вы используете объект в качестве ключа, вы должны переопределить метод hashCode объекта и метод equals. В противном случае он не только не даст ожидаемого эффекта, но и может привести к переполнению памяти.

Например, в приведенном выше примере мы помещаем его в цикл, добавляем -Xmx10m к параметру запуска, и результат работы выглядит следующим образом:

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

Странные знания снова добавлены

Пока писал эту статью, пролистал книгу "Programming Ideas in Java (4th Edition)".

Strange Lore добавляет еще два.

Первый есть в этой книге, пример размещения объектов в HashMap такой:

Сурок: сурок, сурок.

Прогноз: прогноз, прогноз, прогноз.

Рассмотрим систему прогноза погоды, связывающую сурков с прогнозами.

Что за бессмертное требование эта ТМ, которую нельзя прочитать?

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

Вот что случилось.

В Пенсильвании, США, 2 февраля отмечается День сурка.

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

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

Таким образом, говорят, что спрос имеет смысл.

Второе странное знание заключается в следующем.

Что касается метода HashCode, «Идеи программирования на Java (4-е издание)» написано следующим образом:

Я сразу заметил, что что-то не так: результат=37*результат+c.

Как мы уже говорили ранее, базовое число должно быть 31, верно?

Автор сказал, что эта формула взята из книги "Эффективная Java (1-е издание)".

Обе эти книги являются Java-библиями.Я предлагаю вам поместить Dream Link в область сообщений.

«Эффективная Java (1-е издание)» настолько устарело, что у меня есть только физические книги для 2-го и 3-го изданий.

Поэтому я искал в Интернете первое издание электронной книги и, наконец, нашел соответствующее описание:

Видно, что формула, приведенная в книге, действительно рассчитана на основе 37.

Перелистал третье издание, там же, формула дана такая:

Более того, вы заходите в интернет искать: метод вычисления hashCode of String.

Все спорят, почему 31. Число 37 упоминается редко.

На самом деле, я предположил, что метод hashCode String должен был использовать 37 в более ранних версиях JDK, а позже был изменен на 31.

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

Почему в книге он был изменен с 37 на 31?

Вот как это объясняет автор, 1-е издание вверху, 2-е издание внизу:

Коробочная часть пытается выразить то же самое, только объект меняется с 37 на 31.

А почему он изменился с 37 на 31, автор объяснил во втором издании, то есть той части, которую я отметил подчеркиванием.

31 Есть хороший устав, который заменяет умножение сдвигами и вычитаниями для лучшей производительности:

31*i==(i

Простое изменение числа с 37 на 31 может повысить производительность.

Загадка очень интересная, если интересно, можете проверить соответствующую информацию.

Какой удивительный компьютерный мир.

Хорошо, это все для этой статьи.

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

Спасибо за прочтение, настаиваю на оригинальности, очень приветствую и благодарю за внимание.

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

Добро пожаловать, чтобы следовать за мной.