Мало знаний, большой вызов! Эта статья участвует в "Необходимые знания для программистов«Творческая деятельность.
Эта статья приняла участие"Проект "Звезда раскопок"", чтобы выиграть творческий подарочный пакет и бросить вызов творческим поощрительным деньгам.
- Готовьтесь к весеннему набору или летней стажировке 2022 года, и я желаю вам всем миллион очков прогресса каждый день!Day4
- Эта статья суммирует «Как правильно переписать метод equals JDK», который будет обновляться ежедневно ~
- Для получения знаний, таких как «Приступая к освоению Redis» и «Параллельное программирование», вы можете обратиться к моим предыдущим блогам.
- Верь в себя, живи сильнее, Пока ты жив, ты должен открыть дорогу в горах и построить мост через воду! Жизнь, ты на меня надави, я подарю тебе чудо!
1. Введение
Я не знаю, переписали ли вы метод hashcode в процессе разработки или столкнулись с соответствующими проблемами на собеседовании. Например, некоторые основные задания Java могут запрашивать:Вы когда-нибудь использовали объект в качестве ключа HashMap?
Этот вопрос фактически проверяет соответствующие точки знаний программиста, соответствующие переписыванию метода хэш-кода.Следующий снимок экрана с методом put HashMap показывает, что при добавлении элементов в контейнер для вычисления хеш-значения метод хэш-кода ключевого объекта называется.
Как правильно переопределить метод hashcode?
На самом деле это очень распространенная и, казалось бы, очень простая проблема, но программистов, которые действительно умеют хорошо писать, не так много. (Часто чем очаровательнее, тем опаснее, чем проще, тем сложнее!!!)
Давайте посмотрим вниз, чтобы увидеть, принадлежите ли вы к этому хорошо написанному программисту!
2. Текст
2.1 Когда переписывать
Прежде чем углубляться в то, как переопределить метод хэш-кода, важно понять, когда вам нужно переопределить хэш-код?
Подытоживая эту проблему одним предложением:Классы, которым необходимо переопределить метод equals, должны переопределить метод hashcode!
В этот момент вы спросите,Когда вам нужно переопределить метод equals?
Сяо Ба уже говорил об этом вопросе в предыдущей статье, братья, кому это нужно, могут перейти в мою колонкуСерия "Маленькие знания Java: 100 примеров"посмотри,Кстати, подпишитесь и следите за Xiaoba, чтобы изучать Java и не потеряться!
2.2 Как переписать
Метод hashcode — это собственный метод, предоставляемый Java.lang.Object.Этот метод реализован в jvm и может возвращать адрес текущего объекта в памяти.
// 返回对象在内存中的地址
public native int hashCode();
Поэтому, когда наш класс не переопределяет метод хэш-кода, и остальные суперклассы класса тоже не переопределяют, тогда, когда мы вызываем метод хэш-кода, он всегда будет возвращать адрес объекта в памяти.Это может быть не тот результат, который вам нужен, так как же нам его переписать?
идеи
Для начала нам нужно знать, что мы вычисляем хэш через домен объекта,Поля в объекте не что иное, как массивы, ссылочные типы и базовые типы данных.Типов полей так много.Мы не должны выбирать хэш-значение определенного поля в качестве возвращаемого значения метода хэш-кода объекта, поэтому , мы считаемНакопить хеш-значение домена и вернуть его!
- Основные типы данных, вы можете обратиться к методу хэш-кода соответствующего типа упаковки.
- Для ссылочных типов функция hashcode() вызывается напрямую.
- Типы массивов должны проходить по массиву и вызывать hashcode() по очереди.
Универсальная реализация
Это хэш-метод, предоставляемый java.util.Objects для вычисления хэш-кода. Хотя этоНе серебряная пуля для вычисления хэш-кодов, но мы можем извлечь уроки из этой реализации, и хэш-код большинства классов в исходном коде Java JDK похож на эту реализацию!
public static int hash(Object... values) {
return Arrays.hashCode(values);
}
public static int hashCode(Object a[]) {
if (a == null)
return 0;
int result = 1;
for (Object element : a)
result = 31 * result + (element == null ? 0 : element.hashCode());
return result;
}
Этот метод можно условно разделить на два этапа:
- Если a==null, хэш-код возврата равен 0
- Если != null, пройдитесь по каждому полю, если поле не равно null, вызовите метод хэш-кода поля и накапливайте
Есть очень заметный номер 31, Текущий результат будет *31 каждый раз, когда он зацикливается, почему это так?
На самом деле, функция вычисления результата*31 каждый раз заключается в том,Предотвратить конфликтный хэш! Потому что, если коэффициент умножения не установлен, результат вычисления результата будет относительно небольшим, и очень легко иметь такое же значение хеш-функции после процесса накопления Это не то, что мы хотим видеть!
Так почему же 31? 31 Почему я могу стать настоящим сыном вычислительной команды JDK? , не может быть 2? Не может быть 1001?
На самом деле есть причина использовать множитель 31. Сяоба считает, что есть три причины:
- 31 — это маленькое число, оно не будет слишком маленьким, чтобы привести к конфликту результатов вычисления хэш-кода; поскольку возвращаемое значение является целочисленным типом int, оно не будет слишком большим, что приведет к переполнению возвращаемого значения хэш-кода. .
- 31 — нечетное число. При умножении на нечетное число младшие биты потерять непросто, потому что умножение на 2 эквивалентно беззнаковому сдвигу влево на один бит, который добавит 0 к младшим битам. значение, рассчитанное по хэш-коду, очень легко конфликтовать.
- 31 очень удобен для идентификации виртуальных машин.Для виртуальных машин 31 = 2^5 - 1. Он может оптимизировать это число и преобразовать его в битовые операции, поэтому производительность лучше при умножении
Xiaoba использует коэффициент умножения 2 и коэффициент умножения 31, чтобы провести тест здесь:
package com.liziba.part2;
import org.apache.commons.lang3.RandomStringUtils;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Objects;
/**
* <p>
* HashCode方法测试
* </p>
*
* @Author: Liziba
* @Date: 2021/10/24 11:54
*/
public class HashCodeMethodDemo {
/**
* 计算hashcode
*
* @param value 需计算hashcode字符串
* @param capacity 乘数因子
* @return
*/
public static int hashCode(String value, int capacity) {
int hash = 0;
if (Objects.nonNull(value) && value.length() > 0) {
char[] chars = value.toCharArray();
for (int i = 0; i < chars.length; i++) {
hash = capacity * hash + chars[i];
}
}
return hash;
}
/**
* hash值冲突比较
*
* @param capacity
* @param hashValues
*/
public static void conflictCompare(int capacity, List<Integer> hashValues) {
Comparator<Integer> comparator = (x, y) -> (x > y) ? 1 : ((x < y) ? -1 : 0);
Integer max = hashValues.stream().max(comparator).get();
Integer min = hashValues.stream().min(comparator).get();
long conflictNum = hashValues.size() - hashValues.stream().distinct().count();
double conflictRate = conflictNum * 1.0 / hashValues.size() ;
System.out.println(String.format("乘数因子capacity=%d 冲突数=%d 冲突率：%.4f%% 最大值：%d 最小hashCode：%d",
capacity, conflictNum, conflictRate * 100, max, min));
}
public static void main(String[] args) {
int num = 100000;
int capacity2 = 2;
int capacity31 = 31;
List<Integer> hashValues2 = new ArrayList<>(num);
List<Integer> hashValues31 = new ArrayList<>(num);
for (int i = 0; i < num; i++) {
// 生成随机数 org.apache.commons.lang3.RandomStringUtils
String value = RandomStringUtils.randomAlphabetic(15);
hashValues2.add(hashCode(value, capacity2));
hashValues31.add(hashCode(value, capacity31));
}
conflictCompare(capacity2, hashValues2);
conflictCompare(capacity31, hashValues31);
}
}
Всего было протестировано 100 000 случайных строк длиной 15 цифр.
- Когда множитель равен 2, конфликтность близка к 4%.
- Когда множитель равен 31, конфликтность составляет всего 0,0010%
Нужно ли умножать на 31 при переписывании метода hashcode?
Это определенно не так!Коэффициент умножения 31 — это просто решение для уменьшения конфликтов хэшей, вам определенно не нужно использовать коэффициент умножения, когда он вам не нужен!