IcaBlog

Коллизии HashCode

 
  • Jun 30, 2020

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

Пример такой коллизии:

fun main() {
    ​//generates 310265957 as hashcode
    ​​print("I have a common prefixDB".hashCode())

    //generates 310265957 as hashcode
    print("I have a common prefixCa".hashCode())
}

Вообще если длина строк одинаковая и выполняется:

31*(b[n-2] — a[n-2]) == (a[n-1] — b[n-1])

то, хэши всегда будут одинаковыми, не буду вдаваться в подробности почему так :D

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

Стандартная реализация hashCode

Посмотри сгенерированный idea hashCode() для простого POJO класса.

class Lover(
    private val id: Long,
    private val name: String,
    private val mum: Mum?
) {

    // Также генерится реализация equals, зачем она нужна узнаем ниже
    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (javaClass != other?.javaClass) return false

        other as Lover

        if (id != other.id) return false
        if (name != other.name) return false
        if (mum != other.mum) return false

        return true
    }

    override fun hashCode(): Int {
        var result = id.hashCode()
        result = 31 * result + name.hashCode()
        result = 31 * result + (mum?.hashCode() ?: 0) // Если объект null, он не влияет
        return result
    }
}

У String, кстати свой алгоритм: h(s)=∑(s[index] * 31 ^(n-1-index)) Смысл тот же, только проходим по всем char

31

Как вы заметили везде используется это непонятное число 31. Вопрос: А че не 41 или 97, например?

А по каким критериям оно отбирается?

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

Оказывается 31 идеальный кандидат ведь:

  • Оно простое и нечетное
  • Занимает всего 1 байт в памяти
  • Уго умножение можно заменить на быстрый побитовой сдвиг. 31 * i == (i << 5) - i

PS: А че за (i << x) - i ?

Побитовой сдвиг влево на x позиций. Работает точно также как умножить какое-то число на 2 x раз.

println(n.shl(1)) // 6
println(n.shl(2)) // 12
println(n.shl(3)) // 24

Вернемся к сути.

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

Да ничего, HashMap и HashSet самоcтоятельно обрабытывают такие ситуации. Важно только правильно переопределить метод equals(o) у класса.

Логика работы такая:

  1. Кладем в список объект по ключу “cat”

  2. Кладем в него другой по этому же ключу

  3. HashMap/Set проверяет равны ли эти объекты в методе equals

  4. Если равны - заменяет, если нет, создает в этой ячейке связный список, а например в седьмой джаве бакет в HashMap, при появлении в нём более семи объектов, меняет начинку со связного списка на дерево.

Важно помнить, что получение элемента из связного списка работает за время O(n), и если колиизий наберется много, скорость hash таблицы станет уже далеко не константной.

Поэтому если все же решили использовать String в качестве ключа, можно за основу брать 2 простых числа, скажем 17 и 37. Ребята из Project Lombok придумали здесь

fun main(args: Array<String>) {
    val first = BetterHashString("I have a common prefixDB")
    val second = BetterHashString("I have a common prefixCa")
    println(first.hashCode()) // 177503352
    println(second.hashCode()) // 177503346
}

class BetterHashString(val value: String) {

    override fun hashCode(): Int {
        val prime = 37
        var result = 17
        value.chars().forEach { c -> 
            result = prime * result + c 
        }
        return result
    }
}

Минуточку

Переопределил я hashCode(), но как-же теперь JVM узнает, на какой адрес в памяти ссылается этот объект?

На самом деле у каждого объекта есть идентификационный хеш (identity hash code). Если класс переопределил hashCode(), всегда можно вызвать System.identityHashCode(o).

Да и вообще, hashCode() не возвращает какой-либо адрес объекта в памяти, что бы это не значило. В версиях java 6 и 7 это случайно генерируемое число. В версиях 8 и 9 это число, полученное на основании состояния потока. Подробнее об этом можно почитать здесь

Ссылки

Структуры данных в картинках. HashMap

Java HashCode Collision: How uniform is it’s distribution?

Как работает hashCode() по умолчанию?

Внутренняя работа HashMap в Java

Project Lombok

Search