От коллизии хешей до перезаписи hashCode

Java

Что такое хэш-коллизия?

Так называемый хэш (hash) предназначен для отображения различных входных данных в уникальные значения фиксированной длины (также известные как «хэш-значения»). Это одна из самых распространенных программных операций.

Если разные входные данные получают одно и то же значение хеш-функции, происходит «коллизия хэшей».

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

AFGG2piXh0ht6dmXUxqv4nA1PU120r0yMAQhuc13i8

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

Один из методов взлома — попытаться создать «коллизию хэшей», а затем взломать систему для кражи информации.

Как предотвратить коллизии хешей?

Самый эффективный способ предотвратить коллизии хэшей — расширить пространство значений хеш-значений.

16-битное хеш-значение имеет вероятность коллизии 1 из 65536. То есть если пользователей 65537, то должна быть коллизия. Длина хеш-значения увеличивается до 32 двоичных битов, а вероятность коллизии снижается до 1 из 4 294 967 296.

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

Анализ из String hashCode()

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;
}

наверное

假设 n=3
i=0 -> h = 31 * 0 + val[0]
i=1 -> h = 31 * (31 * 0 + val[0]) + val[1]
i=2 -> h = 31 * (31 * (31 * 0 + val[0]) + val[1]) + val[2]
       h = 31*31*31*0 + 31*31*val[0] + 31*val[1] + val[2]
       h = 31^(n-1)*val[0] + 31^(n-2)*val[1] + val[2]

почему простые числа

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

Так почему 31?

  1. 31 — это простое число, которое не слишком мало и не слишком, и является одним из предпочтительных простых чисел в качестве множителя hashCode.
  2. 31 можно оптимизировать с помощью JVM,31 * i = (i << 5) - 1

Так почему же 2, 7 и 101 не являются простыми числами?

Взяв в качестве примера String str = "abcde", вычисление будет приблизительно

  • Когда 2 -> 2^5 = 32
  • Когда 101 -> 101^5 = 10 510 100 501

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

Наконец, давайте посмотрим на результат вычисления простого числа 31: 31^5 = 28629151, полученное значение относится к32а также10,510,100,501сказать. Разве это не хорошо, не большой или маленький

К тому же в действенной java есть такое предложение
Число 31 было выбрано потому, что оно является нечетным простым числом, а выбор четного числа приведет к переполнению в операции умножения, что приведет к потере числовой информации, поскольку умножение на два эквивалентно операции сдвига. Преимущество выбора простых чисел не особенно очевидно, но это традиция. В то же время число 31 имеет приятную особенность: умножение можно заменить сдвигом и вычитанием для большей производительности:31 * i == (i << 5) - i, современные виртуальные машины Java могут выполнять эту оптимизацию автоматически.

Переопределить хэш-код()

Простой и общий алгоритм hashCode предлагается в «Эффективной Java».

А. Инициализируйте целочисленную переменную и присвойте этой переменной ненулевое постоянное значение, напримерint result = 17;//31

B. Выберите все поля, используемые для сравнения в методе equals (причина, по которой выбираются только поля, используемые в equals(), заключается в обеспечении выполнения первого принципа вышеизложенного), а затем вычислите атрибуты каждого поля:

  1. еслиbooleanстоимость, рассчитатьf ? 1:0;
  2. еслиbyte\char\short\int, затем вычислить(int)f;
  3. еслиlongстоимость, рассчитать(int)(f ^ (f >>> 32));
  4. еслиfloatстоимость, рассчитатьFloat.floatToIntBits(f);
  5. еслиdoubleстоимость, рассчитатьDouble.doubleToLongBits(f), а затем возвращается длинный результат, а затем используйте правило (3) для обработки long, чтобы получить int;
  6. Если это объектное приложение, если метод сравнения рекурсивного вызова принят в методе equals, то метод рекурсивного вызова hashCode также принят в hashCode. В противном случае для этого поля необходимо вычислить нормальную форму.Например, когда значение этого поля равно null, значение hashCode равно 0;
  7. В случае массива каждый элемент необходимо рассматривать как отдельное поле.java.util.Arrays.hashCodeМетод включает в себя вычисление hashCode 8 основных типов массивов и эталонных массивов, а алгоритм такой же, как и выше.

C. Наконец, хэш-код каждого поля объединяется с хэш-кодом объекта.

public class Person {
    private String name;
    private int age;
    private boolean gender;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public boolean isGender() {
        return gender;
    }

    public void setGender(boolean gender) {
        this.gender = gender;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age &&
                gender == person.gender &&
                Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        int hash = 17;
        hash = hash * 31 + getName().hashCode();
        hash = hash * 31 + isGender() ? 1:0;        hash = hash * 31 + getAge();
        return hash;
    }

Ссылаться на:

Уууу. Руань Ифэн.com/blog/2018/0…

сегмент fault.com/ah/119000001…



Категории